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

以下是 `HashMap`、`Hashtable` 和 `ConcurrentHashMap` 的详细对比分析，从底层数据结构、线程安全性、执行效率、是否允许 `null` 值、初始容量及扩容、以及 `hash` 值计算六个方面进行阐述。 ### 1. 底层数据结构 - **HashMap** - 数据结构：`数组 + 链表 + 红黑树` - `HashMap` 的底层是一个数组，每个数组元素是一个链表的头结点。当链表长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。当链表长度小于6时，红黑树会转换回链表。 - **ConcurrentHashMap** - 数据结构：`数组 + 链表 + 红黑树` - 与 `HashMap` 类似，`ConcurrentHashMap` 也使用数组、链表和红黑树来组织数据。它使用 `volatile` 关键字修饰其属性，确保内存可见性，以支持并发操作。 - **Hashtable** - 数据结构：`数组 + 链表` - `Hashtable` 的底层结构与 `HashMap` 类似，但它没有将链表转换为红黑树的机制。这使得在高冲突的情况下，`Hashtable` 的性能会有所下降。 ### 2. 线程安全 - **HashMap** - **非线程安全** - 在多线程环境下使用 `HashMap` 可能导致数据不一致的情况，比如当多个线程同时插入键值对时，如果发生哈希冲突，可能导致链表中的节点被覆盖。 - **Hashtable** - **线程安全** - `Hashtable` 使用 `synchronized` 关键字修饰大多数方法，确保每次只有一个线程可以对 `Hashtable` 进行操作。然而，这种机制导致了较大的性能开销。 - **ConcurrentHashMap** - **线程安全** - `ConcurrentHashMap` 通过 CAS 操作（Compare-And-Swap）和 `synchronized` 锁来确保线程安全。CAS 操作确保在数组下标为空时能原子性地插入新节点，而 `synchronized` 锁则用于处理链表或红黑树中的节点操作。 ### 3. 执行效率 - **HashMap** - 执行效率较高，因为它是非线程安全的，操作没有锁机制的开销。 - **ConcurrentHashMap** - 执行效率次之，通过分段锁机制（Java 8 后改为 CAS 操作）减少了锁的粒度，在高并发环境下性能优越。 - **Hashtable** - 执行效率最低，因为 `Hashtable` 对整个对象加锁，所有线程在同一时间只能有一个线程操作 `Hashtable`。 ### 4. 是否允许 `null` 值 - **HashMap** - `HashMap` 允许 `key` 和 `value` 为 `null`。`key` 为 `null` 的键值对会被存储在数组的第一个位置。 - **Hashtable** - `Hashtable` 不允许 `key` 和 `value` 为 `null`。如果尝试插入 `null` 值，会抛出 `NullPointerException`。 - **ConcurrentHashMap** - 与 `Hashtable` 一样，`ConcurrentHashMap` 不允许 `key` 和 `value` 为 `null`，否则会抛出 `NullPointerException`。 ### 5. 初始容量及扩容 - **不指定初始容量** - `HashMap` 和 `ConcurrentHashMap` 的默认初始容量为 16。 - `Hashtable` 的默认初始容量为 11。 - **指定初始容量** - `HashMap` 和 `ConcurrentHashMap` 会调整容量为最接近的 2 的幂次方，而 `Hashtable` 则直接使用指定的初始容量。 - **扩容** - `HashMap` 和 `ConcurrentHashMap` 的扩容方式是容量加倍（2N）。 - `Hashtable` 扩容为 `2N + 1`，以确保数组的长度始终为素数。 ### 6. `hash` 值计算 - **HashMap 和 ConcurrentHashMap** - 通过将 `key` 的 `hashCode()` 高 16 位和低 16 位进行异或运算来计算 `hash` 值，以保留高位特征并减少冲突。然后通过 `hash & (n - 1)` 计算数组下标（`n` 为数组长度）。 - **Hashtable** - `Hashtable` 使用 `key.hashCode()` 直接取模数组长度来计算数组下标。由于数组长度为素数，这样可以使得 `hash` 值的分布更均匀。