Java的HashMap面试题

目录

1. 说一下HashMap的工作原理？（1.7和1.8都是）

2. 了解的哈希冲突解决方法有哪些

3. JAVA8的 HashMap做了哪些优化

4. HashMap的数组长度必须是 2 的 n 次方

5. HashMap什么时候引发扩容

5.1 数组容量小于64的情况：

5.2 链表转红黑树的条件是什么

6. 默认扩容的负载因子为什么是0.75 设太大和太小有什么问题

7. Java 8 中 HashMap 链表转红黑树和红黑树转链表的阈值为什么分别是 8 和 6

一、为什么链表转换为红黑树的阈值是 8？

二、还会从红黑树变回链表吗？会的。

流程核心问题（⭐️💗💗）流程核心问题（⭐️💗💗）

8. JDK1.7的HashMap的扩容流程

参考面试回答：

9. JDK 1.8的HashMap 的 扩容流程

参考面试回答：

10. JDK1.7的put 方法的流程

参考面试回答：

11. JDK 1.8 Put流程

参考面试回答：

12. HashMap key可以为null吗

13. HashMap 和 HashTable 有什么区别

14. HashMap为什么不是线程安全的

JDK 1.7 中 HashMap 的线程不安全表现：

JDK1.8:

15. ConcurrentHashMap在JDK 1.7中实现原理

参考面试回答：

16. ConcurrentHashMap在JDK 1.8中实现原理

参考面试回答：

17. ConcurrentHashMap1.7和1.8的区别

18. ConcurrentHashMap 和 Hashtable 的区别 分别说1.7 和1.8与Hashtable 的区别

19. ConcurrentHashMap的key、value是否可以为null?

---

1. 说一下HashMap的工作原理？（1.7和1.8都是）

分析： 这个问题笼统回答即可

参考回答：

HashMap的工作原理基于哈希表、是使用哈希函数将键映射到存储位置的数据结构。哈希表通过计算键的哈希值、并将其转化为索引数组、从而快速定位键值对的存储位置。

• HashMap 的底层是一个数组，每个数组元素称为一个 bucket。通过哈希函数将键（key）映射到数组（称为 table 或 buckets）的某个索引位置。

• 在理想情况下、哈希函数能将键均匀分布到哈希表中、以最小化哈希冲突。然而当多个键哈希到同一位置时、就需要解决哈希冲突。

• 顺便说一下了解的哈希冲突解决方法有哪些：链地址法、开放地址法、再哈希法

  • 在Java 1.7中、HashMap主要使用链表来解决哈希冲突、将具有相同哈希值的键值对链接在一起。

  • 但在Java 1.8中、为了进一步提高性能、当链表长度和数组长度超过一定阈值时、链表会转换为红黑树。

• 所以总结HashMap结合了哈希表、链表和红黑树的优点，实现了高效的键值对存储和查找功能。

2. 了解的哈希冲突解决方法有哪些

参考回答：链地址法、开放地址法、再哈希法

• 链地址法：

  • 每个哈希桶存放一个链表（或其他数据结构，如红黑树）、所有映射到同一哈希槽的键值对都存放在这个链表中。

  • 优点：实现简单、在负载因子较低时性能较好、链表长度动态增长。

  • 缺点：当碰撞严重时、链表会变长、查找效率可能退化到 O(n)（但可以通过转换为红黑树等方式优化）

• 开放地址法：

  • 所有元素都存放在哈希表本身中、当发生冲突时、通过探测寻找下一个空槽。

  • 常见探测策略：

    • 线性探测（Linear Probing）：依次检查下一个位置。

    • 二次探测（Quadratic Probing）：探测位置与步长的平方有关，减少聚集问题。

    • 双重哈希（Double Hashing）：采用第二个哈希函数确定探测步长，更均匀分布。

  • 优点：节省内存，不需要额外的链表结构。

  • 缺点：在负载因子较高时容易产生堆积现象、性能下降、删除操作较为复杂。

• 再哈希法：

  • 当哈希冲突严重或负载因子达到一定阈值时、重新构造哈希表并计算新的哈希槽。

  • 优点：可以均衡哈希分布、降低冲突概率。

  • 缺点：重建哈希表会带来较大的开销、尤其在数据量大时性能影响明显。

3. JAVA8的 HashMap做了哪些优化

• 1.7的数组+链表 改成了 1.8的数组+链表或红黑树
• 1.7的链表的插入方式从头插法 改成了 尾插法
• 扩容的时候：
  • 1.7 需要对原数组中的元素进行重新hash定位在新数组的位置
  • 1.8采用更简单的判断逻辑位置不变或索引+旧容量大小
  • Java 7 是先扩容后插入新值、而 Java 8 是先插入新值再判断是否要扩容。

4. HashMap的数组长度必须是 2 的 n 次方

参考回答：

HashMap的长度选择为 2的幂次方、主要是为了提高哈希表的性能。

在 HashMap 中、键值对的存储位置是通过哈希值和数组长度计算得出的。一开始是通过取模运算

但是取模运算（%）的性能较低 尤其是在高频率操作（如 put 和 get）中、会影响 HashMap 的整体性能。

所以

• 用位与运算（&）替代取模运算（%） 因为位与运算的性能更高。

• 但位与运算替代取模运算需要满足一个条件：

• 也就是hash % length == hash & (length - 1)

• 这个等式只有当 length 是 2 的 n 次方时才成立。

其次

• 当 HashMap 的键值对数量达到数组长度的75%时、会触发数组扩容操作。

• 而扩容时利用2的幂次方的长度、可以非常快速地将原有的节点重新分配到新的数组位置上。

5. HashMap什么时候引发扩容

参考面试回答：

HashMap进行扩容取决于以下两个元素：

• Capacity：HashMap当前长度。
• LoadFactor：负载因子、默认值0.75
• 当Map中的元素个数超过了16*0.75=12之后开始扩容
• 通常是扩容为原来的两倍长度

扩容的时候：

• JDK 1.7: 在扩容时、需要遍历旧数组中的每一个元素、重新计算其哈希值（因为哈希函数可能依赖于数组长度、或者说重新计算在新表中的索引）、然后将其定位到新数组（容量通常是旧数组的两倍）的相应位置。这个过程涉及到所有元素的重新散列。

• JDK 1.8: 扩容机制得到了优化。由于新容量是旧容量的两倍、元素在新数组中的位置要么保持不变、要么是 原索引 + 旧容量。这个判断只需要根据元素哈希值的某一个特定位（hash & oldCap）是0还是1来决定、避免了对所有元素进行完整的重新哈希计算、效率更高

5.1 数组容量小于64的情况：

• 如果当前链表长度小于8并且数组的长度小于 64、HashMap 会选择扩容、而不是将链表转换为红黑树。

• HashMap 会优先选择扩容整个哈希表。这是因为：

  • 如果数组容量本身就很小（小于64）、出现长链表很可能是因为容量不足导致哈希冲突过于频繁。此时扩大数组容量、让元素能更均匀地散布到更多的桶中、是更合理的解决方案、通常能有效缩短链表长度。

  • 如果扩容后该链表（或者其他链表）依然达到了长度8、并且此时数组容量已经大于等于64了、那么才会进行树化

5.2 链表转红黑树的条件是什么

• 当链表长度达到 8 且 数组长度大于等于64的时候 才会转换为红黑树

  • 当某个桶（bucket）中的链表长度达到 TREEIFY_THRESHOLD（默认为8）

  • 并且 HashMap 当前的数组容量（table.length）必须大于等于 MIN_TREEIFY_CAPACITY（默认为64）。

  • 只有同时满足这两个条件、该桶中的链表才会转换为红黑树。

6. 默认扩容的负载因子为什么是0.75 设太大和太小有什么问题

参考面试回答：

• 是空间与时间的权衡:

  • 对于使用链表法的哈希表、查找一个元素的平均时间复杂度为 O(1+n)、其中 n 是链表的长度。

  • 加载因子越大、空间利用率越高、但链表长度越长、查找效率越低。

  • 加载因子越小、空间利用率越低、链表长度越短、查找效率越高。

• 默认值 0.75 的合理性:

  • 0.75 是一个经验值、能够在空间利用率和查找效率之间取得较好的平衡。

  • 如果加载因子太大（如 1.0）、链表长度会增加、查找效率下降。

  • 如果加载因子太小（如 0.5）、太小可能会影响扩容频繁、影响性能。空间利用率低、造成内存浪费。

7. Java 8 中 HashMap 链表转红黑树和红黑树转链表的阈值为什么分别是 8 和 6

分析：

链表转换为红黑树的阈值是 8、而红黑树转换回链表的阈值是 6。

参考面试回答：

• 在 Java 的 HashMap 中、当发生哈希碰撞、同一个桶内的节点最初会以链表形式组织。

• 如果链表长度较短（小于 8）、遍历链表的性能是可以接受的

• 而当链表长度达到 8 时、意味着碰撞的可能性非常高、查找效率可能会退化到 O(n)的水平。

• 为了避免这种情况、HashMap 会将链表转换成红黑树、这样查找、插入和删除操作的时间复杂度就能降到 O(log⁡n)O(log n)。

选择 8 作为转换的阈值有三个主要原因：

一、为什么链表转换为红黑树的阈值是 8？

选择 8 作为链表转换为红黑树的阈值，主要是基于以下几点考虑：

1. 性能与时间复杂度的权衡：

• 当哈希冲突发生、同一个桶（bucket）中的元素会以链表形式存储。如果链表长度很短、遍历链表的查询效率（O(N)）是可以接受的。
• 但是当链表长度持续增长、查询性能会急剧下降。为了避免在极端情况下（例如大量哈希冲突导致某个桶的链表非常长）性能退化、HashMap 引入了红黑树。红黑树的查找、插入和删除操作的时间复杂度都能稳定在 O(log N)。
• 阈值 8 就是一个在链表查询效率尚可和红黑树结构优势开始显现之间的一个平衡点

2. 概率统计与经验数据：

• 在理想的哈希函数和负载因子下、一个桶中链表长度达到 8 的概率是非常低的。根据泊松分布、理想情况下，哈希冲突导致链表长度达到 8 的概率大约是千万分之六 (0.00000006)。这意味着正常情况下很少会触发树化。
• 这个阈值是基于大量实验和统计分析得出的。选择 8 能够在绝大多数情况下保持链表的简单高效、同时在极少数极端哈希冲突发生时，通过转换为红黑树来保证性能下限。

3. 空间开销的考虑：

• 红黑树的节点（TreeNode）比普通链表的节点（Node）要占用更多的内存空间、因为它需要存储颜色、父节点、左子节点和右子节点的引用。
• 如果链表长度很短就进行树化、那么这种额外的空间开销可能就不太划算。因此只有当链表确实比较长、性能提升能够抵消空间开销时、转换才有意义。

二、还会从红黑树变回链表吗？会的。

为了避免在链表和红黑树之间因为元素数量的微小波动而频繁地进行结构转换（这本身也是有开销的）

因为只有当链表确实比较长、性能提升能够抵消空间开销时、转换才有意义。

设计者引入了一个回退策略

• 去树化阈值： 当红黑树中的节点数量因为删除操作而减少到一定程度时、它会转换回链表。这个阈值通常是 6（UNTREEIFY_THRESHOLD）。

• 滞后性（Hysteresis）： 您可以看到、树化的阈值是 8、而去树化的阈值是 6。这两个阈值之间存在一个差值（7 这个临界点）。这种设计被称为滞后性或迟滞现象。

  • 它的目的是防止频繁转换。如果树化和去树化的阈值是同一个值（比如都是7）、那么当一个桶的元素数量在7和8之间波动时、就会频繁地进行链表和红黑树之间的转换、这会带来不必要的性能开销。

  • 通过设置不同的阈值（8用于树化、6用于去树化）、可以确保只有当元素数量发生较大变化时、才会进行结构转换、从而提高了整体的稳定性与效率

总结：

• HashMap 在链表长度达到 8 时会转换为红黑树以优化查询性能
• 当红黑树节点数减少到 6 时、会转换回链表以减少空间开销并避免在临界点频繁转换结构。

流程核心问题（⭐️💗💗）流程核心问题（⭐️💗💗）

8. JDK1.7的HashMap的扩容流程

参考面试回答：

JDK 1.7 HashMap 的扩容是一个在达到特定条件时、通过创建一个两倍于原容量的新数组、并将旧数组中的所有元素通过头插法 然后重新计算索引并迁移到新数组的过程。这个过程是单线程的、并且由于头插法的特性、在并发环境下（如果外部不加锁）进行扩容操作时存在产生环形链表（死循环）的风险。

关于 JDK 1.7 中 HashMap 的扩容流程、它主要分为以下几个核心步骤：

1. 触发扩容

• 当向 HashMap 中添加元素，并且 HashMap 当前的元素数量 (size) 达到了预设的阈值
• 这个阈值通常是 当前容量 * 加载因子 也就是16*0.75。就会触发扩容操作。

2. 创建新数组

• 首先HashMap 会创建一个新的 Entry 数组、这个新数组的容量通常是旧数组容量的两倍

3. 数据迁移

• 这是扩容过程中最核心也最复杂的部分、由 transfer 方法执行。
• 遍历旧表： transfer 方法会遍历旧 Entry 数组中的每一个桶（bucket）。
• 遍历桶内链表： 对于每个桶中存在的链表（如果该桶非空），它会依次处理链表中的每一个 Entry 对象。
• 重新计算索引： 对于从旧表中取出的每一个 Entry、需要根据其键的哈希值和新数组的容量来重新计算它在新数组中的索引位置。计算方式通常是 hash & (newCapacity - 1)。
• 头插法迁移： 这是 JDK 1.7 扩容的一个关键特点。当将一个 Entry 迁移到新数组的某个桶时、它会采用头插法。也就是说这个被迁移的 Entry 会成为新桶中链表的新的头部、其 next 指针会指向原先该桶中的旧头节点。这个头插法是导致并发扩容时可能产生死循环的根源、因为它会反转原链表中元素的顺序。4. 

4. 最后更新内部引用和属性：

• 当所有元素都从旧表成功迁移到新表后：
• HashMap 内部的 table 引用会从指向旧数组改为指向新创建的、容量更大的数组。
• threshold（下一次扩容的阈值）会根据新的容量和加载因子重新计算并更新。

9. JDK 1.8的HashMap 的 扩容流程

参考面试回答：

10. JDK1.7的put 方法的流程

参考面试回答：

首先会判断 table 容器是否为空:

• 如果 table 为空、表示 HashMap 尚未初始化 需要先初始化 table 数组。

• 如果 table 未初始化 调用 initialize 方法进行初始化。

然后判断 key 是否为空:

• 如果 key 为 null 则调用特殊方法处理 null 键（哈希值固定为 0 存储在 table[0] 的位置）。

• 如果 key 不为 null 则调用 hash(key) 方法 根据 key 计算哈希值。

然后计算数组索引:

• 根据哈希值和数组长度计算键值对在 table 数组中的存储位置

• 如果该位置不为空 说明存在哈希冲突 需要进一步处理。

解析哈希冲突遍历链表（或红黑树）:

• JDK 7:

  • 遍历链表、查找是否存在相同的 key。

  • 如果找到相同的 key、则直接替换对应的 value。

  • 如果未找到相同的 key、则将新的键值对插入到链表的头部（头插法）。

处理扩容:

• 如果当前元素数量超过阈值 则调用 resize() 方法进行扩容。

• 扩容后 数组长度变为原来的 2 倍 并重新计算所有键值对的存储位置

插入新元素:

• 调用 addEntry 方法、将新的键值对插入到链表或红黑树中。

结束:put 方法执行完毕。

11. JDK 1.8 Put流程

参考面试回答：

总结来说，JDK 1.8 的 put 流程是：

• 先定位桶、如果桶为空则直接插入
• 如果不为空、则根据桶是链表还是红黑树进行相应的查找、更新或插入（链表尾插）操作、并在必要时进行链表到红黑树的转换。
• 最后更新 size并检查是否需要扩容。

分析：表初始化检查：首先会检查内部的 数组是否为null或者是空的。如果是会调用 resize() 方法进行初始化

• 计算哈希与定位桶

  • 计算传入 key 的哈希值。根据计算出的哈希值和当前 table 的长度、确定该键值对应该存储在 table 数组中的哪个索引位置（即哪个桶）。

  • 计算方式通常是 hash & (table.length - 1)。

• 处理桶内情况

  • 空桶 (Empty Bucket)： 如果目标桶当前是空的（即 table[i] == null）、则直接创建一个新的 Node（包含键、值、哈希和 next 指针为 null）、并将其放置在该桶中。

  • 非空桶： 如果目标桶中已经有节点了、说明发生了哈希冲突、此时会：

    • 检查头节点： 首先检查桶的头节点（p = table[i]）。如果头节点的哈希值与当前 key 的哈希值相同，并且它们的 key 也相同（通过 == 或 equals() 判断），则说明找到了相同的键。此时会用新的 value 覆盖旧的 value、并返回旧 value。

    • 检查节点类型并遍历： 如果头节点不是要找的键、则需要进一步判断该桶的结构：

      • 红黑树 如果桶的头节点是 TreeNode 类型说、明这个桶已经被树化了。此时会调用红黑树的插入方法 (p.putTreeVal(this, tab, hash, key, value)) 来添加或更新节点。

      • 链表 如果桶是链表结构、则会遍历链表中的每一个节点：

        • 在遍历过程中、如果找到了与当前 key 相同的节点（哈希相同且 key equals）、则用新 value 覆盖旧 value、并返回旧 value。

        • 如果遍历到链表末尾仍未找到相同的 key、则创建一个新的 Node、并将其追加到链表的尾部（尾插法）。

        • 树化检查

• 更新计数与检查扩容

  • 如果成功插入了一个新的键值对（而不是更新已存在的键），modCount（修改计数器）会增加、并且 HashMap 的实际元素数量 size 会加1。

  • 在 size 增加后、会检查 size 是否超过了当前的扩容阈值 (threshold)。如果超过了、则会调用 resize() 方法进行扩容。

• 返回

  • 如果 put 操作是更新了已存在键的值、则返回旧的 value。

  • 如果 put 操作是插入了一个新的键值对、则返回 null

12. HashMap key可以为null吗

答： HashMap 允许键（key）为 null。

• hashMap的key和value都可以null、但是null作为key只能有一个。 即 HashMap 中最多只能有一个 null 键。因为hashMap中、如果key值一样、那么put操作会覆盖相同key值对应value、所以key为null只能有一个。

• 但是null作为value可以有多个

  • 当Key为null时 当键为 null 时 HashMap 会将其哈希值特殊处理为 0。

  • 也就是将 null 键对应的键值对存储到哈希表（table 数组）的第一个位置（即索引为 0 的桶）

13. HashMap 和 HashTable 有什么区别

• HashMap 是线程不安全的、HashTable 是线程安全的。HashTable 的方法通过 synchronized 关键字实现同步、保证了线程安全、但性能较低

• HashMap 只允许一条记录的键为 null、允许多条记录的值为 null

• HashTable：不允许键或值为 null、否则会抛出 NullPointerException

初始容量：

• HashMap：默认初始容量为 16、扩容时容量变为原来的 2 倍

• HashTable：默认初始容量为 11、扩容时容量变为原来的 2 倍加 1

哈希值计算：

• HashMap对hashCode进行额外处理 会重新计算键的哈希值、以减少哈希冲突。

• HashTable：直接使用对象的 hashCode 不进行额外的哈希

14. HashMap为什么不是线程安全的

分为JDK1.7和1.8回答

JDK 1.7 中 HashMap 的线程不安全表现：

• 在 JDK 1.7 中，HashMap 的线程不安全主要体现在以下几个方面：

• 并发 put 操作导致数据覆盖或丢失：

  • 当多个线程同时向同一个桶（bucket）或者对 HashMap 进行插入操作时、由于 put 操作（特别是 addEntry 方法中的步骤不是原子的、一个线程的写入操作可能会被另一个线程的写入操作覆盖、导致数据丢失。

  • 并发的 put、remove 或 resize 操作也可能因为没有正确的同步而导致某些元素丢失、或者 size 属性不准确、出现数据丢失或不一致的情况。

• 并发 resize (扩容) 导致死循环：

  • 这是 JDK 1.7 HashMap 在并发场景下最著名的问题。

  • 死循环产生过程简述：

    • 假设有两个线程（T1、 T2）同时检测到需要扩容并执行 resize。

    • 它们可能同时操作旧表中的同一个链表（例如 e -> nextE）。

    • T1 执行一部分、比如处理了 e、将 e 移到新表、此时在新表中 e 的 next 可能指向了某个节点（或者为 null）。

    • T2 也开始处理、它看到的 e 和 nextE 可能还是旧表中的状态。

    • 由于头插法和并发执行的交错、可能导致 e.next 指向了 nextE、同时 nextE.next 又意外地指向了 e、从而形成一个环形链表。当后续 get 操作遍历到这个环形链表时，就会陷入死循环，导致 CPU 飙升

• ConcurrentModificationException 异常：

  • 当一个线程通过迭代器遍历 HashMap 时、如果另一个线程同时对 HashMap 的结构进行了修改（如添加或删除元素）、那么迭代器在下一次操作时会检测到 modCount 的变化

  • 并抛出 ConcurrentModificationException。

JDK1.8:

• JDK1.8的HashMap 通过在扩容时采用尾插法、成功解决了 JDK 1.7 版本中因并发扩容（头插法）可能导致的链表死循环问题。这是一个重要的改进。

• 然而尽管解决了死循环的问题、JDK 1.8 的 HashMap 仍然不是线程安全的。在没有外部同步的情况下、多个线程并发地对 HashMap 进行修改操作（如 put、remove、resize）时、依旧会产生问题、主要是数据丢失、数据覆盖或内部结构损坏（尽管不一定是死循环）它的核心操作都不是原子性的、也没有内置的锁机制来保护共享状态。

• 因此在多线程环境下、直接并发写 HashMap 是不安全的、会导致数据不一致、丢失或覆盖。对于并发场景应该选择 ConcurrentHashMap。

15. ConcurrentHashMap在JDK 1.7中实现原理

参考面试回答：

• 原理

  • JDK 1.7 的 ConcurrentHashMap 的核心思想是将整个 HashMap 分割成多个独立的段 (Segment)

  • 而每个Segment元素、即每个分段则类似于一个Hashtable，它有自己的锁（ReentrantLock）。

• 数据结构

  • 它的数据结构就是 ConcurrentHashMap 内部维护一个 Segment 数组。

  • Segment 的数量在初始化时确定、并且之后不能改变、默认是16。也就是说默认可以同时支持16个线程并发写

    • 每个 Segment 继承自 ReentrantLock、这意味着每个 Segment 都是一个独立的锁。

    • 每个 Segment 内部包含一个 HashEntry 数组（HashEntry<K,V>[] table）。HashEntry 用于存储键值对、并且当发生哈希冲突时、这些 HashEntry 会以链表的形式组织起来

    • 当对HashEntry数组的数据进行修改时、必须首先获得对应的Segment的锁。也就是说对同一Segment的并发写入会被阻塞、不同Segment的写入是可以并发执行的。

16. ConcurrentHashMap在JDK 1.8中实现原理

参考面试回答：

相比于 JDK 1.7、JDK 1.8 的 ConcurrentHashMap 做了较大的改动，摒弃了分段锁（Segment）的设计。采用了更为细粒度的锁机制、主要是 CAS (Compare-And-Swap) 操作 和 synchronized 关键字

1. 核心设计思想与数据结构变化：

   1. 去 Segment 化： JDK 1.8 不再使用 Segment 数组、而是回归到类似于 HashMap 的结构、即一个Node 数组（Node<K,V>[] table）。Node 是存储键值对的基本单元。

   2. 锁的粒度更细： 锁的粒度从原先的 Segment 级别降低到了每个数组桶（bin）的头节点级别。这意味着只有当多个线程尝试修改同一个桶中的数据时、才会发生锁竞争。

   3. 引入红黑树： 当某个桶中的链表长度过长（默认超过阈值 8、并且数组长度大于等于64）时为了提高查询效率（从 O(N) 降低到 O(logN)）、链表会转换为红黑树（TreeNode）

2. 并发控制机制：

   1. CAS 操作： 对于 Node 数组的初始化、向空桶中放置第一个节点等操作、会优先尝试使用 CAS 操作来原子性地更新。如果 CAS 成功、则避免了加锁的开销。

   2. 如果当 CAS 操作失败、或者需要修改某个桶中已存在的链表或红黑树时（例如添加新节点、删除节点、更新节点值）、会使用 synchronized 关键字锁住该桶的头节点（链表的第一个节点或红黑树的根节点）。

   3. 选择 synchronized 而不是 ReentrantLock，一方面是因为 JDK 1.6 以后 synchronized 的性能得到了极大的优化（如锁膨胀机制）、另一方面是 synchronized 在某些情况下可以减少内存开销

17. ConcurrentHashMap1.7和1.8的区别

ConcurrentHashMap 分为JDK1.7 和JDK1.8 来回答

• JDK 1.7 版本：

  • 1.7是将整个 HashMap 分割成多个独立的段 (Segment)而每个Segment元素、即每个分段则类似于一个Hashtable，每个 Segment 继承自 ReentrantLock、这意味着每个 Segment 都是一个独立的锁。每个数组段内部用链表来解决哈希冲突。

  • 在 JDK 1.7 中、通过分段锁（Segment）机制、每个段拥有独立的锁、不同段之间的操作可以并发执行、大大提升了并发性能。

• JDK 1.8 版本：

  • ConcurrentHashMap 进行了优化、底层数据结构变为 Node 数组+CAS+synchronized、结合链表和红黑树。当某个桶中的链表长度过长（默认链表长度超过阈值 8、并且数组长度大于等于64）时为了提高查询效率（从 O(N) 降低到 O(logN)）、链表会转换为红黑树（TreeNode）

  • 并发控制机制：

    • CAS 操作： 对于 Node 数组的初始化、向空桶中放置第一个节点等操作、会优先尝试使用 CAS 操作来原子性地更新。如果 CAS 成功、则避免了加锁的开销。

    • 如果当 CAS 操作失败、或者需要修改某个桶中已存在的链表或红黑树时（例如添加新节点、删除节点、更新节点值）、会使用 synchronized 关键字锁住该桶的头节点（链表的第一个节点或红黑树的根节点）。

    • 选择 synchronized 而不是 ReentrantLock，主要是JDK 1.6 以后 synchronized 的性能得到了极大的优化（如锁膨胀机制）

18. ConcurrentHashMap 和 Hashtable 的区别 分别说1.7 和1.8与Hashtable 的区别

1. 底层数据结构：

• JDK 1.7 版本：

  • 1.7是将整个 HashMap 分割成多个独立的段 (Segment)而每个Segment元素、即每个分段则类似于一个Hashtable，每个 Segment 继承自 ReentrantLock、这意味着每个 Segment 都是一个独立的锁。每个数组段内部用链表来解决哈希冲突。

  • Hashtable 采用数组+链表的结构、数组作为主要存储结构、链表用于解决冲突。与1.7的Segment有不同

• JDK 1.8 版本：

  • ConcurrentHashMap 进行了优化、底层数据结构变为 Node 数组+CAS+synchronized、结合链表和红黑树。当某个桶中的链表长度过长（默认链表长度超过阈值 8、并且数组长度大于等于64）时为了提高查询效率（从 O(N) 降低到 O(logN)）、链表会转换为红黑树（TreeNode）

  • Hashtable 的数据结构依然保持数组+链表的方式

2. 线程安全实现方式：

• ConcurrentHashMap：

  • 在 JDK 1.7 中、通过分段锁（Segment）机制、每个段拥有独立的锁。

  • 在 JDK 1.8 中、摒弃了 Segment 的概念、改为对每个桶使用 synchronized 和 CAS（进行细粒度控制、仅在冲突时对单个桶加锁、进一步提高了并发度和性能。

• Hashtable：

  • 采用单一的锁机制（即在所有公共方法上都使用 synchronized）、导致任何一个线程操作时都会阻塞其他线程、无论是读还是写、都存在严重的锁竞争、性能明显低于 ConcurrentHashMap。

• ✅ 3. 是否支持 null 键值

• Hashtable：

  • 不允许 null 键和 null 值、调用会抛 NullPointerException。

• ConcurrentHashMap：

  • 也不允许 null 键或 null 值（为了避免在并发场景中、无法判断返回值是 key 不存在还是 value 为 null）。

  • 相比之下、HashMap 是允许一个 null key 和多个 null value 的

19. ConcurrentHashMap的key、value是否可以为null?

参考回答：

• 答：不行。如果key或者value为null会抛出空指针异常。

• （原因是因为没办法解决get返回值为null时的二义性问题、即没办法确定是存储的值本身为null、还是说值不存在）

• 注意：HashMap允许使用null作为值和键。

• （因为HashMap只能单线程下使用、所以hashmap可以用containsKey来二次判断、排除二义性问题）