1. 从“键值对”到“数组+链表/红黑树”：HashMap的设计哲学

如果你写过Java，或者用过任何现代编程语言，那么HashMap对你来说一定不陌生。它就像一个超级高效的“字典”或“电话本”，给你一个名字（Key），你就能瞬间找到对应的电话号码（Value）。这种“瞬间”查找的能力，是HashMap最迷人的地方。但你是否想过，这个看似简单的“键值对”容器，底层是如何做到如此高效的？为什么我们常说HashMap的查询时间复杂度是O(1)？当数据量变大时，它又是如何保持性能的？今天，我们就抛开那些枯燥的API文档，从一个Java老兵的视角，深入HashMap的“五脏六腑”，看看它到底是怎么工作的。

HashMap的核心目标只有一个：用最快的速度，通过一个不重复的键（Key）找到对应的值（Value）。为了实现这个目标，它巧妙地结合了数组、链表和红黑树这三种数据结构。数组提供了O(1)的随机访问能力，这是高速查询的基石；链表解决了数组下标冲突的问题；而红黑树则是在链表过长时，用来挽救性能的“终极武器”。理解这三者的协同工作，是理解HashMap底层原理的关键。接下来，我们将从最基础的哈希函数开始，一步步拆解这个经典容器的实现细节。

2. 哈希函数与数组索引定位：高速访问的起点

当我们调用 map.put(“张三”, “13800138000”) 时，HashMap要做的第一件事，就是决定把这个键值对放在内部数组的哪个位置上。这个过程，就是“哈希”。

2.1 哈希码的计算与扰动

在Java中，每个对象都有一个 hashCode() 方法。对于字符串“张三”，它会计算出一个int类型的哈希码。但是，直接使用这个哈希码是不行的。首先， hashCode() 方法返回的是一个32位的整数，范围从-2^31到2^31-1，而我们内部的数组（在HashMap中称为 table ）长度通常远小于这个范围（比如默认长度16）。其次，如果直接使用，一些实现不佳的 hashCode() 方法可能导致高位的变化无法影响到最终的索引值，从而增加哈希冲突的概率。

因此，HashMap引入了“扰动函数”。在JDK 8的实现中，这个函数非常简洁而精妙：

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

这段代码做了什么呢？它获取了key的原始哈希码 h ，然后让 h 与 h 无符号右移16位后的结果进行 异或（^） 操作。右移16位，相当于把高16位移动到了低16位。异或操作能保证高16位和低16位的特征都被混合起来。这样做的核心目的是 让哈希码的高位特征也能参与到后续的索引计算中 ，从而让哈希值分布得更均匀，减少后续的哈希冲突。你可以把它理解为一种“搅拌”操作，让原材料混合得更充分。

注意 ：这里有一个关键点，HashMap允许键（Key）为 null ，并且规定 null 的哈希值为0，它会被放置在数组的第一个位置（如果该位置没有冲突的话）。

2.2 索引的最终计算

得到扰动后的哈希值 hash 后，如何映射到具体的数组下标呢？HashMap的数组长度 n 总是2的幂（如16, 32, 64…）。它使用了一个非常高效的操作：

index = (n - 1) & hash

这里 & 是按位与操作。因为 n 是2的幂，所以 n-1 的二进制形式就是一串连续的1（例如，16-1=15，二进制是 1111 ）。 (n-1) & hash 这个操作，本质上就是取哈希值 hash 的低几位。这相当于一个高效的取模运算（ hash % n ），但位运算的速度远快于取模运算。

为什么数组长度必须是2的幂？

1. 计算高效 ：如上所述，用 (n-1) & hash 代替 hash % n ，位运算效率极高。
2. 分布均匀 ：当 n 是2的幂时， n-1 的二进制低位全是1，这使得 & 操作的结果能均匀地利用哈希值的每一位，减少冲突。如果 n 不是2的幂，比如是10，那么 n-1 的二进制是 1001 ，中间有0，会导致某些数组位置永远无法被映射到（例如，哈希值第二位是1的位置永远无法映射到），造成数组空间浪费和冲突加剧。

一个简单的例子 ：假设 hash(“张三”) 扰动后是 1010 1101 0011 0101 （仅为示意），数组长度 n=16 ， n-1=15 （二进制 1111 ）。 计算索引： (1111) & (1010 1101 0011 0101) = 0101 （二进制），即十进制5。所以键值对 <“张三”, “138…”> 就会被尝试放在数组下标为5的位置。

3. 哈希冲突的解决：链表与红黑树的演进

理想情况下，每个不同的Key都计算出唯一的索引，直接放入数组对应位置。但现实是骨感的，不同的Key完全可能计算出相同的索引，这就是 哈希冲突 。比如，“张三”和“李四”经过哈希和取模后，都指向了数组下标5。HashMap解决冲突的方法，经历了从单纯链表到“链表+红黑树”的演进。

3.1 链表拉链法：最直接的解决方案

在JDK 8之前，HashMap处理冲突只有一种方式： 链表拉链法 。数组的每个位置不再只存储一个元素，而是存储一个链表的头节点。当发生冲突时，新的键值对会以链表节点的形式，插入到对应位置链表的 头部 （头插法）。这种方式实现简单，在数据量不大、冲突不严重时，效率尚可。

但是，链表拉链法有一个致命的弱点：如果某个数组下标位置发生的冲突非常严重，链表变得非常长（例如，在极端情况下，所有数据都哈希到同一个位置），那么查询时就需要遍历整个链表，时间复杂度退化为O(n)，HashMap的高性能优势将荡然无存。在JDK 7及以前，这甚至是导致拒绝服务攻击（HashDoS）的一个潜在漏洞，攻击者可以精心构造大量哈希冲突的Key，使HashMap的性能急剧下降。

3.2 红黑树的引入：性能的守护者

为了解决长链表导致的性能退化问题，JDK 8对HashMap的实现做了重大优化：引入了 红黑树 。红黑树是一种自平衡的二叉查找树，它能保证在最坏情况下，基本的动态集合操作（查找、插入、删除）的时间复杂度为O(log n)，这远比O(n)的链表要好。

链表何时会转为红黑树？ HashMap设定了两个关键的阈值：

1. TREEIFY_THRESHOLD ：值为8。当某个数组位置（桶）中的链表长度超过8时，HashMap会判断是否要将这个链表转换为红黑树。
2. MIN_TREEIFY_CAPACITY ：值为64。链表转红黑树还有一个前提条件：当前HashMap的数组总长度（容量）必须达到64。如果容量小于64，即使链表长度超过8，HashMap也会选择先进行 数组扩容 （ resize ），试图通过扩大数组分散元素来缩短链表长度，而不是立即树化。因为在小容量下，扩容的收益可能比树化更高。

红黑树何时会退化为链表？ 同样，为了节省空间，当红黑树中的节点数由于删除操作而减少到小于等于6（ UNTREEIFY_THRESHOLD ）时，红黑树会退化为链表。

为什么阈值是8和6？ 这是一个基于统计学概率的设计。在理想的随机哈希情况下，一个桶中链表长度达到8的概率已经微乎其微（泊松分布下小于千万分之一）。因此，在绝大多数正常使用的场景中，我们根本不会遇到红黑树。这个设计是在极端情况（哈希碰撞攻击或糟糕的哈希函数）下的性能保障和正常情况下的空间开销之间取得的一个完美平衡。而退化的阈值设为6（小于8），是为了避免在节点数在8附近频繁地树化和退化，造成不必要的性能抖动。

3.3 插入流程详解：putVal()的核心逻辑

理解了数据结构，我们再来看最核心的 put 方法（内部是 putVal ）的详细步骤，这能帮你把前面所有知识点串联起来：

1. 判断表是否为空 ：如果内部数组 table 为空或者长度为0，则先调用 resize() 方法进行初始化扩容。
2. 计算索引 ：通过 (n-1) & hash 计算键值对应放入的数组索引 i 。
3. 检查首节点 ：
   • 如果 table[i] 位置为空，直接新建一个普通链表节点（ Node ）放进去，插入完成。
   • 如果 table[i] 位置不为空，则说明发生了哈希冲突，进入下一步。
4. 处理冲突 ：
   • 情况A：首节点Key匹配 。检查 table[i] 处节点的Key是否与待插入Key相同（通过 equals 方法判断）。如果相同，则找到了旧节点，准备覆盖其Value。
   • 情况B：首节点是树节点 。如果 table[i] 处的节点是 TreeNode （红黑树节点），则调用红黑树的插入方法 putTreeVal 。
   • 情况C：遍历链表 。否则，开始遍历该位置的链表。在遍历过程中：
     • 如果找到Key相同的节点，则标记为旧节点。
     • 如果遍历到链表尾部仍未找到，则在尾部插入新节点。插入后，立即检查链表长度是否达到 TREEIFY_THRESHOLD （8）。如果达到且数组总容量 >= MIN_TREEIFY_CAPACITY （64），则调用 treeifyBin 方法将整个链表转换为红黑树。
5. 处理覆盖 ：如果步骤3或4中找到了已存在的Key（旧节点），则用新Value替换旧Value，并返回旧Value。
6. 结构修改与扩容检查 ：这是一个新插入的节点，因此增加修改次数 modCount 和元素总数 size 。然后判断 size 是否超过了 容量 * 负载因子 （默认 容量*0.75 ）。如果超过，则调用 resize() 方法进行扩容。

这个流程清晰地展示了HashMap如何根据不同的情况，在数组、链表、红黑树三者之间进行选择和转换。

4. 动态扩容机制：resize()的智慧

负载因子（Load Factor）和扩容（Resize）是HashMap调节性能和空间利用率的核心杠杆。默认负载因子是0.75，这是一个经验值。

为什么是0.75？ 这是一个在时间和空间成本上的折衷。负载因子越高（比如0.9），数组的利用率就越高，空间开销越小，但哈希冲突的概率会显著增加，导致链表变长，查询性能下降。负载因子越低（比如0.5），冲突减少，查询性能好，但会有大量的数组空间被浪费，空间利用率低。0.75这个值，在大量实验统计下，被认为是能在时间和空间上取得较好平衡的点。

扩容触发条件 ：当HashMap中存储的键值对数量（ size ）超过 容量（capacity） * 负载因子（loadFactor） 时，就会触发扩容。例如，默认初始容量16，负载因子0.75，那么当放入第13个元素（16*0.75=12）时，就会触发扩容。

扩容做了什么？ resize() 方法主要做两件大事：

1. 创建新数组 ：将数组容量扩大为原来的2倍（因为容量必须是2的幂，所以是2倍扩容，比如16->32）。
2. 数据迁移（重哈希） ：遍历旧数组中的每一个桶（可能是空、单个节点、链表或红黑树），将里面的所有节点重新计算索引，并放置到新数组的对应位置。

JDK 8的优化：高效的数据迁移 在JDK 8的扩容中，有一个非常巧妙的优化。由于扩容是2倍，新数组的容量 newCap 是旧数组容量 oldCap 的2倍。那么新索引的计算公式是 (newCap-1) & hash 。观察二进制可以发现， newCap-1 相比 oldCap-1 ，只是在高位多了一个1。

关键结论来了：一个节点在新数组中的位置， 要么和原位置相同，要么是原位置加上旧容量（oldCap） 。具体是哪种情况，取决于该节点哈希值在 oldCap 对应二进制位上的值是0还是1。

示例：
旧容量 oldCap = 16 (二进制 10000)
旧索引计算：hash & (16-1) = hash & 1111
新容量 newCap = 32 (二进制 100000)
新索引计算：hash & (32-1) = hash & 11111

对比新旧索引，多出来的一位就是 hash & 10000（即 oldCap）。
如果 (hash & oldCap) == 0， 则该节点新索引 = 原索引。
如果 (hash & oldCap) != 0， 则该节点新索引 = 原索引 + oldCap。

基于这个原理，JDK 8在迁移链表时，不需要像JDK 7那样对每个节点重新计算哈希，而是可以直接将原链表拆分成两个子链表：一个保持原索引（低位链表），另一个索引为原索引+oldCap（高位链表）。然后将这两个链表直接挂到新数组的对应位置。这个过程只需要遍历一次链表，效率非常高。对于红黑树，也有类似的优化拆分逻辑。

5. 线程安全问题与ConcurrentHashMap的启示

HashMap是一个非线程安全的容器。这在它的源码注释里写得清清楚楚。在多线程环境下使用HashMap，最常见的问题就是 数据不一致 和 死循环 （在JDK 7的头插法扩容时尤其突出）。

为什么线程不安全？ 我们回顾一下 putVal 和 resize 的流程，其中包含了多个“检查-然后-操作”的步骤，例如检查桶是否为空、检查链表长度、修改 size 等。这些操作在多线程环境下都不是原子的。两个线程可能同时检查到同一个桶为空，然后都认为自己可以插入，导致其中一个线程的写入被覆盖。更严重的是在JDK 7的扩容过程中，由于采用头插法反转链表，在多线程同时扩容时可能产生循环链表，导致后续的 get 操作陷入死循环。JDK 8虽然通过尾插法解决了死循环问题，但数据覆盖等不一致性问题依然存在。

解决方案：ConcurrentHashMap 这也就是为什么在并发编程中，我们几乎总是使用 ConcurrentHashMap 来代替 HashMap 。 ConcurrentHashMap 在JDK 7中采用分段锁（Segment）机制，而在JDK 8中则做了更彻底的优化，使用了** synchronized + CAS（Compare-And-Swap）** 的方式。

在JDK 8的ConcurrentHashMap中：

• 对于数组元素的插入，它使用 synchronized 锁住链表的头节点（或红黑树的根节点），而不是锁住整个Map。这大大提高了并发粒度。
• 对于 size 等变量的更新，广泛使用了CAS操作，这是一种无锁的乐观并发控制，性能更高。
• 其 get 操作通常完全不需要加锁，因为 Node 的 val 和 next 都被 volatile 修饰，保证了可见性。

理解HashMap的线程不安全性和ConcurrentHashMap的解决方案，能让你在设计和面试中清晰地知道何时该用谁。简单来说：单线程用HashMap，追求极致性能；多线程并发场景，无脑选择ConcurrentHashMap。

6. 关键参数与性能调优实践

在实际使用中，我们虽然不常去修改HashMap的内部参数，但理解它们对于写出高性能的代码和进行问题排查至关重要。

1. 初始容量（initialCapacity） 这是创建HashMap时内部数组的初始大小。默认是16。如果你能提前预估要存储的键值对数量，最好通过构造函数 new HashMap<>(expectedSize) 来指定一个初始容量。这可以避免或减少后续扩容的次数。一个简单的估算公式是： initialCapacity = (expectedSize / loadFactor) + 1 。例如，预计要存100个元素，负载因子0.75，那么 100/0.75≈133 ，取下一个2的幂就是256。指定 new HashMap<>(256) 会比使用默认16然后多次扩容高效得多。

2. 负载因子（loadFactor） 除非有非常特殊的场景，否则不建议修改默认的0.75。降低负载因子（如0.5）会提升查询速度但浪费内存；提高负载因子（如0.9）会节约内存但增加查询时间。通常默认值是最佳选择。

3. 键（Key）对象的设计 这是影响HashMap性能最容易被忽视，也最关键的一点。HashMap的性能严重依赖于键的 hashCode() 和 equals() 方法。

• hashCode() ：必须保证对同一个对象返回相同的值，同时尽可能让不同的对象返回不同的值（分布均匀）。一个好的哈希函数能极大减少冲突。对于自定义类，推荐使用 Objects.hash(field1, field2, ...) 来计算。
• equals() ：必须与 hashCode() 保持一致，即如果两个对象 equals() 返回 true ，那么它们的 hashCode() 必须相等。反之， hashCode() 相等的两个对象， equals() 不一定为 true （这就是哈希冲突）。

一个常见的坑 ：使用可变对象作为Key。例如，用一个 ArrayList 作为Key，放入HashMap后，又修改了这个 ArrayList 的内容。这会导致其 hashCode() 改变，后续再也无法通过 get() 方法正确找到它（因为计算出的索引变了），但它又确实存在于Map的某个错误位置，造成内存泄漏和逻辑错误。因此， 最佳实践是使用不可变对象（如String、Integer）或确保作为Key的对象在其作为Key的生命周期内不会改变其用于计算 hashCode 和 equals 的字段 。

7. 源码层面的精妙设计赏析

最后，我们跳出使用层面，看看HashMap源码中一些体现设计智慧的地方。

1. 容量总是2的幂 我们前面已经分析了其好处（高效取模、分布均匀）。构造函数中，如果你传入一个不是2的幂的初始容量，比如 new HashMap<>(10) ，HashMap会通过 tableSizeFor 方法将其转换为大于等于该值的最小的2的幂（16）。这个方法同样使用了精妙的位操作：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这个方法的作用是将 cap 最高位1之后的所有位都置为1，然后加1，从而得到2的幂。例如， cap=10 ， n=9 (1001)，经过一系列右移和或操作后，最终得到 15 (1111)，再加1得到 16 。

2. 树化与退化的阈值 hysteresis 设置树化阈值8和退化阈值6，中间有个差值2，这是一种“迟滞”（hysteresis）设计。目的是防止在节点数在阈值边界频繁增删时，发生链表和红黑树之间频繁且昂贵的转换。比如，一个桶的节点数在7、8、9之间波动，如果没有迟滞，可能会频繁触发树化和退化，得不偿失。

3. 红黑树节点的特殊处理 当链表转为红黑树时， TreeNode 节点不仅维护了红黑树结构（父、左、右指针），还通过 prev 和 next 指针维护了原链表的顺序。这样在退化回链表时，或者进行遍历时，可以保持与链表一致的顺序（插入顺序或访问顺序，取决于Map的类型）。这种设计体现了在复杂性和功能性之间的权衡。

HashMap的源码是Java集合框架中最值得品读的经典之一。它用相对简洁的代码，实现了高效、健壮的数据结构，并且在JDK的迭代中不断优化。理解它的原理，不仅能让你在面试中游刃有余，更能让你在编写高性能、高可靠性的代码时，做出最合适的选择。下次当你再写下 Map<String, Object> map = new HashMap<>() 时，希望你的脑海里能清晰地浮现出它背后那个精妙而高效的世界。