播面

Java中的HashMap是开发中最常用的集合类之一，基于哈希表的 Map 接口实现。要彻底理解 HashMap 的原理，我们需要从 底层数据结构、核心参数、工作原理（Put/Get）、扩容机制、JDK 1.7 与 1.8 的区别 等几个维度来进行剖析。

一、 底层数据结构 (JDK 1.8)

在 JDK 1.8 中，HashMap 的底层结构是：数组 + 链表 + 红黑树。

1. 数组（Array）：
   • 默认类型是 Node<K,V>[]，是 HashMap 的主体（被称为哈希桶/bucket）。
   • 数组的下标是通过 Key 的 Hash 值计算出来的，查询时间复杂度为 $O(1)$。
2. 链表（Linked List）：
   • 用于解决哈希冲突（Hash Collision）。当不同的 Key 计算出相同的数组下标时，这些键值对会以链表的形式存储。
   • 链表的查询时间复杂度为 $O(n)$。
3. 红黑树（Red-Black Tree）：
   • 当链表过长时，查询效率会急剧下降。
   • 树化阈值：当链表长度大于 8 且 数组容量大于等于 64 时，链表会转化为红黑树。
   • 红黑树的查询时间复杂度为 $O(\log n)$，极大地提高了在高冲突情况下的性能。

二、 核心参数

HashMap 有几个决定其性能的关键参数：

• initialCapacity（初始容量）：默认是 16。容量必须是 2 的幂次方（原因见下文）。
• loadFactor（负载因子）：默认是 0.75。它是对空间和时间效率的一个平衡。
  • 设得太大（如 1.0），空间利用率高，但哈希冲突会增加，查询效率降低。
  • 设得太小（如 0.5），冲突少，查询快，但频繁扩容，空间浪费严重。
• threshold（扩容阈值）：threshold = capacity * loadFactor。当 HashMap 中的元素个数超过这个值时，就会触发扩容。例如：默认情况下 $16 \times 0.75 = 12$。

三、 核心工作原理

1. 确定哈希桶位置（Hash 算法）

如何把一个 Key 映射到数组的某个下标上？HashMap 经历了三步：

1. 取 hashCode：调用 Key 对象的 hashCode() 方法，得到一个 32 位的 int 值。
2. 扰动函数（Hash 扰动）：
   java

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

   作用：将 hashCode 的高 16 位与低 16 位进行异或（^）运算。这样能混合高低位的信息，即使数组容量很小，高位的信息也能参与到下标计算中，减少哈希冲突。
3. 取模运算（计算下标）：
   index = hash & (n - 1) （n 为数组长度）。
   为什么不用 % 而是用 &？ 因为位运算 & 的效率远高于模运算 %。而只有当 n 是 2 的幂次方时，hash & (n - 1) 才等价于 hash % n。这就是为什么 HashMap 的容量必须是 2 的幂。

2. PUT 方法执行流程（写数据）

当你调用 map.put(key, value) 时，内部步骤如下：

1. 检查数组：如果数组（table）为空或长度为 0，先进行初始化扩容（resize）。
2. 计算下标：根据 Key 计算出对应的数组下标 i。
3. 判断桶是否为空：
   • 若 table[i] == null，直接创建新节点放入桶中。
4. 发生冲突（桶中已有数据）：
   • Key 相同：判断首个节点的 Key 是否与待插入的 Key 相同（通过 equals 和 hash）。若相同，直接覆盖其 value。
   • 红黑树节点：如果首个节点是 TreeNode，说明已经树化，调用 putTreeVal 将节点插入红黑树。
   • 普通链表节点：遍历链表：
     • 如果在遍历过程中发现相同的 Key，直接覆盖 value。
     • 若遍历到链表尾部也没找到相同的 Key，则在尾部插入新节点（尾插法）。
     • 判断是否树化：插入后，如果链表长度达到 8，会触发 treeifyBin 方法。该方法会先判断数组长度是否达到 64，若没达到则先扩容；若达到了，则将链表转为红黑树。
5. 扩容检查：插入成功后，如果 size 超过了 threshold，调用 resize() 进行扩容。

3. GET 方法执行流程（读数据）

当你调用 map.get(key) 时：

1. 计算 Key 的 hash 值，定位到对应的数组下标。
2. 检查桶中的第一个节点：
   • 如果第一个节点的 Key 刚好匹配，直接返回该节点的值。
3. 如果第一个节点不匹配，且存在后续节点：
   • 如果是 TreeNode，在红黑树中进行 $O(\log n)$ 的检索。
   • 如果是链表，遍历链表进行 $O(n)$ 的 equals 比较，直到找到匹配的 Key，找不到则返回 null。

四、 扩容机制 (Resize)

当元素个数超过扩容阈值时，HashMap 会进行扩容。

1. 容量翻倍：新容量 = 旧容量 $\times$ 2。
2. 创建新数组：创建一个两倍大小的新数组。
3. 数据迁移（Rehash）：将老数组中的所有节点迁移到新数组。
   • JDK 1.8 的优化（高低位链表）：
     在 JDK 1.8 中，不需要重新计算每个 Key 的 hash 值。因为数组长度是 2 的幂次方，扩容后，元素的新位置要么在原位置，要么在原位置 + 旧数组容量的位置。
     • 通过 (e.hash & oldCap) == 0 来判断：
       • 如果结果为 0，说明该元素在扩容后的位置保持不变（低位链表 lo）。
       • 如果结果不为 0，说明该元素移动到 原索引 + oldCap 的位置（高位链表 hi）。
     • 这种设计避免了重新计算 hash，且由于高低位分流，迁移后的链表长度通常会减半。

五、 JDK 1.7 与 JDK 1.8 的区别 (面试必问)

六、 线程安全性

HashMap 是非线程安全的。
在多线程环境下使用 HashMap 可能会导致：

1. 数据丢失/覆盖：多个线程同时 put 并在相同位置发生哈希冲突，可能导致其中一个线程的数据被覆盖。
2. 脏读：一个线程在扩容，另一个线程在读取，可能会读到 null 或旧值。

解决方案：

• 在多线程环境下，请使用 ConcurrentHashMap（推荐，采用分段锁/CAS+synchronized，性能高）。
• 或者使用 Collections.synchronizedMap(new HashMap())（性能较差，使用全局锁）。