前言

HashMap 是 Java 面试的必考题。"HashMap 底层原理"这个问题，10 个面试 9 个会问。

但很多人只知道"数组+链表+红黑树"，追问细节就答不上来：

• 为什么负载因子是 0.75？

• 链表转红黑树的阈值为什么是 8？

• resize 到底做了什么？

• put 流程你能完整说一遍吗？

本文从 JDK 1.8 源码出发，逐行拆解 HashMap 的核心逻辑。

核心数据结构

组件	类型	作用	类比
table	Node[] 数组	存储所有键值对	书架的格子
Node	链表节点	处理哈希冲突	格子里的书
TreeNode	红黑树节点	链表过长时优化查询	格子里的索引卡
size	int	当前元素数量	书的数量
threshold	int	扩容阈值 = capacity × loadFactor	书架满了要换大的临界点
loadFactor	float	负载因子，默认 0.75	书架多满就该换

// JDK 1.8 HashMap 核心结构
public class HashMap<K,V> {
​
    // 默认初始容量：16（必须是 2 的幂）
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
​
    // 最大容量：2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
​
    // 默认负载因子：0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
​
    // 链表转红黑树的阈值：链表长度 >= 8 且数组长度 >= 64
    static final int TREEIFY_THRESHOLD = 8;
​
    // 红黑树退化为链表的阈值：节点数 <= 6
    static final int UNTREEIFY_THRESHOLD = 6;
​
    // 最小树形化容量：64
    static final int MIN_TREEIFY_CAPACITY = 64;
​
    // 实际存储数组
    transient Node<K,V>[] table;
​
    // 元素数量
    transient int size;
​
    // 扩容阈值
    int threshold;
}

put 流程（完整版）

这是 HashMap 最核心的流程，面试必背：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
​
/**
 * put 完整流程：
 * 1. 计算 key 的 hash 值
 * 2. 如果 table 为空，调用 resize() 初始化
 * 3. 用 hash & (n-1) 定位数组下标
 * 4. 如果该位置为空，直接插入新 Node
 * 5. 如果该位置有元素：
 *    a. key 相同 → 覆盖 value
 *    b. 是 TreeNode → 红黑树插入
 *    c. 是链表 → 尾插法插入，链表长度 >= 8 且数组 >= 64 → 转红黑树
 * 6. 插入后 size++，如果超过 threshold → resize() 扩容
 */
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：table 为空则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
​
    // 步骤 2：定位下标，如果为空直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
​
        // 步骤 3：key 相同，覆盖
        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) {
                    p.next = newNode(hash, key, value, null);  // 尾插法
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);  // 链表长度 >= 8，尝试转红黑树
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
​
        // 覆盖旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
​
    ++modCount;
​
    // 步骤 6：超过阈值则扩容
    if (++size > threshold)
        resize();
​
    return null;
}

💡 关键区别：JDK 1.7 用头插法（多线程死循环），JDK 1.8 改为尾插法，解决了并发扩容的死循环问题。

hash 计算原理

HashMap 不直接用 hashCode()，而是做二次扰动，减少哈希冲突：

/**
 * hash 扰动函数
 * 高 16 位与低 16 位异或
 * 让高位也参与下标计算，减少冲突
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
​
// 下标计算：hash & (n-1)
// 等价于 hash % n（但位运算更快）
// 前提：n 必须是 2 的幂

为什么容量必须是 2 的幂？

容量	n-1（二进制）	& 运算效果
16	0000 1111	取 hash 低 4 位
32	0001 1111	取 hash 低 5 位
64	0011 1111	取 hash 低 6 位

2 的幂 - 1 的二进制全是 1，这样 hash & (n-1) 等价于取模，且分布均匀。

扩容机制（resize）

/**
 * 扩容核心逻辑：
 * 1. 新容量 = 旧容量 × 2
 * 2. 新阈值 = 新容量 × loadFactor
 * 3. 创建新数组
 * 4. 重新分配所有元素（核心优化：不用重新 hash）
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
​
    if (oldCap > 0) {
        newCap = oldCap << 1;  // 容量翻倍
        newThr = oldThr << 1;  // 阈值翻倍
    } else {
        newCap = DEFAULT_INITIAL_CAPACITY;  // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  // 12
    }
​
    Node<K,V>[] newTab = new Node[newCap];
​
    // 重新分配元素（JDK 1.8 优化）
    // 不用重新 hash，只需要 hash & oldCap 判断新位置
    // 要么在原位置，要么在原位置 + oldCap
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;  // 单节点直接放
            else {
                // 链表/红黑树拆分到两个位置
                // ...（省略详细代码）
            }
        }
    }
​
    table = newTab;
    threshold = newThr;
    return newTab;
}

💡 扩容优化：JDK 1.8 不重新计算 hash，而是通过 hash & oldCap 判断元素在新数组的位置，要么原位，要么偏移 oldCap，效率翻倍。

红黑树转换

条件	动作
链表长度 >= 8 且 数组长度 >= 64	链表 → 红黑树
链表长度 >= 8 但 数组长度 < 64	先扩容，不转树
红黑树节点数 <= 6	红黑树 → 链表

为什么阈值是 8？

泊松分布计算：在负载因子 0.75 的情况下，一个桶中链表长度达到 8 的概率约为 0.00000006（千万分之六）。超过 8 的概率更低，所以转红黑树是极少数情况下的优化。

/**
 * 链表转红黑树
 * 前提：tab.length >= 64，否则只是扩容
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
​
    // 数组太小先扩容，不急着转树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 链表 → 红黑树
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

get 流程

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
​
/**
 * get 流程：
 * 1. 计算 hash
 * 2. 定位数组下标
 * 3. 如果第一个节点匹配 → 返回
 * 4. 如果是红黑树 → 树查找 O(logN)
 * 5. 如果是链表 → 遍历查找 O(N)
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
​
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
​
        // 第一个节点匹配
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
​
        if ((e = first.next) != null) {
            // 红黑树查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
​
            // 链表遍历
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

面试高频问题

Q: HashMap 和 HashTable 的区别？

A:

对比项	HashMap	HashTable
线程安全	❌ 不安全	✅ synchronized
null 键值	✅ 允许 1 个 null key	❌ 不允许
初始容量	16	11
扩容方式	×2	×2 + 1
推荐	✅ 单线程/配合 ConcurrentHashMap	❌ 已过时

Q: 为什么 HashMap 线程不安全？

A: JDK 1.7 头插法导致并发扩容死循环。JDK 1.8 虽然改为尾插法，但 put 操作本身不是原子的，并发仍会丢数据。多线程用 ConcurrentHashMap。

Q: 负载因子为什么是 0.75？

A: 时间和空间的折中。太小（如 0.5）→ 浪费空间；太大（如 1.0）→ 冲突增多，查询变慢。0.75 是经过大量测试得出的最优值。

Q: 容量为什么建议设为 2 的幂？

A: hash & (n-1) 等价于 hash % n，但位运算更快。如果不是 2 的幂，hash 分布不均匀，冲突增多。

Q: HashMap 的 key 可以是自定义对象吗？

A: 可以，但必须同时重写 hashCode() 和 equals()。否则两个"相同"的对象会被当作不同的 key。

总结

• 数据结构：数组 + 链表 + 红黑树（JDK 1.8）

• put 流程：hash → 定位 → 空则插入 → 非空则判断 key/树/链表 → 扩容

• 扩容：容量翻倍，元素要么原位要么偏移 oldCap

• 红黑树：链表 >= 8 且数组 >= 64 时转换，概率极低

• 线程不安全：多线程用 ConcurrentHashMap

• 面试关键：能手写 put 流程 + 说清扩容机制 = 稳了

• 实战建议：预估元素数量，提前指定初始容量（如 new HashMap<>(1000)），避免频繁扩容

参考

• JDK 1.8 HashMap 源码

• Java 官方文档 - HashMap