HashMap与HashTable，ConcurrentHashMap的区别是什么？

### HashMap、Hashtable 和 ConcurrentHashMap 的区别 ### 1. 线程安全性 - **HashMap**：非线程安全。在多线程环境下，多个线程可能会覆盖彼此的数据，导致数据不一致。 - **Hashtable**：线程安全，通过 `synchronized` 修饰方法来实现，保证在多线程环境下安全，但会阻塞其他线程的访问，影响性能。 - **ConcurrentHashMap**：线程安全。在 JDK 1.7 中使用分段锁（Segment）将哈希表分为多个分段，每个分段独立加锁，细化了锁的粒度。在 JDK 1.8 中，分段锁被 CAS 操作和 `synchronized` 代替，将锁粒度降低到单个桶，进一步提升了并发性能。 ### 2. 继承关系 - **HashMap**：继承自 `AbstractMap`，实现了 `Map` 接口。 - **Hashtable**：继承自 `Dictionary`（已废弃类），是历史遗留类，具有 `Map` 的功能但不建议使用。 - **ConcurrentHashMap**：继承自 `AbstractMap`，实现了 `ConcurrentMap` 接口，提供更细粒度的并发控制，是并发环境下推荐的线程安全 `Map` 实现。 ### 3. 是否允许 null 值 - **HashMap**：允许 `key` 和 `value` 为 `null`。如果 `key` 为 `null`，则计算哈希值为 0，并将其存储在数组的第一个位置。 - **Hashtable**：不允许 `key` 和 `value` 为 `null`。插入 `null` 值会抛出 `NullPointerException`，因为 `null` 无法参与哈希计算。 - **ConcurrentHashMap**：不允许 `key` 和 `value` 为 `null`。这是为了避免并发环境下由于 `null` 值引发的不确定性。 ### 4. 默认初始容量和扩容机制 - **默认初始容量**： - `HashMap` 和 `ConcurrentHashMap` 的默认容量为 16。 - `Hashtable` 默认容量为 11。 - **扩容机制**： - **HashMap**：当元素个数超过 75% 时，扩容为原容量的两倍。 - **Hashtable**：扩容为原容量的两倍加 1，以保持容量为素数。 - **ConcurrentHashMap**：同样扩容为原容量的两倍，但使用分段锁机制，每个分段独立扩容。 ### 5. 遍历时的实现和一致性保障 - **HashMap**：使用 `EntrySet` 进行遍历，支持 `fail-fast` 机制，即在遍历过程中如果结构发生修改（如添加或删除元素），会抛出 `ConcurrentModificationException`。 - **Hashtable**：使用 `Enumeration` 进行遍历，同样支持 `fail-fast`，会检测并发修改并抛出 `ConcurrentModificationException`。 - **ConcurrentHashMap**：遍历使用 `EntrySet`、`KeySet`、`Values` 等提供弱一致性，支持遍历过程中读取最新数据而不抛出异常，但可能出现数据不一致的情况，因为没有对全表加锁，仅保证弱一致性。 ### 6. 执行效率 - **HashMap**：无锁，单线程环境下执行效率最高。 - **ConcurrentHashMap**：在 JDK 1.7 中使用分段锁，并在 JDK 1.8 中改为 CAS 操作结合 `synchronized` 锁，使并发性能大幅提升。 - **Hashtable**：每个方法都加 `synchronized` 锁，导致单一线程操作，效率最低。 ### 总结 | 特性/集合类 | HashMap | Hashtable | ConcurrentHashMap | |---------------------------|----------------------------|-------------------------|-------------------------------------| | **线程安全性** | 否 | 是，基于方法锁 | 是，基于 CAS + synchronized 实现 | | **继承关系** | AbstractMap | Dictionary | AbstractMap, ConcurrentMap | | **允许 null 值** | `key` 和 `value` 均允许 | `key` 和 `value` 均不允许 | `key` 和 `value` 均不允许 | | **默认初始容量** | 16 | 11 | 16 | | **默认加载因子** | 0.75 | 0.75 | 0.75 | | **扩容后容量** | 原来的两倍 | 原来的两倍加1 | 原来的两倍 | | **遍历时支持 fail-fast** | 支持 | 支持 | 部分支持，提供弱一致性 |

### 1. 底层数据结构 - **HashMap**：采用**数组 + 链表 + 红黑树**结构。当键的哈希值冲突时，使用链表存储冲突的键值对；如果链表长度超过阈值（8），则转换为红黑树，提升查找效率。 - **ConcurrentHashMap**：采用和 `HashMap` 一样的**数组 + 链表 + 红黑树**结构，使用 `volatile` 修饰数组，以保证线程的可见性。 - **Hashtable**：使用**数组 + 链表**结构。当冲突发生时，通过链地址法形成链表，但不会转换为红黑树。 ### 2. 线程安全 - **HashMap**：非线程安全，多个线程可能同时修改导致数据不一致。 - **ConcurrentHashMap**：线程安全，采用**CAS + synchronized**保证安全性。CAS 实现元素的无锁插入，`synchronized` 锁住链表头节点，以控制冲突解决。 - **Hashtable**：线程安全，所有方法使用 `synchronized`，在多线程访问时性能较低。 ### 3. 执行效率 - **HashMap**：非线程安全，在单线程环境下执行效率最高。 - **ConcurrentHashMap**：使用细粒度锁，性能次于 `HashMap`，但在多线程环境中效率优于 `Hashtable`。 - **Hashtable**：由于对整个表加锁，多线程访问性能最低。 ### 4. 是否允许 `null` 值 - **HashMap**：允许 `key` 和 `value` 为 `null`。若 `key` 为 `null`，则存储在数组的第一个位置。 - **ConcurrentHashMap**：不允许 `key` 和 `value` 为 `null`，若插入 `null` 会抛出 `NullPointerException`。 - **Hashtable**：不允许 `key` 和 `value` 为 `null`，若插入 `null` 会抛出 `NullPointerException`。 ### 5. 初始容量及扩容 - **默认初始容量**：`HashMap` 和 `ConcurrentHashMap` 默认初始容量为 **16**，`Hashtable` 为 **11**。 - **指定初始容量**：`HashMap` 和 `ConcurrentHashMap` 会调整到大于指定容量的最小 2 的幂次方，`Hashtable` 直接使用指定值。 - **扩容机制**：`HashMap` 和 `ConcurrentHashMap` 扩容倍数为 **2 倍**，`Hashtable` 扩容为 **2N+1**。 ### 6. 哈希值计算 - **HashMap** 和 **ConcurrentHashMap**：使用 `hash(key) ^ (hash >>> 16)` 对哈希值进行扰动，减少冲突的同时避免频繁的链表或红黑树转换。 - **Hashtable**：通过 `hash % length` 计算数组下标，并且采用素数大小（如初始容量 11）作为数组长度，来增强哈希值分布的均匀性，降低冲突率。