参考文章

HashMap 源码详细分析(JDK1.8)

继承关系

image.png

数据结构

底层由桶数组+链表或红黑树组成

一些重要属性的值都是多少

1. 常量

  • 默认初始容量：DEFAULT_INITIAL_CAPACITY = 1 << 4
  • 最大容量：MAXIMUM_CAPACITY = 1 << 30
  • 默认负载因子：DEFAULT_LOAD_FACTOR = 0.75f
  • 最小树化容量：MIN_TREEIFY_CAPACITY = 64
  • 树化阈值：TREEIFY_THRESHOLD = 8

  • 反树化阈值：UNTREEIFY_THRESHOLD = 6

    2. 可调整参数

  • 初始容量：initialCapacity 只作为参数并通过 tableSizeFor(int cap) 赋值给 threshold

  • 负载因子：loadFactor
  • 阈值：threshold 当前所能容纳键值对数量的最大值，超过这个值，则需扩容。调用有参构造函数时为大于 initialCapacity 的最小2的幂，真正初始化底层数据结构时会通过 capacity * load factor 计算

    什么时候创建的底层数据结构

    以下除4之外的构造方法在调用时，只赋值了一些基本参数，并未实际创建底层数据结构，是在第一次插入元素时才实际创建底层数据结构
  1. public HashMap(int initialCapacity, float loadFactor) 阈值最开始为大于 initialCapacity 的最小2的幂，等真正初始化底层数据结构时会通过 capacity * load factor 计算；
  2. public HashMap(int initialCapacity)：使用默认负载因子 DEFAULT_LOAD_FACTOR = 0.75f，阈值同上；
  3. public HashMap()：使用默认容量 DEFAULT_INITIAL_CAPACITY = 1 << 4
  4. public HashMap(Map<? extends K, ? extends V> m)

    什么情况下转成红黑树

    插入元素时当链表长度>=TREEIFY_THRESHOLD(8) 时，且桶数组大小 >= MIN_TREEIFY_CAPACITY(64) 时，才转换成红黑树，否则只扩容桶数组。原因是当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长，此时应优先选择扩容。如果优先树化，由于此时容量较小，可能出现频繁扩容进而造成红黑树频繁拆分和反树化，比较耗时；

    扩容机制

  • 元素数量 > 阈值时会扩容；
  • 当某链表长度>=TREEIFY_THRESHOLD(8) ，且桶数组大小 < MIN_TREEIFY_CAPACITY(64) 会扩容；

扩容时，如果容量>= MAXIMUM_CAPACITY(230) 则不进行扩容，当 DEFAULT_INITIAL_CAPACITY=< 容量2 <=MAXIMUM_CAPACITY 时，桶数组长度和阈值都扩大为原来的2倍，注意此时阈值可能会溢出，若溢出会使用 capacity load factor 重新计算；扩容后会出现链表或红黑树的拆分

链表和红黑树如何拆分

根据 hash & oldCap 拆分链表和红黑树，拆分红黑树时由于树节点通过 next 和 prev 保留了原有的链表结构，因此拆分和链表过程类似，只不过拆分成了两段，会再判此时拆分出的链表长度 < UNTREEIFY_THRESHOLD，是则将链表转换成普通链表, 否则根据条件重新将 TreeNode 链表树化

如何计算 hash 值

通过(h = key.hashCode()) ^ (h >>> 16)计算，为了减少碰撞原因如下：

  1. 让 key 的 hash 值高位也可以参与桶数组下标的计算；
  2. 对于分布性不佳的 hashCode 方法，可以增加 hash 复杂度；

hashCode 方法产生的 hash 是 int 类型，32 位宽。前16位为高位，后16位为低位，所以要右移16位

如何计算 hash 值在桶数组的位置

HashMap 中桶数组的大小 length 总是2的幂，此时，(n - 1) & hash 等价于对 length 取余。但取余的计算效率没有位运算高，所以 (n - 1) & hash 也是一个小的优化