HashMap Temp

HashMap 是 Java 中的一种数据结构，实现了 Map 接口，用于存储键值对（key-value pairs），允许 null 键和 null 值，非线程安全。

根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。

为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

**HashMap：**链表>8&数组大小>=64转为红黑树，如果链表>8，数组没有到达64，先扩容，等数组长度达到64在把链表树化，节点<6转为链表。插入后判断是否需要扩容，扩容因子0.75，2倍扩容，初始容量16。

底层结构

  • JDK 1.7 及以前：纯粹是 数组 + 链表。发生哈希冲突时，新元素会被放到链表的头部（头插法）。
  • JDK 1.8 及以后：变成了 数组 + 链表 + 红黑树。当链表长度超过阈值（默认为 8）并且当前数组容量达到一定值（默认为 64）时，链表会转换为红黑树，以提高极端情况下的查询效率（从 O(n) 提升到 O(log n)）。当树节点数减少到较小值（默认为 6）时，红黑树会退化成链表。
  • 桶数组（table）*：核心存储载体，每个元素称为“桶”，用于定位键值对的基础位置。数组容量（n）始终是2的幂次方**（如16、32、64...，初始默认16），这是高效计算索引的前提。**
  • 链表：当多个键计算出相同桶索引（哈希冲突）时，节点以链表形式串联在同一桶中（节点通过next指针连接），适合冲突较少的场景（节点数≤7）。
  • 红黑树：当链表长度≥8且数组容量≥64时，链表转为红黑树（TreeNode）。红黑树通过自平衡特性保证查询/插入/删除效率为O(logn)，解决长链表（O(n)）的性能问题。

关键特性

  • 允许null键值：null键的哈希值为0，固定存于索引0的桶。
  • 依赖hashCode()和equals()：自定义键必须重写这两个方法——hashCode()决定存储位置，equals()判断键是否相同，否则会导致查询/插入异常。
  • 不保证顺序：插入的顺序和遍历的顺序不一定一致。
  • 非线程安全：多线程并发修改可能导致数据覆盖（JDK 1.8）或环形链表死循环（JDK 1.7头插法），需用ConcurrentHashMap替代。
  • 树化与退化：链表≥8且容量≥64时树化；红黑树节点≤6时退化回链表（避免频繁转换开销）。
  • 性能：在理想情况下（没有哈希冲突），get 和 put 操作的时间复杂度都是 O(1)

工作原理

存数据（put 过程）

当我们调用 map.put(key, value) 时，会发生以下步骤：

  1. 计算哈希值：

    • 首先调用 key.hashCode() 方法得到原始的哈希值 h。

    • 然后，HashMap 会通过一个 扰动函数 对这个原始哈希值进行二次处理。在 JDK 1.8 中，这个处理非常简洁高效：(h = key.hashCode()) ^ (h >>> 16)。

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

    • 为什么要扰动？ 将高 16 位与低 16 位进行异或操作，目的是为了将高位的特征融入到低位中，从而增加低位的随机性，减少哈希冲突。（目的是混合哈希值的高位和低位信息，减少因高位未被利用导致的哈希冲突。）

  2. 计算数组下标：

    • 利用处理后的哈希值，与当前数组长度 n（一定是 2 的幂）进行 (n - 1) & hash 操作，得到元素在数组中的具体下标。
    • 为什么是 (n-1) & hash？ 因为当 n 是 2 的幂时，(n-1) 的二进制表示就是一串连续的 1（比如 15 的二进制是 1111）。这个操作等价于 hash % n，但位运算的效率远高于取模运算。

  3. 放入数组（桶）：

    • 如果计算出的下标位置为 null，直接创建一个新 Node 节点放进去。

    • 如果该位置不为null（发生了哈希冲突），则需要遍历该位置上的链表或红黑树：

      • 如果是链表：依次比较每个节点的key（先用hash快速判断，再用equals方法精确判断）。
        • 如果找到相同的 key，则用新的 value 覆盖旧的 value。
        • 如果没找到，则将新节点插入到链表的末尾（尾插法）。
      • 如果是红黑树：则按照红黑树的方式插入节点。

    • 插入链表后，会检查当前链表长度是否

      大于等于 8（TREEIFY_THRESHOLD）

      。如果是，则调用treeifyBin方法。

      • 在 treeifyBin 中，会再次判断当前数组容量是否大于等于 64（MIN_TREEIFY_CAPACITY）。如果是，则将链表转换为红黑树；如果不是，则优先选择扩容（resize）。

  4. 判断是否需要扩容：

    • 插入成功后，会检查当前 HashMap 中的元素总数（size）是否超过了 阈值（threshold）。阈值 = 当前数组容量（capacity） * 负载因子（loadFactor，默认 0.75）。
    • 如果超过阈值，则调用 resize() 方法进行扩容。

取数据（get 过程）

当我们调用 map.get(key) 时，过程与 put 类似：

  1. 计算 key 的哈希值（同样的扰动函数）。
  2. 通过 (n-1) & hash 计算数组下标。
  3. 定位到数组下标：
    • 如果该位置是红黑树，则在树中查找。
    • 如果该位置是链表，则遍历链表。
    • 查找时，同样先比较 hash，再使用 equals 方法比较 key。
  4. 找到则返回对应的 value，没找到则返回 null。

扩容机制（Resize）

扩容是 HashMap 性能的关键点之一。当元素数量达到阈值后，HashMap 会创建一个新的、容量是原来 2倍 的数组。

扩容步骤：

  1. 分配一个新数组（例如，从 16 扩容到 32）。

  2. 遍历旧数组中的每一个桶（链表或树）。

  3. 对于每个节点，重新计算其在新数组中的下标。由于新容量是旧容量的 2 次幂，所以节点的新位置

    要么保持不变，要么是 原位置 + 旧容量。

    • 这是因为 (新容量-1) & hash 的结果只比 (旧容量-1) & hash 多了一个高位 1。这个高位 1 是正是由旧容量的值决定的。
    • 例如，旧容量为 16 (10000)，(16-1)=15 (01111)。新容量为 32 (100000)，(32-1)=31 (11111)。节点的新位置就取决于其哈希值在第 5 位（从右向左）是 0 还是 1。如果是 0，则位置不变（原下标）；如果是 1，则新位置为 原下标 + 16。

为什么要扩容？

  • 为了减少哈希冲突。当元素越来越多，链表就会越来越长，查询效率会从 O(1) 退化为 O(n)。通过扩容，可以将元素重新分散到更多的桶中，使链表的长度变短，从而维持高效的操作性能。

关键参数

  • 初始容量（Initial Capacity）：默认是 16。创建 HashMap 时可以指定。
  • 负载因子（Load Factor）：默认是 0.75。这是一个权衡时间和空间的经验值。值越小，空间开销越大，但哈希冲突概率低，查询快；值越大，空间开销小，但哈希冲突概率高，查询慢。
  • 阈值（Threshold）：容量 * 负载因子。是触发扩容的临界点。

扩容机制

触发树化或扩容：

  • 若链表长度≥8且容量≥64：链表转红黑树；
  • 若容量<64：不树化，触发扩容（优先通过扩容拆分链表）；
  • 若元素总数超过“阈值”（容量×负载因子，默认负载因子0.75）：触发扩容。

当元素数超过阈值（或链表过长但容量不足）时，HashMap会扩容以减少冲突：

  1. 容量翻倍：新容量=原容量×2（保持2的幂次方），新阈值=新容量×负载因子。
  2. 节点重分配：遍历原数组，重新计算每个节点的新索引（基于新容量）：
  • 新索引由“新增高位”（容量翻倍多的一位二进制）决定：若高位为0，新索引=原索引；若为1，新索引=原索引+原容量。
  • 此过程会将原链表/红黑树拆分为两个子结构，分别存入新桶，避免结构过长。

使用 HashMap 时，有哪些提升性能的技巧？

提升 HashMap 性能，说白了就是两件事：少扩容、少冲突。

1）初始容量一定要给够

业务代码尽量不写 new HashMap<>()，而是 new HashMap<>((int)((size/0.75f)+1))，size 是业务上能预估的最大元素数，这样就能避免频繁的扩容操作。

Java 中 HashMap 默认初始容量是 16

2）负载因子别乱调

官方提供的默认负载因子是 0.75，是时间复杂度与空间利用率的最佳平衡。

较低的负载因子会减少冲突，提高查找效率，但会占用更多内存。较高的负载因子则会减少内存消耗，但可能增加冲突的概率，降低查找效率。

3）确保 hashCode 均匀分布

对应 key 的 hashCode() 方法生成的哈希值需均匀分布，减少哈希冲突。避免使用质量不高的哈希函数，防止大量键映射到相同的槽位上，造成性能瓶颈。

除此之外，还有个遍历场景可以提一下：优先使用 entrySet（需要 key 和 value）或 keySet（只要 key）

错误的方式如下：

for (String key : map.keySet()) {
    Object v = map.get(key); // 这里会再次 hash，一次 keySet + 一次 get
}

推荐方式：

for (Map.Entry<String, Object> entry : map.entrySet()) {
    var k = entry.getKey();
    var v = entry.getValue(); // 不需要再次 hash
}

为什么既要链表又要红黑树？

jdk1.7之前只有链表,jdk1.8的时候增加了红黑树,因为如果太长了可以将链表转换成红黑树,红黑树可以把查找从o(n)降低为o(logn)提升效率

为什么要红黑树？不要AVL树？

因为AVL树是严格平衡维护代价比较高,红黑树平衡策略相对宽松

为什么有红黑树还要链表？

因为红黑树节点是普通节点大小的2倍,能省则省

什么时候链表转换成红黑树？

当链表大于等于8且数组长度大于等于64的时候

为什么数组要大于等于 64 才转红黑树？

主要原因有以下两点：

  • 避免频繁的树化
  • 减少内存占用

当数组容量较小的时候，哈希冲突大，但是扩容后的 HashMap 自然会减少哈希冲突。如果在小数组上过早地进行链表转红黑树，可能会因为很快的扩容导致不必要的树化开销。

刚树化了没多久就扩容了，冲突就少了，此时不就白白树化了？所以设计上设置了数组大小需要大于 64 才允许链表转为红黑树，防止频繁的树化。

红黑树相比链表需要更多的内存，尤其是在节点较少的情况下，红黑树的额外指针和结构占用更大。为了节省内存，HashMap 选择只有在数组容量达到一定规模后才树化，防止红黑树在小规模数据中带来额外的内存负担。

当链表大于等于8，数组小于64的时候会怎么样？

会扩容,为什么是8,和柏松分布有关,因为红黑树占用内存大,默认负载因子为0.75,链表冲突到8点几率极低,所以不会触发.所以选择了8是时间和空间平衡

如果链表转了红黑树，还会转回来吗？

会,当树节点小于等于6的时候就会转回来,这个也是为了平衡时间和空间

为什么是6而不是8?

因为要留一些缓冲余地,避免反复横跳

说说put流程?

put流程先计算hash,选择bucket,若空的时候插入,若非空检查equals,选择替换还是插入尾部,还会根据阈值决定树化或扩容

为什么是插入到尾部?不是插入到头部?

1.7之前是头插法,如果并发可能会成环.所以,1.8改为尾插法

HashMap的扩容机制?

HashMap的默认初识容量是16,负载因子是0.75,因此默认扩容域是12,理论上插入第13个值就会扩容,扩容就是新建一个2倍大的新数组,然后把原来的数据迁移过去

为什么是2倍?

容量始终保持为2的幂,这样可以通过(n-1) & hash这个位运算,快速定位到数组下标,比直接取余运算效率高很多;

什么是负载因子？

负载因子是 HashMap 中的一个参数，用来衡量 HashMap 的满载程度，公式为： 负载因子 = 实际存储的元素数量 / 容量。

当 HashMap 中存储的元素数量超过 容量 × 负载因子 时，HashMap 会进行扩容操作，增加容量以维持性能。

为什么 Java 中 HashMap 的默认负载因子是 0.75？

HashMap 的默认负载因子为 0.75 是为了在时间复杂度和空间复杂度之间取得一个合理的平衡。负载因子为 0.75 时，避免过多扩容的同时，也保证了不会出现过多的哈希冲突，确保查找和插入操作的效率，维持良好的性能表现。

简单理解下就是设置 0.75 是因为空间和时间上的平衡。

较低的负载因子（例如 0.5）会导致 HashMap 需要频繁扩容，空间利用率就低。不过因为冲突少，查找效率就高，但是因为扩容频繁会增加 rehashing 的开销。

较高的负载因子（例如 1.0）会减少扩容次数，空间利用率高了，但会增加哈希冲突的概率，从而降低查找效率。

经过大量实践，0.75 被认为是大多数场景下比较合适的值，能够在时间和空间之间取得良好的平衡。

所以设置了 0.75。

为什么不选择 1.0 作为默认负载因子

尽管负载因子 1.0 可以减少扩容次数，提高内存利用率，但它增加了哈希冲突的可能性。冲突过多会导致桶内链表或红黑树变长，降低查找、插入和删除的效率。因此，负载因子 1.0 会使得时间复杂度劣化为 O(n)，不利于 HashMap 的高效运行。

不同场景下的负载因子调整

在某些特定场景下，可以根据业务需求调整 HashMap 的负载因子。例如：

  • 高并发读取场景：可以降低负载因子（如 0.5），以减少哈希冲突，提高读取性能。
  • 内存受限场景：可以提高负载因子（如 0.85 或更高），以减少扩容次数和内存消耗，但可能会降低写入和查询的性能。

不能抛弃链表，直接使用红黑树吗？

来看下源码的注释:

* Because TreeNodes are about twice the size of regular nodes。

因为红黑树节点的大小是普通节点大小的两倍，所以为了节省内存空间不会直接只用红黑树，只有当节点到达一定数量才会转成红黑树，这里定义的是 8。

为什么是 8 呢？这个其实 HashMap 注释上也有说，和泊松分布有关系。

简单翻译下就是在默认阈值是 0.75 的情况下，冲突节点长度为 8 的概率为 0.00000006，也就概率比较小（毕竟红黑树耗内存，且链表长度短点时遍历的还是很快的）。

这就是基于时间和空间的平衡了，红黑树占用内存大，所以节点少就不用红黑树，如果万一真的冲突很多，就用红黑树，选个参数为 8 的大小，就是为了平衡时间和空间的问题。

为什么节点小于等于 6 要从红黑树转成链表？

链表树化的节点是 8，除此之外，当树节点数小于等于 6 时候，又会从红黑树转为链表。

这个操作是为了平衡时间和空间，节点太少链表遍历也很快，没必要成红黑树，变成链表节约内存。

为什么定了 6 而不是小于等于 8 就变？

是因为要留个缓冲余地，避免反复横跳。举个例子，一个节点反复添加，从 8 变成 9 ，链表变红黑树，又删了，从 9 变成 8，又从红黑树变链表，再添加，又从链表变红黑树？

所以余一点，毕竟树化和反树化都是有开销的。

为什么 HashMap 在 Java 中扩容时采用 2 的 n 次方倍？

HashMap 采用 2 的 n 次方倍作为容量，主要是为了提高哈希值的分布均匀性和哈希计算的效率。

HashMap 通过 (n - 1) & hash 来计算元素存储的索引位置，这种位运算只有在数组容量是 2 的 n 次方时才能确保索引均匀分布。位运算的效率高于取模运算（hash % n），提高了索引计算的速度。

且当 HashMap 扩容时，通过容量为 2 的 n 次方，扩容时只需通过简单的位运算判断是否需要迁移，这减少了重新计算索引的开销，提升了 rehash 的效率。

哈希分布均匀性

如果数组容量为 2 的 n 次方，那么 n - 1 后低位都是 1 ，此时进行 & （两个位都为 1 时，结果才为 1）运算可以确保哈希码的最低几位均匀分布。

比如 64 二进制表示为 0100 0000，64 - 1 = 0011 1111。

此时 0011 1111 与哈希码进行 & 运算，低位能均匀的反应出哈希码的随机性。

假设来个 0100 0000 与哈希码进行 & 运算，那么低位得到的值就都是 0 了，随机性很差，都是冲突。

位运算与取模

正常情况下，如果基于哈希码来计算数组下标，我们想到的都是 %（取余）计算。例如数组长度为 5 ，那么哈希码 % 5 得到的值就是对应的数组下标。

但相比于位运算而言，效率比较低，所以推荐用位运算，而要满足 i = (n - 1) & hash 这个公式，n 的大小就必须是 2 的 n 次幂。即：当 b 等于 2 的 n 次幂时，a % b 操作等于 a & ( b - 1 )

JDK 1.8 对 HashMap 除了红黑树还进行了哪些改动？

  • 改进了哈希函数的计算：JDK 1.8 中优化了哈希函数，使得哈希值的分布更加均匀，减少了哈希冲突的发生。通过在生成哈希值时使用“扰动函数”，确保哈希值的高低位都能参与到桶的选择中。
  • 扩容机制优化：JDK 1.8 改进了扩容时的元素迁移机制。在扩容过程中不再对每个元素重新取模计算索引，而是根据原数组长度的高位来判断元素是留在原位置，还是迁移到新数组中的新位置。这一改动减少了不必要的计算，提升了扩容效率。
  • 头插法变为尾插法：头插法的好处就是插入的时候不需要遍历链表，直接替换成头结点，但是缺点是扩容的时候会逆序，而逆序在多线程操作下可能会出现环，产生死循环，于是改为尾插法。

哈希函数的优化

1.7是这样实现的：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

而 1.8 是这样实现的：

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

具体而言就是 1.7 的操作太多了，经历了四次异或，所以 1.8 优化了下，它将 key 的哈希码的高 16 位和低 16 位进行了异或，得到的 hash 值同时拥有了高位和低位的特性，使得哈希码的分布更均匀，不容易冲突。

这也是 JDK 开发者根据速度、实用性、哈希质量所做的权衡来做的实现：

HashMap 是不是线程安全的？如果让你来实现一个线程安全的 HashMap 你要怎么设计？如果不用加锁你要怎么设计？

HashMap 是 非线程安全 的。因为 HashMap 的内部实现并没有加锁，多个线程同时访问和修改时可能会引发数据竞争，导致数据不一致或陷入死循环等问题。

如何实现一个线程安全的 HashMap

要实现一个线程安全的 HashMap，有多种设计方案，下面是几种常见的实现方法：

使用 Collections.synchronizedMap

Java 提供了一个简单的方法，可以将非线程安全的 HashMap 包装为线程安全的版本：

Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

这种方法通过在 HashMap 的方法上加 synchronized 锁实现线程安全。不过，这种方式对整个 Map 加锁，会导致较高的锁竞争和性能开销，尤其是在高并发情况下。

参考ConcurrentHashMap 的分段锁

使用分段锁（在 Java 8 之后更改为 CAS + 分段桶机制）来实现线程安全，同时避免了整个 Map 加锁的问题。

  • 在 Java 7 中，ConcurrentHashMap 将 Map 划分为多个 Segment，每个 Segment 是一个小的 HashMap，只有在同一个 Segment 上有冲突时才会加锁，减少了锁的粒度。
  • 在 Java 8 中，ConcurrentHashMap 引入了 CAS（Compare-And-Swap）操作和分段桶（Bucket）机制，大大减少了锁的使用，进一步提升了并发性能。

不使用锁的设计方案

如果要实现一个线程安全的 HashMap 且不使用锁，可以考虑以下几种方案：

CAS（Compare-And-Swap）+ 分段机制

可以借鉴 ConcurrentHashMap 的思想，使用分段机制结合 CAS 操作来减少锁的需求。以下是实现思路：

  1. 分段机制：将 Map 分成多个分段（如 16 个分段），每个分段是一个小的 HashMap。通过 key 的 hash 值定位到具体的分段，这样可以减少锁的粒度。
  2. CAS 操作：CAS 是一种无锁操作，可以避免传统锁带来的性能开销。CAS 操作检查某个变量是否等于期望值，如果是，则将其更新为新值；否则，返回失败。使用 CAS 操作可以在无锁的情况下实现线程安全的写入。
  3. 内部状态控制：对于需要扩容的操作，可以借助 CAS 和重试机制。比如扩容时，只对需要扩容的分段进行扩展，而不是整个 Map，以减少性能影响。

Copy-on-Write 机制

Copy-on-Write 是一种无锁实现的思路，适合读多写少的场景。实现思路如下：

  1. 每次写入操作（如 put 或 remove）时，复制当前的 Map，在副本上进行修改，然后将副本替换为当前的 Map。
  2. 读取时始终访问当前的 Map 实例，保证不会受到写入操作的影响。

这种方式的缺点是每次写入都需要复制整个 Map，会带来较大的内存和性能开销，所以只适合读多写少的场景。

为什么HashMap的头插法改为尾插法

两个线程同时操作链表且需要扩容时，在A线程执行到即将插入时，B线程此时扩容成功，由于是头插法，扩容遍历后的链表顺序倒转，再执行A线程会形成链表循环

看一个最小例子（旧桶里只有 A→B）：

初始：

  • 旧桶：A -> B -> null
  • 新桶：null

并发搬运的一个可能交错（T1、T2 都迁移同一桶）：

  1. T1处理A：保存 next=B；新桶为空，执行头插
    • 令 A.next = null
    • newHead = A
  2. T2也开始处理A（它还以为 A 还在旧桶里）：
    • 读取 next = A.next（此时已被 T1 改成 null）
    • 执行头插：A.next = newHead，而 newHead 此刻是 A 本身
    • 于是得到 A.next = A（自环）；T2 结束对 A 的处理
  3. T1继续处理B：保存next = null；头插到新桶
    • B.next = newHead（即 A，但 A 已经自环）
    • newHead = B

最终新桶链形态是：B -> A -> A -> A ...

HashMap的性能提升技巧

  • 创建时直接设置合适的大小，避免扩容
  • 适当增加扩容因子
  • 避免使用质量不高的哈希函数，确保哈希分布均匀

各种集合的特点

为什么高并发场景下可以适当降低hashmap的负载因子

高并发读取场景下减少负载因子可以降低哈希冲突，提高读取性能 频繁扩容的场景就可以适当提高负载因子的值

头插法和尾插法

1.7 是头插法，头插法的好处就是插入的时候不需要遍历链表，直接替换成头结点，但是缺点是扩容的时候会逆序，而逆序在多线程操作下可能会出现环，然后就死循环了。

然后 1.8 是尾插法，每次都从尾部插入的话，扩容后链表的顺序还是和之前一致，所以不可能出现多线程扩容成环的情况。

再延伸一下，改成尾插法之后 HashMap 就不会死循环了吗？

好像还是会，这次是红黑树的问题，我在网上看到这篇文章，有兴趣的可以深入了解下：

https://blog.csdn.net/qq_33330687/article/details/101479385

Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？

这两个版本的主要区别点在于锁的粒度。

JDK 1.7 ConcurrentHashMap 采用的是分段锁（Segment），底层还是 HashMap 的数组，但把整个数组分成 16 个 Segment（默认），每个 Segment 里面有个完整的 HashMap + 一个 ReentrantLock。

不同线程访问不同 Segment 完全不挡，同一 Segment 才锁竞争，并发度最高 16（基本够用了，但锁还是有点粗）

而 JDK 1.8 移除了 Segment，锁的粒度更细。数据结构彻底跟 HashMap 同步，变成数组 + 链表 + 红黑树。

插入时先用 CAS 无锁尝试插到数组位置，真冲突了才用 synchronized，但只锁链表/树的第一个节点（头节点），其他线程照样可以操作别的 bucket，并发度大大增加。

锁只在链表或红黑树的节点级别上进行。通过 CAS 进行插入操作，只有在更新链表或红黑树时才使用 synchronized，并且只锁住链表或树的头节点，进一步减少了锁的竞争，并发度大大增加。

详细区分图如下：

可以顺便提一句的加分点：

  • 1.7 计算 size 要把 16 个 Segment 锁住加起来，慢
  • 1.8 用 longAdder / CounterCells，基本无锁统计

扩展知识

ConcurrentHashMap 1.7 简单图解

我们再来看下大致的结构。

原理就是先通过 key 的 hash 判断得到 Segment 数组的下标，将这个 Segment 上锁，然后再次通过 key 的 hash 得到 Segment 里 HashEntry 数组的下标，下面这步其实就是 HashMap 一致了，所以我说差别就是引入了一个 Segments 数组。

因此可以简化的这样理解：每个 Segment 数组存放的就是一个单独的 HashMap。

可以看到，图上我们有 6 个 Segment，那么等于有六把锁，因此共可以有六个线程同时操作这个 ConcurrentHashMap，并发度就是 6，相比于直接将 put 方法上锁，并发度就提高了，这就是分段锁。

具体上锁的方式来源于 Segment，这个类实际继承了 ReentrantLock，因此它自身具备加锁的功能。

可以看出，1.7 的分段锁已经有了细化锁粒度的概念，它的一个缺陷是 Segment 数组一旦初始化了之后不会扩容，只有 HashEntry 数组会扩容，这就导致并发度过于死板，不能随着数据的增加而提高并发度。

ConcurrentHashMap 1.8 简单图解

1.8 ConcurrentHashMap 做了更细粒度的锁控制，可以理解为 1.8 HashMap 的数组的每个位置都是一把锁，这样扩容了锁也会变多，并发度也会增加。

思想的转变就是把粒度更加细化。不分段了，我直接把 Node 数组的每个节点分别上一把锁，这样并发度不就更高了吗？

并且 1.8 也不借助于 ReentrantLock 了，直接用 synchronized，这也侧面证明，都 1.8 了 synchronized 优化后的速度已经不下于 ReentrantLock 了。

具体实现思路也简单：当塞入一个值的时候，先计算 key 的 hash 后的下标，如果计算到的下标还未有 Node，那么就通过 cas 塞入新的 Node。如果已经有 node 则通过 synchronized 将这个 node 上锁，这样别的线程就无法访问这个 node 及其之后的所有节点。

然后判断 key 是否相等，相等则是替换 value ，反之则是新增一个 node，这个操作和 HashMap 是一样的。

扩容的区别

JDK 1.7 中的扩容：

  • 基于 Segment：ConcurrentHashMap 是由多个 Segment 组成的，每个 Segment 中包含一个 HashMap。当某个 Segment 内的 HashMap 达到扩容阈值时，单独为该 Segment 进行扩容，而不会影响其他 Segment。
  • 扩容过程：每个 Segment 维护自己的负载因子，当 Segment 中的元素数量超过阈值时，该 Segment 的 HashMap 会扩容，整体的 ConcurrentHashMap 并不是一次性全部扩容。

JDK 1.8 中的扩容：

  • 全局扩容：ConcurrentHashMap 取消了 Segment，变成了一个全局的数组（类似于 HashMap）。因此，当 ConcurrentHashMap 中任意位置的元素超过阈值时，整个 ConcurrentHashMap 的数组都会被扩容。
  • 基于 CAS 的扩容：在扩容时，ConcurrentHashMap 采用了类似 HashMap 的方式，但通过CAS 操作确保线程安全，避免了锁住整个数组。在扩容时，多个线程可以同时帮助完成扩容操作。
  • 渐进式扩容：JDK 1.8 的 ConcurrentHashMap 引入了渐进式扩容机制，扩容时并不是一次性将所有数据重新分配，而是多个线程共同参与，逐步迁移旧数据到新数组中，降低了扩容时的性能开销。

渐进式扩容分析

当 put 的时候，发现当前 node hash 值是 -1，则表明当前的节点正在扩容，则会触发协助扩容机制：

其实大家大致理解下就够了：

扩容无非就是搬迁 Node，假设当前数组长度为 32，那就可以分着搬迁，31-16 这几个下标的 Node 都由线程 A 来搬迁，然后线程 B 来搬迁 15-0 这几个下标的 Node。

简单说就是会维护一个 transferIndex 变量，来的线程死循环 cas 争抢下标，如果下标已经分配完了，那自然就不需要搬迁了，如果 cas 抢到了要搬运的下标，那就去帮忙搬就好了，就是这么个事儿。

size 逻辑的区别

1.7 有个尝试的思想，当调用 size 方法的时候不会加锁，而是先尝试三次不加锁获取 sum。

如果三次总数一样，说明当前数量没有变化，那就直接返回了。如果总数不一样，那说明此时有线程在增删 map，于是加锁计算，这时候其他线程就操作不了 map 了。

if (retries++ == RETRIES_BEFORE_LOCK) {
       for (int j = 0; j < segments.length; ++j)
           ensureSegment(j).lock(); // force creation
}
   ...再累加数量

而 1.8 不一样，它就是直接计算返回结果，具体采用的是类似 LongAdder 的思想，累加不再是基于一个成员变量，而是搞了一个数组，每个线程在自己对应的下标地方进行累加，等最后的时候把数组里面的数据统一一下，就是最终的值了。

所以这是一个分解的思想，分而治之。

在 put 的时候，就会通过 addCount 方法维护 counterCells 的数量，当然 remove 的时候也会调用此方法。

总而言之，就是平日的操作会维护 map 里面的节点数量，会先通过 CAS 修改 baseCount ，如果成功就直接返回，如果失败说明此时有线程在竞争，那么就通过 hash 选择一个 CounterCell 对象就行修改，最终 size 的结果就是 baseCount + 所有 CounterCell 。

这种通过 counterCell 数组来减少并发下场景下对单个成员变量的竞争压力，提高了并发度，提升了性能，这也就是 LongAdder 的思想。

ConcurrentHashMap1.7和1.8的区别

**1.7：**采用分段锁，每个segment是独立的，默认16个，所以最多16个线程并发执行 **1.7的扩容：**单个segment扩容，每个segment维护自己的负载因子

**1.8：**移除segment，每一个点都是Node级别的，锁只在链表或红黑树节点级别上进行，通过CAS进行插入操作，只有在更新链表或红黑树的时候才使用synchronized，并且只锁住链表或树的头结点 **1.8的扩容：**触发扩容就会全局扩容，通过CAS确保线程安全且允许多个线程同时帮助完成

总结一句话：

  • 空桶装头→ CAS（最快）；
  • 非空桶的结构性修改→ synchronized(桶头)（只锁这个 bin，比锁整个 Segment 并发度高得多）；
  • 读操作始终无锁；扩容按桶迁移，遇到转发节点就路由到新表。

渐进式rehash： 1.当进行扩容时，先为哈希表2分配空间大小为哈希表1的2倍，此时字典的rehashidx从-1变为0 2.数据开始转移，每次对hash进行crud操作都会将表1的数据迁移到2上，然后rehashidx+1 3.迁移完成后，指针从表1指向2，原先的表1置为空，rehashidx置为-1

1.7和1.8的size()方法： 1.7无锁两次采样modCount，如果相同直接返回，如果不同把所有segment加锁并获取精准值 1.8基于CAS增减的baseCount和CounterCell[ ]，为LongAdder风格，返回值近似，不精准，直接求和不加锁

ConcurrentModificationException是如何产生的？

在非线程安全的集合中并发修改集合会产生错误

使用Iterator中的remove()方法就不会，因为他维护了一个modCount的变量，每次修改操作就会增加这个参数，迭代的时候检查如果和expectedModCount不同就会抛出ConcurrentModificationException，这是一种快速失败(fail)的方式

Java 中的 HashMap 和 HashSet 有什么区别？

HashSet：是基于 HashMap 实现的集合类，不允许重复元素，用于存储一组无序的唯一元素。

HashMap：基于哈希表的数据结构，存储的是键值对（key-value），键必须唯一，值可以重复。

实际上HashSet 内部使用 HashMap 来实现，HashSet 中的元素实际上存储在 HashMap 的键中，而所有的值都是一个常量对象 PRESENT。因此，HashSet 仅操作 HashMap 的键部分。

Java 中的 HashMap 和 Hashtable 有什么区别？

线程安全性：

  • HashMap：非线程安全，多线程环境下可能会产生数据不一致问题。
  • Hashtable：线程安全，内部大部分方法都使用了 synchronized 关键字进行同步，保证了多线程的并发安全性。

2）性能差异：

  • HashMap：由于没有线程同步开销，因此在单线程环境下性能优于 Hashtable。
  • Hashtable：由于方法的同步锁机制，性能低于 HashMap。由于使用全局锁的方式，使得即使是不同的操作也会被串行化。

3）允许空值：

  • HashMap：允许一个 null 键和多个 null 值。
  • Hashtable：不允许 null 键和 null 值，插入 null 键或 null 值时会抛出 NullPointerException。

4）继承结构：

  • HashMap：继承自 AbstractMap，是 Map 接口的实现类。
  • Hashtable：继承自 Dictionary（已废弃），后来也实现了 Map 接口。它是一种较为古老的类，在 Java 2 之后逐渐被 HashMap 所取代（不推荐使用）。

5）迭代器类型：

  • HashMap：使用的是快速失败的 Iterator，在迭代过程中如果对 Map 进行结构性修改，会抛出 ConcurrentModificationException。
  • Hashtable：使用的是弱一致性的 Enumerator，虽然也不建议在迭代过程中修改 Map，但不会抛出 ConcurrentModificationException。

什么是 Java 的 Hashtable、HashMap 和 TreeMap？它们有什么区别？

了解 Hashtable、HashMap、TreeMap

1）Hashtable

  • 是一个古老的实现，随 Java 1.0 引入。
  • 它是同步的，这意味着它是线程安全的，但这也意味着它通常比非同步的实现（如 HashMap ）慢。
  • 不允许使用 null 键或 null 值。
  • 是一个基于散列表的 Map 实现。

2）HashMap

  • 是 Java 1.2引入的，作为 Hashtable 的一个更先进的替代品。
  • 它是非同步的，这意味着它不是线程安全的，但其性能在单线程环境下通常比 Hashtable 好。
  • 允许一个 null 键和多个 null 值。
  • 同样是基于散列的 Map 实现，但提供更快的迭代。

3）TreeMap

  • 基于红黑树（ Red-Black tree ）的 NavigableMap 实现。
  • 按照键的自然顺序或创建时提供的 Comparator 进行排序，因此它除了作为 Map 外，还可以用作双端队列。
  • 不是线程安全的。
  • 不允许 null 键（如果使用自然排序），但允许多个 null 值。
  • 提供了一些特殊的方法来处理键的有序性，如 firstKey(), lastKey(), headMap(), tailMap() 等。

Java 中的 LinkedHashMap 是什么？

LinkedHashMap 是 Java 集合框架中的一个实现类，它继承自 HashMap，并且保留了键值对的插入顺序或访问顺序。

它内部是通过维护了一个双向链表来记录元素的插入顺序或访问顺序。

使用场景：

  • 缓存实现：可以根据访问顺序移除最久未使用的元素，常用于 LRU（Least Recently Used）缓存。
  • 数据存储：需要保持元素插入顺序的场景。

什么是Hash碰撞？

Hash 碰撞就是：两个不同的 key，经过 hash 函数计算后，得到了同一个数组下标（桶位置）。

常见有以下几种方式解决哈希碰撞问题：

1）拉链法（链地址法）：

将哈希表中每个槽的位置变成一个链表，当多个键的哈希值相同时，将它们存储在同一个链表中。

2）开放寻址法：

如果出现碰撞，寻找哈希表中的下一个可用位置。

3）再哈希法：

在出现碰撞时，使用第二个哈希函数计算新的索引位置，如果还冲突则再用另一个哈希函数重新算一次位置，直到无冲突。

扩展知识

一定会发生 Hash 碰撞吗？

理论上是的，核心原因是鸽巢原理，也称为抽屉原理。

就像 10 只鸽子放进 9 个鸽笼，那么一定有一个鸽笼放进了至少两只鸽子。

同理，HashMap 初始桶数 16，key 的数量确是无限多，不论哈希函数多平均，要把无数的 key 放进有限的桶中，必然就会冲突。

所以碰撞无法避免，咱们能做的是 “减少碰撞概率” 或 “优雅处理碰撞”。

拉链法（链地址法）

这是最常见、也是最容易理解的方法。Java 的 HashMap 就是采用这种方式（数组 + 链表/红黑树）。

核心思想是：外挂存储。哈希表的每一个槽位（Bucket）不再只存一个数据，而是作为一个“入口”。所有哈希值相同的 Key，都像挂葡萄一样，挂在这个入口下面的链表上。

工作流程：

  1. 计算 Hash(Key) 取余得到索引 i。
  2. 查看数组下标 i 的位置
  3. 如果是空的，直接把数据放进去（或者创建一个新链表头）。
  4. 如果已经有数据了（发生碰撞），就顺着链表往下找。
  5. 如果链表中找到了相同的 Key，覆盖 Value。
  6. 如果走到链表尾部还没找到，就把新数据追加到链表末尾。

这种方式的优点是：

  1. 内存利用率高：不需要预先分配大量连续空间，链表节点是动态申请的。
  2. 处理冲突简单：无论冲突多少次，无非就是链表变长而已。
  3. 对负载因子不敏感：即使哈希表里的元素数量超过了数组大小（负载因子 > 1），它依然能工作（只是链表会很长，查询变慢）。

缺点也很明显：

  1. 额外的内存消耗：每个节点都需要额外的指针（Next指针）来指向下一个节点。
  2. 缓存不友好：链表节点在内存中是分散的，CPU 缓存命中率不如连续数组高。
  3. 查询退化：如果黑客故意构造大量 Hash 值相同的 Key（Hash 洪水攻击），链表会变得极长，查询时间从 O(1) 退化为 O(n)。

💡所以：Java 8 引入了红黑树来解决这个问题，当链表长度超过 8 时转为红黑树，将 O(n) 优化为 O(log n)。详细可看为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

开放寻址法

这种方法不使用额外的链表，所有的数据都必须存在主数组里。

核心思想是：占坑位。如果你的位置被占了，你就去数组里找下一个空位。这就像在电影院找座位，票上的座位有人了，你就往后挨个找空座。

常见的探测方式：

  • 线性探测：步长为 1。位置被占了，就看 index+1，再看 index+2... 直到找到空位。
  • 二次探测：步长为平方数。位置被占了，就看 index+1²，再看 index+2²... 避免数据聚集在一起。

工作流程（以线性探测为例）：

  1. 计算 Hash(Key)取余 得到索引 i。
  2. 如果 i 位置是空的，直接存入。
  3. 如果 i 位置有人了（且 Key 不同），就检查 (i+1) % size。
  4. 重复步骤 3，直到找到空位或者遍历完整个数组。

在哈希表中寻找下一个空闲的槽位以存储发生碰撞的元素，常见寻找方式有线性探查、平方探查和双重散列。

这种方式的优点是：

  1. 节省内容：不需要指针，节省了指针占用的内存空间。
  2. 缓存友好：数据都在连续的数组里，CPU 缓存命中率高。

缺点：

  1. 删除困难：你不能直接把元素删掉，因为这会截断后续元素的查找路径。通常需要标记为“墓碑（Tombstone）”或“已删除”，逻辑复杂。
  2. 聚集现象：这是线性探测最大的问题。一旦某一块区域冲突多了，数据会连成一片，后续插入的数据为了找空位要走很久，导致性能急剧下降。
  3. 容量限制：因为没有链表，数组存满了就必须扩容，负载因子通常不能太高（一般 0.7 左右性能就开始下降）。

💡Java 的 ThreadLocalMap 使用的就是开放寻址法。

再哈希法

当一个哈希函数计算出的地址发生冲突时，它会使用另一个哈希函数来重新计算地址，直到找到一个空位为止。

核心思想是：多重哈希。不进行探测（不去找相邻或跳跃的空位），而是直接换一个新哈希函数重新计算一个全新的地址，直到不冲突！

工作流程：

  1. 计算 Hash(Key) 取余得到索引 i。
  2. 如果 i 位置是空的，直接存入。
  3. 如果 i 位置有人了（且 Key 不同），使用备用的第二个函数。
  4. 计算新位置 Hash2(Key) 取余得到索引 j。
  5. 如果 j 位置有人了（且 Key 不同）继续用 Hash3(Key)……
  6. 直到找到空位

优点是：

  • 不易产生聚集：因为不同的哈希函数计算出的分布通常是独立的，数据会散落得非常均匀，不会像线性探测那样连成一片。

缺点：

  • 计算开销大：每次冲突都要做一次完整的、复杂的哈希运算（比如 MD5 换成 SHA-1，或者不同的多项式计算），比简单的“加法探测”要消耗更多的 CPU 时间。
  • 函数设计难：需要准备好几个“足够好且相互独立”的哈希函数，这在实现上比较麻烦。

开放寻址法，还存在聚集问题（Clustering） 基本聚集：线性探测易形成连续的元素块，导致后续冲突需更长的探测链。 负载因子敏感 随着负载因子（元素数 / 容量）升高，冲突概率急剧增加，性能下降。 通常需保持负载因子 < 0.5，导致空间利用率低。 删除元素的陷阱与解决方案 直接删除的问题： 若直接删除元素（如将数组位置置为 null），可能导致后续查找失败。例如：

键 k1 和 k2 冲突，k2 被插入到探测链的下一个位置。 若删除 k1 并清空其位置，查找 k2 时会在 k1 的位置提前终止，误认为 k2 不存在。

正确做法： 使用逻辑删除而非物理删除， 墓碑标记（Tombstone） 实现：在删除位置放置特殊标记（如 TOMBSTONE），指示该位置曾被占用但现已删除。 查找时：遇到墓碑标记继续探测，遇到 null 才终止。 插入时：可重用墓碑标记位置。

何时可以安全删除元素？ 使用墓碑标记时： 任何时候都可删除元素，只需标记为墓碑。 插入时可重用墓碑位置，但需确保探测链完整。 不使用墓碑标记时： 仅当元素位于其原始哈希位置或探测链的起始位置时，才可直接删除。 否则需使用墓碑或重建哈希表。

资料

一口气过完HashMap所有面试考点

最近更新：:
Contributors: luokaiwen