深入解析 HashMap 底层原理与源码 (JDK 1.8)

在 Java 与 Android 开发中，HashMap 是使用最频繁的集合之一，也是面试中出现频率最高的考点。本文将基于 JDK 1.8，带你深入阅读并剖析 HashMap 的底层原理。

1. 底层数据结构

在 JDK 1.7 中，HashMap 由数组 + 单向链表组成。 到了 JDK 1.8，为了解决严重哈希冲突下链表过长导致查询效率降级（O(1) 退化为 O(n)）的问题，底层数据结构升级为了：数组 + 单向链表 + 红黑树。

当链表长度超过阈值（8）且数组容量达到（64）时，链表将转化为红黑树，从而将最坏情况下的查询时间复杂度从 $O(n)$ 优化到 $O(\log n)$。

核心节点源码

数组中存储的元素是 Node 或者 TreeNode：

// 单向链表节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    // 经过扰动函数计算后的 hash 值
    final K key;       // 键
    V value;           // 值
    Node<K,V> next;    // 指向下一个节点的指针
    
    // ...
}

// 红黑树节点（继承自 LinkedHashMap.Entry，间接继承自 HashMap.Node）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父节点
    TreeNode<K,V> left;    // 左子节点
    TreeNode<K,V> right;   // 右子节点
    TreeNode<K,V> prev;    // 删除节点时需要取消链接
    boolean red;           // 颜色属性（红黑树特性）
}

2. 核心属性与阈值

HashMap 中有几个至关重要的静态常量，规定了它的运作机制：

// 默认初始容量（数组大小）：必须是 2 的整数次幂。1 << 4 即 16。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// 数组最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子：衡量 HashMap 满的程度，0.75 是时间和空间成本的折中。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 树化阈值：链表长度达到 8 时，可能转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 退化阈值：当树中的节点数量减少到 6 时，红黑树将退化为链表
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树化容量：链表转为红黑树的前提是，数组的总容量不能小于 64，
// 否则优先选择扩容（resize），而不是树化。
static final int MIN_TREEIFY_CAPACITY = 64;

3. Hash 算法（扰动函数）

当我们存入一个键值对时，如何计算它在数组中的下标？

static final int hash(Object key) {
    int h;
    // 如果 key 为 null，直接存入下标 0 的位置。
    // 否则，拿到对象的 hashCode，并将其与自身无符号右移 16 位的结果进行异或（^）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么要异或自己右移 16 位的值？

• hashCode() 返回的是一个 32 位 int 类型。如果直接使用它进行后续的下标计算（(n - 1) & hash），由于通常数组的长度 n 不会很大（比如默认 16），那么只有 hashCode 的低位会参与运算。
• (h = key.hashCode()) ^ (h >>> 16) 这步操作叫做扰动函数，它将高 16 位和低 16 位混合（异或），使得高位的特征也保留在了低位中，从而让 Hash 值的分布更加均匀，减少哈希冲突。

4. put() 方法的完整源码解析

put() 操作是 HashMap 的核心，它底层调用的是 putVal() 方法。我们逐行分析其逻辑：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 判断当前数组是否为空（懒加载机制，第一次 put 时才初始化）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // 执行扩容/初始化，并拿到数组长度
        
    // 2. 计算数组下标：i = (n - 1) & hash，等同于 hash % n (前提 n 是 2 的幂)
    // 如果该下标对应的位置没有节点，直接新建 Node 放进去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 以下为发生 Hash 冲突的处理逻辑
        Node<K,V> e; K k;
        
        // 3. 冲突节点正是我们要找的节点（hash 值相同，且 key 用 == 或 equals 判断相等）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            
        // 4. 判断当前位置是否已经是红黑树了？
        else if (p instanceof TreeNode)
            // 如果是红黑树，走红黑树的插入或更新逻辑
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            
        // 5. 当前节点是普通单向链表
        else {
            // 遍历链表
            for (int binCount = 0; ; ++binCount) {
                // 如果遍历到了链表尾部
                if ((e = p.next) == null) {
                    // JDK 1.8 采用【尾插法】追加新节点
                    p.next = newNode(hash, key, value, null);
                    
                    // 6. 判断链表长度是否达到树化阈值（binCount >= 7 说明原本长度是 8，加上新增的 1 个变成了 9）
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash); // 尝试树化（内含对数组容量是否大于 64 的判断）
                    break;
                }
                
                // 遍历过程中发现了相同的 key，停止遍历，准备覆盖该值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                    
                p = e;
            }
        }
        
        // 7. 如果找到了已存在的 key（e 不为空）
        if (e != null) { 
            V oldValue = e.value;
            // 判断是否允许覆盖（onlyIfAbsent 为 false，或旧值为 null）
            if (!onlyIfAbsent || oldValue == null)
                e.value = value; // 覆盖新值
            afterNodeAccess(e);  // LinkedHashMap 的回调，HashMap 内部为空实现
            return oldValue;     // 返回旧值
        }
    }
    
    ++modCount; // 结构修改次数加 1，用于 fast-fail 机制
    
    // 8. 成功插入新节点后，判断当前元素个数是否超过了阈值，若超过则扩容
    if (++size > threshold)
        resize();
        
    afterNodeInsertion(evict); // 同样是回调方法
    return null;
}

5. 扩容机制 resize() 与巧妙的重分配

HashMap 何时扩容？

1. 初始化时（第一次 put）。
2. size > threshold（当前元素个数大于容量的 0.75 倍）时。
3. 链表长度达到 8 但数组总容量小于 64，优先进行扩容。

JDK 1.8 最大的优化之一在于数据迁移的过程。由于每次扩容都是原容量的 2 倍，这就导致旧数组中的元素，在新数组中只有两种可能的去处：

1. 保留在原索引位置。
2. 移动到：原索引 + 旧数组长度 的位置。

源码中利用了非常巧妙的位运算技巧：e.hash & oldCap。

// 旧链表迁移核心逻辑（省略了红黑树及前面的部分代码代码）
Node<K,V> loHead = null, loTail = null; // 存放不需要移位的节点 (Low)
Node<K,V> hiHead = null, hiTail = null; // 存放需要移位的节点 (High)
Node<K,V> next;

do {
    next = e.next;
    // 【核心技巧】如果 hash 值与旧数组容量进行按位与运算等于 0
    // 说明由于容量乘 2 增加的那个高位上，hash 值该位也是 0
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    // 否则，说明需要移位
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

// 原位置不动的链表，放入新数组的原下标
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
// 需要移动的链表，放入新数组的：原下标 + 旧容量
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

为什么 (e.hash & oldCap) == 0 能判断是否移位？ 假设原容量 oldCap 是 16（二进制 10000）。那么扩容后新容量是 32（二进制 100000）。 原来计算下标的掩码 n - 1 是 01111，扩容后的新掩码是 11111。 只有哈希值在原来掩码的前一位（即第 5 位，对应值正好是 16）是 1 时，下标才会改变。 因此，hash & 16 如果等于 0，新下标等于旧下标；如果等于 16（非 0），新下标等于旧下标加 16（旧容量）。这一步省去了重新计算 hash % n 的开销，非常高效。

6. 面试常见追问解答

1. 为什么 HashMap 的容量必须是 2 的幂次方？ 为了能使用高效的位运算 (n - 1) & hash 来代替取模运算 hash % n，提升性能。而且保证了扩容时元素能均匀散列到两半区间中。
2. 为什么 Load Factor 是 0.75？ 这是一个时间和空间成本的折中。如果设为 1，空间利用率高，但更容易发生哈希冲突，链表拉长导致查询效率下降；如果设为 0.5，哈希冲突极少，但内存浪费一半，频繁触发扩容操作。数学上（基于泊松分布），0.75 能够在理想情况下有效控制链表的长度。
3. 线程安全吗？ 绝对不安全。 JDK 1.7 并发扩容时可能产生循环链表（由于头插法）；JDK 1.8 虽用尾插法解决了死循环问题，但并发写入时仍然会导致数据丢失和覆盖问题。多线程环境请使用 ConcurrentHashMap。