【Java集合 | 第三篇】HashMap详解

雨落倾城夜未眠丶

2910人浏览 · 2026-01-29 20:13:27

雨落倾城夜未眠丶 · 2026-01-29 20:13:27 发布

Map

HashMap和Hashtable区别

线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果要保证线程安全的话使用 ConcurrentHashMap）；
效率：因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同：

① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。

② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间。Hashtable 没有这样的机制。
哈希函数的实现：HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 Hashtable 直接使用键的 hashCode() 值。

HashMap和TreeMap区别

底层与性能：HashMap 基于哈希表，平均 O(1) 性能；TreeMap 基于红黑树，稳定 O(logn) 性能；
有序性：HashMap 无序，TreeMap 可按 key 自然排序 / 自定义排序；
键的限制：HashMap 允许 null 键，需重写 hashCode/equals；TreeMap 不允许 null 键，需实现 Comparable 或指定 Comparator；

HashSet 检查重复的流程

同HashMap

步骤 1：计算哈希值（hashCode）

首先调用元素 e 的 hashCode() 方法，得到该元素的哈希值；
HashMap 会基于这个哈希值计算出该元素在哈希表中的「桶位置」（数组下标）。

步骤 2：equals 方法校验（解决哈希冲突）

找到桶位置后，会遍历该桶下的链表 / 红黑树节点，依次调用节点元素的 equals(e) 方法：
- 若存在任意一个节点的 equals(e) 返回 true：说明元素重复，add() 方法返回 false，不插入新元素；
- 若所有节点的 equals(e) 都返回 false：说明元素不重复，将该元素作为新节点插入桶中，add() 方法返回 true。

HashMap的底层实现

JDK 7：数组 + 链表（拉链法解决哈希冲突）；

JDK 8：数组 + 链表 + 红黑树（链表长度≥8 且数组容量≥64 时，链表转红黑树，优化哈希冲突严重时的性能）。

桶的概念：

概念	本质	类比（通俗理解）
桶（bucket）	HashEntry 数组的一个下标位置	HashMap/ConcurrentHashMap 里的 “桶” 是数组的一个 “格子”，比如数组 [0]、数组 [1] 都是一个桶
Entry	链表节点	桶里装的 “东西”，一个桶里可以装多个Entry（哈希冲突时形成链表）

HashMap 的桶数组 = 一排储物柜（每个储物柜是一个「桶」）；
HashEntry = 储物柜里的「盒子」（一个储物柜里可以放多个盒子，对应一个桶里有多个 HashEntry 节点）；

HashMap的Put流程

计算数组索引：根据待添加键（key）的哈希码，结合 HashMap 哈希扰动规则（高 16 位与低 16 位异或）计算最终哈希值，再通过 (数组长度 - 1) & 哈希值 确定该键值对在底层数组中的桶位置（索引）。
检查桶位置是否为空：
1. 若桶位置为空：直接创建新节点（JDK7 为 Entry，JDK8 为 Node）存储键值对，存入该桶位置；同时将 HashMap 的修改计数器（modCount）加 1（用于 fail-fast 机制检测并发修改）。
桶位置非空时，检查首个节点是否匹配：
1. 先对比哈希值（哈希值不同，一定不是同一个键），再通过 == || equals() 最终确认是否是同一个键（==比较地址，equals比较内容）；
2. 若一样（即键重复）：直接用新值替换该节点的旧值，完成更新操作。
遍历桶内链表 / 红黑树查找重复键：
1. 若首个节点不匹配，判断桶内数据结构：
  - 链表结构：从链表头部开始，逐个对比节点的哈希值 + == ||equals()方法；找到重复键则替换值，未找到则将新节点尾插法（JDK8）添加到链表尾部（注：JDK7 为头插法）；
  - 红黑树结构：在红黑树中基于哈希值和 == || equals() 查找节点；找到重复键则替换值，未找到则将新节点插入红黑树并维持红黑树的自平衡。
链表转红黑树校验：
1. 若新增节点后链表长度达到阈值（默认 8），且 HashMap 数组长度≥64：将该链表转换为红黑树，优化后续查询性能；若数组长度 < 64，仅触发扩容而非树化。
扩容阈值校验：
1. 计算当前 HashMap 实际元素数（size）与数组长度的比值，若超过负载因子阈值（默认 0.75）：触发扩容操作。
执行扩容：
1. 创建一个容量为原数组 2 倍的新数组；
2. 将旧数组中所有节点重新计算哈希值，分配到新数组的对应桶位置；
3. 更新 HashMap 的底层数组引用为新数组，并同步更新扩容阈值（新数组容量 × 负载因子）。
完成添加：若为新增节点（无重复键），返回 null；若为更新操作（替换旧值），返回被替换的旧值。

HashMap的Get流程

计算数组索引：根据待查询键（key）的哈希码，结合 HashMap 哈希扰动规则（高 16 位与低 16 位异或）计算最终哈希值，再通过 (数组长度 - 1) & 哈希值 确定该键在底层数组中的桶位置（索引）；若 key 为 null，哈希值固定为 0，直接定位到数组索引 0 的位置。
检查桶位置是否为空：
1. 若桶位置为空（无任何节点）：直接返回 null，表示未找到该键对应的键值对。
桶位置非空时，检查首个节点是否匹配：
1. 对比首个节点的哈希值与待查询键的哈希值，且通过 == 或 equals() 方法校验键是否相同；
2. 若匹配：直接返回该节点的 value，完成查询操作。
遍历桶内链表 / 红黑树查找匹配键：
1. 若首个节点不匹配，判断桶内数据结构：
  - 链表结构：从链表头部开始，逐个对比节点的哈希值 + equals() 方法；找到匹配键则返回对应 value，遍历至链表尾部仍未找到则返回 null；
  - 红黑树结构：在红黑树中基于哈希值和 equals() 查找节点；找到匹配键则返回对应 value，未找到则返回 null。
完成查询：最终返回匹配节点的 value（找到时）或 null（未找到时）；整个过程无修改操作，不会更新 modCount，也不会触发扩容 / 树化。

HashMap长度是2的幂次方原因

原因 1：保证 哈希值 & (数组长度 - 1) 等价于 哈希值 % 数组长度，使用位运算效率更高

取模运算（%）是算术运算，底层实现复杂，效率低于位运算（&）；
只有当「数组长度是 2 的幂次方」时，(数组长度-1) & 哈希值 才等价于 哈希值 % 数组长度。

原因 2：让 (数组长度 - 1) 的二进制全为 1，保证哈希值的低位充分参与运算，减少哈希冲突

(数组长度-1) & 哈希值 会「保留哈希值的低 N 位」
哈希值的每一位都能参与索引计算，而非只用到某几位 —— 能让不同哈希值的 key 映射到不同桶位置，减少哈希冲突。

原因 3：扩容时简化节点迁移逻辑（JDK8 优化）

HashMap 扩容时，数组容量翻倍（依然是 2 的幂），此时旧数组中的节点迁移到新数组时，无需重新计算哈希值，只需判断哈希值的「某一位」即可确定新位置：

总结：

效率优化：2 的幂次方让 (长度-1) & 哈希值 等价于取模运算，位运算比取模更快；

减少冲突：长度-1 的二进制全 1，让哈希值的低位充分参与运算，key 分布更均匀；

扩容高效：扩容时无需重新计算哈希，只需判断哈希值的某一位，简化节点迁移；

HashMap扩容

两种结果

  情况 1：新索引 = 旧索引（节点留在原位置）；

  情况 2：新索引 = 旧索引 + oldCap（节点移到「原位置 + 旧容量」的新位置）。

  判断是哪种情况，只需看 key 的哈希值的「第 N 位」是 0 还是 1。N是从右向左数，由0开始算。
举例

假设Key算出的哈希值 = 0000 0000 0001 0101，转换成十进制是21。

👉 以上的规律可以看出：新索引 = 旧索引 + 旧容量= 5 + 16 = 21。
1. 容量是16时，旧索引 = 哈希值 & 15 → 0000 0000 0001 0101 & 0000 0000 0000 1111 = 0000 0000 0000 0101（十进制 5）；
2. 容量增加为32时，新索引 = 哈希值 & 31 → 0000 0000 0001 0101 & 0000 0000 0001 1111 = 0000 0000 0001 0101（十进制 21）；
总结

怎么找红色的位置：旧容量的二进制位是2的4次方，所以N=4(0开始)，哈希值从右向左数5位，第五个是1，因此符合情况2，新索引要加上旧容量16，否则保持不变。

HashMap多线程操作导致死循环问题

JDK1.7以前，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。
JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

HashMap线程不安全的原因

数据覆盖：并发 put 操作可能导致一个线程的写入被另一个线程覆盖。
无限循环：在 JDK 7 及以前的版本中，并发扩容时，由于头插法可能导致链表形成环，从而在 get 操作时引发无限循环，CPU 飙升至 100%。

HashMap常见的遍历方式

方式 1：遍历 key 集合，通过 key 获取 value

// 步骤：1. 获取key集合；2. 遍历key，通过get(key)取value
Set<String> keySet = map.keySet();
for (String key : keySet) {
    Integer value = map.get(key);
    System.out.println("key: " + key + ", value: " + value);
}

方式 2：迭代器遍历 Entry 集合（安全遍历，支持删除）

// 步骤：1. 获取Entry集合；2. 迭代器遍历Entry
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
    // 支持安全删除（不会触发ConcurrentModificationException）
    if ("Python".equals(entry.getKey())) {
        iterator.remove();
    }
}

方式 3：增强 for 循环遍历 Entry 集合（主流传统方式）

// 步骤：直接遍历entrySet，一步获取key+value
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}

方式 4：JDK8+ forEach + Lambda 表达式（极简方式）

// 一步到位，Lambda表达式简化遍历
map.forEach((key, value) -> {
    System.out.println("key: " + key + ", value: " + value);
});

方式 5：JDK8+ Stream 流遍历

// 基础遍历
map.entrySet().stream().forEach(entry -> {
    System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
});

// 进阶：过滤+遍历（比如筛选value>1的元素）
map.entrySet().stream()
   .filter(entry -> entry.getValue() > 1)
   .forEach(entry -> System.out.println("筛选后：" + entry.getKey() + "=" + entry.getValue()));

遍历方式	性能	代码简洁度	支持遍历删除	JDK 版本	适用场景
遍历 keySet + get (key)	一般	中等	不支持	所有	仅处理 key，小数据量
迭代器遍历 entrySet	优	中等	支持	所有	遍历中需删除元素
增强 for 遍历 entrySet	优	高	不支持	5+	仅遍历，不删除
forEach + Lambda	优	极高	不支持	8+	JDK8+，极简遍历
Stream 流遍历	一般	高	不支持	8+	复杂处理（过滤、排序等）