HashMap和ConcurrentHashMap介绍

HashMap 是 Java 集合框架中一个非常重要的数据结构，它基于哈希表实现，用于存储键值对（Key-Value）。它允许使用 null 作为键（最多一个）和值（可以多个）。HashMap 的主要特点是能够以接近 O(1) 的平均时间复杂度进行插入、删除和查找操作。但是，HashMap 是非线程安全的。

HashMap 底层实现

HashMap 的底层数据结构在不同的 Java 版本中有所演进，但核心思想是“数组 + 链表/红黑树”。

JDK 1.7 及之前：数组 + 链表
1. 基本结构：内部维护一个 Entry 类型的数组（table）。每个 Entry 对象包含四个部分：key、value、hash 值以及一个指向下一个 Entry 的 next 指针。
2. put (存入) 过程：
  - 当一个键值对 (key, value) 被存入时，首先计算 key 的 hashCode()。
  - 通过一个扰动函数对 hashCode 进行再处理，以减少哈希冲突。
  - 将处理后的哈希值与数组长度减一进行按位与运算 (hash & (length - 1))，得到该键值对应在数组中的索引位置（index）。
  - 如果该位置（bucket）上没有元素，则直接创建一个新的 Entry 节点存入。
  - 如果该位置已经有元素（即发生哈希冲突），则遍历该位置上的链表：
    - 如果找到一个节点的 key 与要存入的 key 相同（通过 hashCode 和 equals() 判断），则用新的 value 覆盖旧的 value。
    - 如果遍历完链表都没有找到相同的 key，则创建一个新的 Entry 节点，并采用“头插法”将其插入到链表的头部。
3. 扩容 (resize)：
  - 当 HashMap 中存储的元素数量超过 容量 * 加载因子 (默认为 16 * 0.75 = 12) 时，会触发扩容。
  - 会创建一个新的、容量是原来两倍的数组。
  - 然后遍历旧数组中的所有 Entry，重新计算它们在新数组中的索引位置，并将其迁移过去。这个过程被称为 rehash。
JDK 1.8 及之后：数组 + 链表 + 红黑树
1. 结构优化：为了解决哈希冲突严重时，链表过长导致查询性能下降到 O(n) 的问题，JDK 1.8 引入了红黑树。
2. put 过程变化：
  - 基本流程与 JDK 1.7 类似，但当同一个索引位置的链表长度达到一个阈值（默认为 8）时，并且数组的总容量大于等于 64，这条链表就会被转换成红黑树。
  - 红黑树是一种自平衡的二叉查找树，其查询、插入、删除的时间复杂度稳定在 O(log n)，极大地提高了在哈希冲突严重情况下的性能。
  - 如果后续操作导致红黑树的节点数减少到一定阈值（默认为 6），它会退化回链表。
3. 插入方式：JDK 1.8 将头插法改为了尾插法，这主要是为了避免在多线程扩容时产生循环链表的问题。

HashMap 的线程不安全问题

HashMap 在多线程环境下使用时，会出现以下主要问题：

数据覆盖：如果多个线程同时对同一个索引位置进行 put 操作，没有锁机制保护，后一个线程的写入可能会覆盖前一个线程的写入，导致数据丢失。
JDK 1.7 中的死循环（最著名的问题）：
- 问题根源：扩容 (resize) 过程中的 rehash 操作 + 头插法。
- 发生过程：假设有两个线程（T1 和 T2）同时检测到需要扩容并都执行了 resize 操作。
- T1 在执行迁移时，可能会因为时间片用完而挂起。它已经处理了链表中的一部分节点。
- T2 此时开始执行 resize，它会完成整个迁移过程。
- 当 T1 重新获得 CPU 时间片后，它会继续从它上次挂起的地方开始迁移。由于 T2 已经改变了链表的结构，T1 使用旧的指针关系继续迁移，会导致链表中的某些节点形成一个环形结构。
- 此后，当任何线程（包括 T1）尝试 get 一个位于这个环形链表中的 key 时，就会陷入无限循环，导致 CPU 使用率 100%。
JDK 1.8 中的数据丢失：
- 虽然 JDK 1.8 改用尾插法解决了扩容时的死循环问题，但仍然存在其他线程不安全问题。
- 例如，在 put 操作中，if (tab[i] == null) 这个判断和真正写入 tab[i] = newNode(...) 这两步操作不是原子的。
- 场景：线程 A 和线程 B 同时向一个为 null 的桶（bucket）中 put 元素。
- 线程 A 判断 tab[i] 为 null，然后挂起。
- 线程 B 判断 tab[i] 为 null，成功插入一个新节点。
- 线程 A 恢复执行，它依然认为 tab[i] 是 null，于是也插入一个新节点，这样就会覆盖掉线程 B 插入的节点，导致数据丢失。

ConcurrentHashMap

ConcurrentHashMap 是 java.util.concurrent 包下的一个类，是 HashMap 的线程安全版本。它提供了比 Hashtable 和 Collections.synchronizedMap() 更高的并发性能。它允许多个线程同时读写集合，而不会导致数据不一致或抛出异常。

线程安全的实现原理

ConcurrentHashMap 的线程安全实现也经历了重要的版本迭代。

JDK 1.7：分段锁 (Segment Locking)
1. 基本结构：ConcurrentHashMap 内部由一个 Segment 数组和一个 HashEntry 数组组成。Segment 本身继承自 ReentrantLock，可以看作是一个小的、线程安全的 HashMap。
2. 分段思想：整个 ConcurrentHashMap 被分成多个 Segment（默认 16 个）。当一个线程需要对某个数据进行操作时，它不是锁定整个 Map，而是先定位到数据所在的 Segment，然后只锁定那一个 Segment。
3. 如何工作：
  - put 操作：先通过哈希值定位到具体的 Segment，然后对该 Segment 加锁。加锁成功后，再执行与 HashMap 类似的 put 操作。由于锁只作用于单个 Segment，其他线程可以同时访问并修改其他 Segment 中的数据，从而实现了并发。Segment 的数量被称为“并发度”。
  - get 操作：get 操作大部分时候是不需要加锁的。HashEntry 中的 value 和 next 指针都使用 volatile 关键字修饰，这保证了内存可见性。当一个线程修改了某个 value 后，其他线程能够立即看到这个修改，从而可以安全地读取。只有在读取到的值为 null 时，才会尝试加锁来保证获取到最新的值。
  - size 操作：计算 size 时，会先尝试不加锁地累加两次所有 Segment 的 count 值。如果两次结果一致，就直接返回。如果不一致，则会依次锁住所有的 Segment 来进行精确计算。
4. 优点：通过将锁的粒度从整个 Map 缩小到一个 Segment，大大提高了并发访问的效率。
5. 缺点：分段锁的实现相对复杂，且在某些场景下（例如 size() 操作）的开销较大。
JDK 1.8 及之后：CAS + synchronized
1. 基本结构：摒弃了 Segment 的设计，回归到与 JDK 1.8 中 HashMap 类似的“数组 + 链表 + 红黑树”的结构。
2. 锁粒度更细：锁的粒度进一步降低，从锁定一个 Segment 缩小到只锁定数组中某个具体的索引位置（bucket）。
3. 实现方式：
  - CAS (Compare-And-Swap)：在很多关键操作中，都使用了 CAS 这种无锁算法。例如，在向一个为 null 的 bucket 中添加第一个节点时，会使用 CAS 操作来尝试写入。如果 CAS 成功，说明没有竞争，操作完成。如果失败，说明有其他线程已经占用了该位置，则会进入下一步的同步逻辑。
  - synchronized：当 CAS 操作失败，或者需要修改的 bucket 中已经存在节点（链表或红黑树的头节点）时，就会使用 synchronized 关键字锁住这个头节点。
  - put 操作流程：
    1. 计算哈希值，定位到数组的索引位置。
    2. 如果该位置为 null，使用 CAS 尝试插入新节点。成功则返回。
    3. 如果该位置不为 null，则使用 synchronized 锁住该位置的头节点。
    4. 在同步块内，遍历链表或红黑树，判断是更新 value 还是在末尾添加新节点。
    5. 这个过程中，其他线程如果也想操作同一个 bucket，就会因为获取不到 synchronized 锁而阻塞。但如果它们操作的是不同的 bucket，则完全不受影响，可以并发执行。
4. 优点：
  - 锁粒度更小：只在发生哈希冲突时才加锁，并且锁定的只是单个 bucket 的头节点，并发性能更高。
  - 实现更简洁：相比分段锁，实现逻辑更清晰。
  - 更好的性能：在大多数情况下，尤其是在高并发场景下，性能优于 JDK 1.7 的版本。