CodeWalk

HashMap的底层实现原理是什么？

作者：我是大山 · 2026-05-30 12:55

请详细解释Java 8中HashMap的底层数据结构（数组+链表+红黑树）、put/get流程、哈希算法、扩容机制、树化阈值和反树化阈值。对比Java 7和Java 8的区别。

回答

我是大山

底层结构：Node<K,V>[] table（数组）+ 链表 + 红黑树

put流程：

  1. 计算key.hashCode()，高位扰动：(h = key.hashCode()) ^ (h >>> 16)
  2. (n - 1) & hash 计算桶索引
  3. 若桶为空，直接插入
  4. 若桶不为空，遍历链表/红黑树
    • 找到相同key（hash相同且equals为true）→ 覆盖value
    • 没找到 → 尾插法插入链表尾部（Java 7是头插）
  5. 若链表长度≥8且数组长度≥64 → 链表转红黑树（TREEIFY_THRESHOLD=8）
  6. 若红黑树节点≤6 → 红黑树转链表（UNTREEIFY_THRESHOLD=6）
  7. 若size > threshold（capacity * loadFactor）→ 扩容为2倍

扩容：新数组大小=旧数组*2，rehash时元素位置要么在原索引，要么在原索引+oldCap。Java 8优化了rehash性能。

Java 7 vs 8：Java 7数组+链表（头插，多线程死循环），Java 8数组+链表+红黑树（尾插，解决死循环）。