JDK1.8 HashMap底层原理图解与源码逐行拆解：面试必备核心

HashMap是Java中非常重要的一个集合，其底层原理在各种面试中被频繁考察。

HashMap也叫哈希表，主要用于存储键值对，能够实现O(1)时间复杂度的快速查找。无论是日常的算法练习还是项目开发，它都应用广泛。例如，力扣上的经典题目“两数之和”就可以利用哈希表进行高效优化。

如果只是停留在使用层面，那么它非常简单，无非就是调用 put(k, v) 存放元素，使用 get(k) 获取元素。但HashMap的底层实现却相当精妙，理解其如何实现键值对的存储与查找非常有意思。阅读源码不仅能学习编程技巧，更能领会优秀函数的设计思想。如果有时间，强烈建议深入了解这部分源码，如果在面试中能展示出你对源码的理解，往往能让面试官眼前一亮。

在结合源码详细解释之前，我们先通过图解来直观地理解HashMap的 put 和 get 流程。

HashMap利用数组作为底层哈希表来存储数据，默认创建的数组长度为16。在下图中，每一个绿色小方块代表一个键值对（key-value）。

添加键值对 put 操作

HashMap的put流程可以分为以下几个步骤：

1. 首先利用“哈希函数”将key映射成一个整数值 hashKey。哈希函数本质上是一种映射规则。
2. 接着，为了确定这个键值对在数组中的存储位置，需要计算 hashKey % n（n为数组长度），这样就能在数组下标范围内找到一个具体的存储位置。
3. 创建一个键值对节点，并将其存放到计算出的位置 (hashKey % n)。
4. 结束。

以上是最理想的情况，没有发生任何冲突。但细心观察就会发现：如果两个不同的key被映射到同一个hashKey，那么计算出的存储位置肯定相同，这就产生了冲突。

没错，这就是哈希冲突，在实际应用中完全可能出现。

为了应对哈希冲突，开发者提出了多种解决方案。在Java的HashMap中，采用了链地址法（俗称拉链法）。

简单来说，当发生哈希冲突时，HashMap会将冲突的元素作为链表节点，链接到当前位置已有元素的后面。随着冲突元素增多，某个位置上的链表会越来越长，形状酷似一条拉链。

在JDK 1.7及之前的版本，新冲突元素采用头插法加入链表（即新节点成为链表头）。

为什么是头插法？
这基于程序局部性原理，即最近被访问或插入的数据，在短期内再次被访问的概率更高。将新元素放在链表头部，查找时能更快命中。
循环就是程序局部性原理的经典体现，循环体内的变量会在短时间内被反复使用。

然而，头插法在多线程环境下进行扩容时，可能导致链表出现环状结构，进而引发死循环和数据丢失问题。

因此，在JDK 1.8及之后的版本，链表改为采用尾插法加入新节点。这保证了元素在扩容前后的顺序一致性，避免了死循环，但仍然可能发生数据覆盖（例如两个线程同时判断同一槽位为空并插入数据）。所以，我们常说HashMap不是线程安全的。

Java同样提供了线程安全的键值对集合，如 HashTable 和 ConcurrentHashMap。HashTable通过对整个表进行同步锁来实现线程安全，在某些高并发场景下效率较低。而ConcurrentHashMap则使用更精细的分段锁或CAS操作来保证线程安全，性能更优。

随着某个位置冲突的元素越来越多，链表会变得很长，每次查找都需要遍历整个链表，效率会降至O(n)。

为了优化这一过程，在JDK 8及之后的版本中，当某个链表的长度 >= 8，且哈希表（数组）的容量 >= 64时，该链表会转变为红黑树。

红黑树的查找效率要高得多。链表的查找时间复杂度为O(n)，而红黑树的查找、插入、删除时间复杂度均为O(log n)。

红黑树的更多细节在此不展开，网上有大量资料可供查阅。

当某个红黑树中的节点数 <= 6 时，它会重新退化为链表。 因为在元素较少时，顺序遍历的效率已经很高，使用复杂的红黑树反而得不偿失。

为什么链表转树的阈值是8，而树转链表的阈值是6？
这主要是为了设置一个缓冲区间，防止在阈值8附近频繁发生链表与红黑树之间的转换，这种反复的结构转换会消耗性能、降低效率。

随着哈希表中放入的元素越来越多，数组的空闲位置会减少，必须进行扩容以容纳更多元素。

那么HashMap是如何扩容的呢？

HashMap在初始化时会设置一个扩容因子（Load Factor），可以由开发者指定。如果未指定，默认值为0.75。

这意味着，当哈希表中被占用的元素数量达到 容量 * 扩容因子 时（例如默认容量16 * 0.75 = 12），HashMap会自动触发扩容。每次扩容，容量都会增加一倍，例如从16变为32。

获取键值对 get 操作

get操作是通过key查找value的过程，流程如下：

1. 根据key计算哈希值。HashMap使用哈希函数将key转换为一个数字，这个数字决定了查找的起始位置。
2. 确定在数组中的具体下标。计算出哈希值后，通过与数组长度进行运算（例如 hash % 长度 或位运算等价操作）得到具体下标。
3. 在链表或红黑树中寻找元素。在指定下标的链表或红黑树中，逐个比对节点的key。如果找到则返回对应的value；如果遍历完仍未找到，则返回null。

源码拆解

HashMap初始化

首先看初始化过程，重点关注容量和扩容因子这两个参数。HashMap提供了三种构造方式：

#1 无参构造
HashMap<Key, Value> map = new HashMap<>();

#2 指定初始容量
HashMap<Key, Value> map = new HashMap<>(40);

#3 指定初始容量和扩容因子
HashMap<Key, Value> map = new HashMap<>(40, 0.8);

如果使用无参构造，默认容量为16，扩容因子为0.75。这意味着当元素数量达到 16 * 0.75 = 12 时，容量会自动扩容为原来的两倍，即32。

HashMap的put操作

这是HashMap最核心的方法。直接阅读完整源码可能有些复杂，下面我们将对其进行逐行拆解。这里先展示完整源码，供你概览。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

接下来进行逐行解析，理解起来会轻松很多。

1. 方法声明

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

参数说明：

• hash: key的哈希值。
• key: 要插入的键。
• value: 要插入的值。
• onlyIfAbsent: 如果为true，则仅当key不存在时才插入（不覆盖已存在的值）。
• evict: 如果为false，表示处于创建模式（LinkedHashMap使用）。

2. 检查并初始化数组

Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

HashMap底层使用 Node<K,V>[] table 数组存储键值对。首先检查数组 table 是否为空或长度为0。如果是，则调用 resize() 方法进行初始化，并获取初始化后的数组长度 n（即HashMap的当前容量）。

resize() 方法身兼两职：初始化数组和扩容。默认初始化长度为16，扩容策略是容量翻倍（16 -> 32 -> 64...）。你会发现数组的长度总是2的幂次方。

如果初始化HashMap时指定的容量不是2的幂次方怎么办？
HashMap会自动将其向上调整为最近的2的幂次方，例如指定40会调整为64。

为什么在put时才初始化数组？
这是一种延迟初始化（lazy initialization） 策略，只有在第一次插入元素时才创建底层数组，有助于节省内存。

3. 计算索引位置并检查是否为空

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

这行代码是定位和插入的核心：

• i = (n - 1) & hash：计算元素在数组中的下标。n是数组长度（2的幂），n-1的二进制形式是低位全1。通过与(&)操作，等价于 hash % n，但效率更高。
• 如果计算出的位置 tab[i] 为 null，说明没有发生哈希冲突，直接在此处创建一个新节点存放。

4. 处理哈希冲突（关键部分）

如果 tab[i] 不为 null，说明发生了哈希冲突，进入 else 块。

4.1 检查第一个节点是否匹配

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

p 是当前位置的第一个节点。检查该节点的key是否与要插入的key相同（先比较引用，再调用equals方法）。如果匹配，则用变量 e 记录这个节点，后续会更新它的value。

4.2 如果是红黑树节点

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

如果当前节点是树节点（TreeNode），说明此位置已经是红黑树结构。则调用红黑树的插入方法 putTreeVal。

4.3 遍历链表

else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            // 情况1：遍历到链表末尾，没找到相同的key
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            // 情况2：在链表中找到了相同的key
            break;
        p = e;
    }
}

遍历链表，存在两种结果：
情况1：遍历到链表末尾，仍未找到相同的key

• 创建新节点，并采用尾插法追加到链表末尾。
• 如果链表长度已达到或超过 TREEIFY_THRESHOLD - 1（即7，从0开始计数，第8个节点触发），则调用 treeifyBin() 尝试将链表树化。注意，在 treeifyBin() 内部还会检查数组容量是否>=64，只有满足该条件才会真正转换为红黑树。

情况2：在链表中找到了相同的key

• 变量 e 指向找到的节点。跳出循环，后续将更新这个节点的value。

5. 更新已存在的key

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue; // 返回旧值
}

如果 e != null，说明是更新操作（找到了已存在的key）。

• 保存旧值 oldValue。
• 根据 onlyIfAbsent 参数决定是否覆盖：onlyIfAbsent 为false（默认）则覆盖；为true则不覆盖（这是 putIfAbsent 方法的行为）。
• 返回被覆盖的旧值。
  注意：如果执行了这一步（更新），方法就此结束，不会增加元素总数 size。

6. 插入新节点后的处理

++modCount; // 修改次数+1，用于fail-fast机制
if (++size > threshold) // threshold = capacity * loadFactor
    resize();
afterNodeInsertion(evict);
return null; // 返回null表示是新插入

• ++modCount：记录结构修改次数，用于迭代器的快速失败（fail-fast）机制。
• 检查是否需要扩容：如果插入新节点后，元素总数 size 超过了阈值 threshold，则调用 resize() 进行扩容（容量翻倍，并重新散列部分元素）。
• 最后返回 null，表示此次操作是插入新元素，而非更新。

至此，put操作的源码分析就完成了。get操作相对简单，主要就是在链表或红黑树中进行查找，其流程在之前的图解部分已做介绍。

如果你想了解更多细节，例如链表到红黑树的具体转换逻辑、resize() 方法如何实现重新散列等，可以自行深入阅读源码。在IDE中，对HashMap变量按Ctrl+单击即可跳转到其源码定义。