HashMap
|
这里是修真院后端小课堂，每篇分享文从 【背景介绍】【知识剖析】【常见问题】【解决方案】【编码实战】【扩展思考】【更多讨论】【参考文献】 八个方面深度解析后端知识/技能，本篇分享的是： 【HashMap 】 （1）背景介绍： 不讲HashMap的使用方法，看一看底层的源码是什么？ 思考：HashMap使用key,·value进行存储，使用的数据结构是什么？ 我们知道数组和链表两种数据结构 数组： 优点：查询速度快 缺点：增加和删除慢 链表： 优点：增加和删除快 缺点：查询速度慢 那我们可不可以将两者的优点结合一下，达到查询、增加、删除效率都非常快呢？ 所以我们猜测一下，HashMap能否源码底层数据结构是采用的链表+数组的形式呢？ （2）知识剖析： 1.HashMap数据底层具体存储的是什么？ Java是一门面向对象开发的语言，可以把所有东西可以看做是对象。 通过查看源码可知：map里面的key和value都保存在了这个Node对象里面。 class Node ? ? private K key;? ?//用来定位数组索引位置 ? ? private V value; ? ? private Node } 2.数组怎么表示？ transient Node< K,V>[] table; 每个列表被称为桶，即哈希桶数组，是一个Node的数组。 HashMap使用哈希表进行存储。怎样得到表中对象的索引位置？ key.hashCode( )----->hashCode----->Hash算法的高位运算和取模运算----->得到存储位置 有时两个key会定位到相同的位置，就发生了Hash碰撞。Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。 如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞。 3.数组要不要有一个大小呢？ 学过数组都知道，要给数组一个初始化大小，那么HashMap有没有大小呢？ Defalutsize = ...? 初始大小？？？ Maxmumsize = ...? ?上限大小？？？ 肯定是要有的。 4.数组初始大小是多少呢？ 从源码可以看到 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 初始大小是16 如果初始大小不够用，或者达到某个值，是不是要进行数组大小的扩容？ final Node 5.扩容是不是要有一个依据？ int threshold = 16; Node[] table的初始化长度 transient int size; HashMap中实际存在的键值对数量 size > threshold * 小于1的小数? 实际使用的size肯定不可能达到16才进行扩容，那样会损失性能，一定要达到一个点就进行扩容，这个点是0.25 0.5 0.75哪一个呢？ 源码中定义了一个扩容因子 static final float DEFAULT_LOAD_FACTOR = 0.75f size = threshold * Load factor ----->16 * 0.75 =12 所以在12的时候就会进行扩容。 为什么要选择0.75？ 默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。 6.链表的是不是需要一个长度限制呢？ 负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。链表达到一个限制值后，是否需要进行一个改变？ 在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。 当链表长度太长时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能 源码中定义，当链表超过8时，就转化为红黑树 static final int TREEIFY_THRESHOLD = 8; 7.Node节点到底存在哪里？ 存在哪里要有一个位置，这个位置就是通过计算得来的。 利用这个key进行一个计算，计算出这个Node应该存在哪里。 想知道key,value存放在HashMap结构中的位置，使用hash函数，源码的实现(方法一+方法二): 方法一： static final int hash(Object key) {? ?//jdk1.8 & jdk1.7 ? ? ?int h; ? ? ?// h = key.hashCode() 为第一步 取hashCode值 ? ? ?// h ^ (h >>> 16)? 为第二步 高位参与运算 ? ? ?return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 方法二： static int indexFor(int h,int length) {? //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的 ? ? ?return h & (leng （3）常见问题： HashMap线程安全吗？ （4）解决方案： HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全ConcurrentHashMap。 （5）编码实战： 比如我的一个key的哈希值 h=hashCode()： 22222222222222222222000011101010 h>>>16： 00000000000000002222222222222221 hash=h^(h>>>16)： 22222222222222210000111100010101 (n-1)&hash： 22222222222222210000111100010101 最后取后四位0101转换成十进制就是5 （6）拓展思考： JDK1.8与JDK1.7的性能对比？ JDK1.8引入红黑树大程度优化了HashMap的性能。 （7）参考文献： Java 8系列之重新认识HashMap——美团技术团队 （8）更多讨论： Q1.Map集合还有哪些实现类？ A1:LinkedHashMap、Hashtable和treeMap Q2.HashMap为什么要保证hashmap的容量为2的幂次方？ A2:HashMap容量为2的幂次方，是为了减小哈希冲突，因为如果存在哈希冲突的时候，存储entry的时候，会出现一个位置上存在多个entry的情况，会造成读写速度的降低；使用2的幂次方的容量，存储的时候，会根据key的哈希值跟hashmap的(容量-1)进行位运算，这样的运算，当(容量-1)的二进制数全为1的时候，存储位置的计算结果是哈希冲突最小的。 Q3.HashMap优缺点？ A3:它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。 （9）鸣谢： （10）结束语： 今天的分享就到这里啦，欢迎大家点赞、转发、留言、拍砖~ PPT链接?视频链接 更多内容，可以加入IT交流群565734203与大家一起讨论交流 这里是技能树·IT修真院：，初学者转行到互联网的聚集地 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |