基于本文回答

播面 播面

文图音视，全方位拆解八股文
0
评论
请从左侧选择一个分类

java hashmap原理

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)O(1)。
  2. 链表（Linked List）：
    • 用于解决哈希冲突（Hash Collision）。当不同的 Key 计算出相同的数组下标时，这些键值对会以链表的形式存储。
    • 链表的查询时间复杂度为 O(n)O(n)。
  3. 红黑树（Red-Black Tree）：
    • 当链表过长时，查询效率会急剧下降。
    • 树化阈值：当链表长度大于 8 且 数组容量大于等于 64 时，链表会转化为红黑树。
    • 红黑树的查询时间复杂度为 O(log⁡n)O(\log n)，极大地提高了在高冲突情况下的性能。

二、 核心参数

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

  • initialCapacity（初始容量）：默认是 16。容量必须是 2 的幂次方（原因见下文）。
  • loadFactor（负载因子）：默认是 0.75。它是对空间和时间效率的一个平衡。
    • 设得太大（如 1.0），空间利用率高，但哈希冲突会增加，查询效率降低。
    • 设得太小（如 0.5），冲突少，查询快，但频繁扩容，空间浪费严重。
  • threshold（扩容阈值）：threshold = capacity * loadFactor。当 HashMap 中的元素个数超过这个值时，就会触发扩容。例如：默认情况下 16×0.75=1216 \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(\log n) 的检索。
    • 如果是链表，遍历链表进行 O(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 的区别 (面试必问)

特性 JDK 1.7 JDK 1.8
底层数据结构 数组 + 链表 数组 + 链表 + 红黑树
链表插入方式 头插法（在多线程扩容时会导致死循环/环形链表） 尾插法（避免了死循环问题）
扩容迁移方式 每个元素重新计算 hash 值并排序迁移 通过高低位指针（e.hash & oldCap）直接分组迁移，效率高
Null Key 存储 专门的 putForNullKey 方法 统一计算 hash，null 的 hash 值为 0，固定在数组 0 号位置

六、 线程安全性

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

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

解决方案：

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