探索学习与面试中的HashMap奥秘

探寻学习与面试中的HashMap核心知识

1. HashMap的结构特性

• 结构构成：由桶数组搭配链表或者红黑树组成
• 转换情形：（共3点）
  • 当链表长度超过8且桶数组长度不少于64时，链表会转换为红黑树。
  • 若链表长度超8，但桶数组长度未达64，优先进行扩容操作，以提升桶数组长度。
  • 当红黑树节点数量小于等于6时，红黑树会退回到链表形态。
• 链表的查找时间复杂度为O(n)，长度较长时查找性能会下降。红黑树是一种折中的方案，其查找、插入、删除操作的时间复杂度均为O(log n)。

2. 红黑树的基础讲解

红黑树属于自平衡的二叉查找树，不过其平衡条件相比平衡二叉树没那么严格。

具备5点特性
* 每个节点不是红色就是黑色；
* 根节点始终为黑色；所有的叶子节点（即NULL节点）均为黑色；
* 红色节点的子节点必定是黑色；
* 从任意一个节点到其每一个叶子节点的所有简单路径所包含的黑色节点数目相同（不会走回头路）；
* 任意一条路径的长度不会超过另一条路径长度的两倍。

对比平衡二叉树
* AVL树在查、插、删操作时的时间复杂度也是O(log n)，但它查找速度更快，树的高度更矮；不过插入和删除操作更慢，需要处理更多的旋转操作（红黑树主要通过旋转和染色来处理）。

3. HashMap的扩容机制【关键】

• 首先，HashMap的容量是2的幂次方，这样做的目的是将取模运算hash % table.length优化成位运算hash & (length - 1)。
• 扩容是依据总表的所有节点数来判断的，并非只看链表或者桶数组；其时间复杂度为O(n)。
• 通常扩容为原来的2倍，不需要重新进行哈希运算，只需通过判断hash & oldCap == 0就能知晓键在新数组中的位置，这里的Cap指桶数组的大小。

扩容的三种情况
* 单个节点：indexNew = hash & (newCap - 1)，这相当于取模运算。
* 链表情况：遍历链表，将链表拆分成两个链表
* 低位链表（Lo）：当hash & oldCap == 0时，保留在原位置。
* 高位链表（Hi）：当hash & oldCap != 0时，移动到原位置 + oldCap的位置。
* 红黑树结构
* 如果当前桶是红黑树（TreeNode），HashMap会调用split()方法进行分裂。
* 分裂后的红黑树若节点数小于等于UNTREEIFY_THRESHOLD（默认6），会退回到链表形态。
* 举例说明：8的二进制是1000，扩容后16的二进制是10000，那么newCap - 1的二进制是1111。indexNew = hash & (newCap - 1)相当于保留二进制的低四位，也就是0 - 15，等同于取模运算。hash & oldCap相当于把桶数组分成了两部分，0 - 7是旧的部分，8 - 15是新的部分。当低四位中的第四位不是1时，就在旧的部分，不需要迁移，需要迁移的情况是原位置 + oldCap。

扩容后顺序变化情况：JDK7扩容时使用头插法重新插入链表节点，这会导致链表无法保持原有的顺序（头插法性能高，无需遍历）。JDK8改用了尾插法，并且当(e.hash & oldCap) == 0时，元素保留在原索引的位置；否则元素移动到原索引 + 旧数组大小的位置。元素迁移是逐个进行的，所以扩容后用头插法会出现倒序，基于此会出现常见问题：头插法 + 多线程操作 + 扩容会导致形成环形链表。例如：原链表是a → b → c，两个线程同时扩容（假设链表不拆分），理想情况下应该是c → b → a。线程A线头插【a】（它的current和next指针更新，指向b，c），线程A、B同时进行插入【b，c】，线程B抢占成功，最终得到c → b → a，此时线程A恢复（它不知道线程B做了修改，此时它的current和next指针还是指向b，c），继续插入b：b → c → b 【b → a断了】a ，形成死循环。

4. HashMap的put流程【关键】

流程大致为哈希寻址（123）→ 处理哈希冲突（判断是链表还是红黑树）→ 插入/覆盖节点（45）→ 判断是否需要扩容（67）

• 扰动哈希：先获取key的哈希值，它是32位的int类型数值，然后让哈希值的高16位和低16位进行异或操作，以此保证哈希分布均匀。（补充：哈希表的索引是通过h & (n-1)计算的，相当于截取了最低的四位。只取h的低位很容易导致哈希冲突。通过异或操作将h的高位引入低位，可以增加哈希值的随机性，从而减少哈希冲突。）
• 判断table是否为null或空，若是就进行首次分配；并使用哈希值和数组长度进行取模运算，确定索引位置。（这里有懒加载，HashMap在初始化时，并不会立即创建存储键值对的数组。只有当第一次调用put()、get()等方法时，才会触发数组的初始化。）
• 如果value相同则覆盖，不同则代表有哈希冲突，插入链表尾部，当条件达到后，链表转换为红黑树。
• 判断是否需要扩容：大于capacity * loadFactor（总容量*负载因子，默认为0.75）。
• 新建桶数组容量为原来的2倍，进行扩容。

HashMap.put(k, v)
1. 计算扰动 hash 值（h = hash(k) ^ (h >>> 16)）
2. 判断 table 是否为空，若为空则初始化
3. 计算桶索引 index = (n - 1) & hash
4. 若无冲突：直接插入
5. 若冲突：
   - 若 key 已存在：替换
   - 否则插入链尾
   - 若链表 > 8 且 table ≥ 64：转红黑树(插入链表后再转换为红黑树)
6. 插入完成后：size++
7. 判断是否 > threshold？若是：resize（扩容）

5. JDK 8对HashMap做了哪些优化？

• 结构变化：由数组 + 链表改成了数组 + 链表或红黑树。
• 插入方式改变：由头插法改为了尾插法。头插法在扩容后会改变原来链表的顺序。
• 扩容时机调整：扩容的时机由插入时判断改为插入后判断。
• 哈希扰动算法优化：JDK 7是通过多次移位和异或运算来实现的。JDK 8让 hash 值的高16位和低16位进行了异或运算。

6. LinkedHashMap、TreeMap对比

• LinkedHashMap在HashMap的基础上维护了一个双向链表，通过before和after标识前置节点和后置节点，保持插入顺序。
• TreeMap通过key的比较器来决定元素的顺序，如果没有指定比较器，那么key必须实现[Comparable接口]。底层是红黑树，类比二叉排序树实现顺序访问。
• TreeMap的key不允许出现NULL，因为NULL无法比较，而另外两个可以。