深入理解 Java 中的 HashMap 底层原理

摘要：​ 探讨 HashMap 的数据结构、哈希冲突的解决方案以及在 JDK 1.8 中的优化。

HashMap 是 Java 后端和 Android 开发中最高频使用的数据结构之一。今天在阅读源码时，对其底层实现有了更深的理解。

数据结构

JDK 1.8 中，HashMap 采用 数组 + 链表 + 红黑树​ 的结构。

• 数组 (Node<K,V>[] table)：用于快速定位下标。
• 链表：解决哈希冲突，当同一位置元素过多时形成链表。
• 红黑树：当链表长度大于阈值（默认为 8）且数组容量大于 64 时，链表转为红黑树，将查找时间复杂度从 O(n) 降至 O(log n)。

Hash 算法

javajavastatic final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这段代码将高 16 位与低 16 位进行异或运算，增加了低位随机性，减少了 Hash 冲突的概率。