HashMap 源码阅读笔记
HashMap
java.util.HashMap
HashMap 允许 key 和 value 为 null,不保证元素的顺序。HashMap 的 get 和 put 可以实现常数级别的复杂度。 HashMap 的初始容量 capacity 和 负载因子 load factor 对其性能的影响比较大。当 Entry 的数量超过 capacity * load factor 时,哈希表将会被 rehash(内部的数据结构重建)
另外 HashMap 非线程安全,不过可以借助 Collections.synchroniedMap
进行包装。
1 | Map m = Collections.synchronizedMap(new HashMap(...)); |
源码阅读
一、静态成员变量
1 | /** |
相关思考:
容量为什么是 2 的幂次?
这就要从 hashMap 元素 put 的时候说起了,要找到放入新元素的位置,我们一般想到的思路是将 key 的 hash 值对 hash table 的长度 n 取余,但是%运算的效率比较低,于是在这里引入位运算,通过
hash & (n-1)
来获得新元素的索引位置,只有当 n 为 2 的次幂时,才满足一个公式:(n - 1) & hash = hash % n
。(注意:这里 hash 值不是 key 的 hashCode,后面会解释。)负载因子为什么是 0.75?
Java API 中解释:取 0.75 是时间和空间效率的一个权衡。较高的值会降低空间开销,但会增加查找成本。
我的理解是:如果 load factor 取的比较小,比如 0.5, 那么达到容量的一半就会进行扩容,这样会频繁进行 resize 操作。而扩容时变成原来容量的两倍,还会使得使用空间和未使用空间的差值逐渐增加,空间利用率低下。 假如说 load factor 取的比较大,比如 1,那么要等到所有空间都用完了才进行扩容,put 时的时间效率就会很低。可以说 0.75 是 0.5-1.0 的一个中间值。
🌻来自 StackOverFlow 的一个数学解释:
一个 bucket 空和非空的概率为 0.5,通过牛顿二项式等数学计算,得到这个 load factor 的值为log(2),约等于 0.693. 回答者说,可能小于0.75 大于等于log(2)的factor都能提供更好的性能,0.75这个数怎么来的,大概是方便计算?
为什么达到 8 转红黑树?
也是一个数学统计,根据泊松分布,在负载因子0.75(HashMap默认)的情况下,单个 hash 槽内元素个数为 8 的概率小于百万分之一;链表转红黑树的开销和冲突带来的额外开销的一个权衡;
为什么到 6 才转链表?
中间有个差值 7 可以防止链表和树之间频繁的转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。
源码继续来看😁
1 | static final int hash(Object key) { |
我们上面提到,计算元素 key 的索引位置时需要用到 hash 值,就是通过这个函数计算得到的,key 的 hashCode 右移 16 位,与自身做异或计算。实际上就是高低位异或。
✨这样做有什么好处呢?
HashMap 的初始容量是16,要远小于 int 类型的范围,所以如果只是单纯的用 hashCode 取余来获取对应的 bucket 会大大增加哈希碰撞的概率,并且最坏情况下还会将 HashMap 变成一个单链表。主要是因为如果使用 hashCode 取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以为了让 hashCode 高位也参与运算,进一步降低 hash 碰撞的概率,使得数据分布更平均,就采取了这样的优化策略。
二、构造方法
HashMap 在创建的时候,如果不传入初始容量,会默认建立一个 16 的 hash table,所以当需要的 HashMap 存储的元素比较大的时候,建议传入容量大小,避免频繁 resize。
另外当使用默认构造方法的时候,只是将 loadfactor 设为了 0.75,这里的 threshload 仍然为 0
而当使用后面两个构造方法的时候,初始化 loadfactor 为设定值,另外会将 hash table 的 threshold 设为大于传入容量值的最小的 2 的次幂(tableSizeFor 方法)
1 | // 空参构造,使用初始容量 16,load factor 0.75 |
三、查找
1 | public V get(Object key) { |
四、插入 Put
hash table 的初始化是在 put 中通过调用 resize() 完成的
1 | public V put(K key, V value) { |
总结:
hashtable 为空,调用 resize,创建 hash table
计算出的索引位置没有元素,直接创建一个新的节点
如果发生了 hash 冲突:
key 是否存在:
- 若存在直接修改旧值,进行覆盖
- 不存在,判断该节点是链表中的元素还是红黑树:
- 链表,则插入链表尾部,当链表的长度大于调整阈值时,将链表转成红黑树
- 红黑树,执行红黑树的操作
若 hash table 中的元素超过阈值,进行扩容。
之前看过的一张图,比较清楚,链接找不到了,望作者原谅。
五、扩容
当 HashMap 中的键值对数量超过 hash table 容量 * load factor
时,进行扩容。
HashMap 按当前容量的 2 倍进行扩容,阈值也变为原来的 2 倍(如果计算过程中,阈值溢出归零,则按阈值公式重新计算)。扩容之后,要重新计算键值对的位置,并把它们移动到合适的位置上去。
1 | final Node<K,V>[] resize() { |
总结:
计算新的 hash table 的容量和阈值
创建新的 hash table 并进行初始化,将键值对节点重新映射到新的 hash table 里。如果节点是 TreeNode 类型,则需要拆分红黑树。如果是普通节点,则节点按原顺序进行分组。
Java 1.8 扩容的过程要比 1.7 更加复杂,是为了解决 1.7 扩容时的循环引用问题,因为 HashMap 非线程安全,扩容分组指针的指向过程在纸上画一下就很容易明白了。
最后
本来是想了解一下 HashMap 的扩容机制的,零零散散写了这么多,可能有一些错误的地方。
另外关于链表和红黑树的转换,扩容时红黑树的拆分还没有好好研究,下次专门总结一下吧。
历史上最长的一篇博客,哈哈,蛮不容易的,但阅读源码并分析的过程也是特别快乐~~
附上讲解的比较好的几篇博客:
- 本文作者: Kelly Liu
- 本文链接: http://tiantianliu2018.github.io/2020/03/26/HashMap-源码阅读/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!