✅HashMap、Hashtable和ConcurrentHashMap的区别？默认的初始容量和扩容机制

<think>我们正在讨论HashMap、Hashtable和ConcurrentHashMap的区别，特别是默认初始容量和扩容机制。根据引用内容，我们可以总结如下： 1. **HashMap**: - 默认初始容量：16（引用[2]提到） - 扩容机制：当元素数量超过阈值（容量*负载因子，默认0.75）时，扩容为原来的2倍（即新容量=旧容量*2）。在JDK1.8中，当链表长度超过8且数组长度大于等于64时，链表会转换为红黑树。 2. **Hashtable**: - 默认初始容量：11（引用[2]提到） - 扩容机制：当元素数量超过阈值（容量*负载因子，默认0.75）时，扩容为原来的2倍加1（即新容量=旧容量*2+1）。 3. **ConcurrentHashMap**: - 默认初始容量：16（引用[2]提到） - 扩容机制：在JDK1.7中采用分段锁，扩容时只针对每个段进行；在JDK1.8中，采用CAS和synchronized，扩容时支持多线程协同扩容（即协助扩容），每次扩容为原来的2倍。 此外，我们还需要注意它们在数据结构、线程安全、null值处理等方面的区别： - **线程安全性**：HashMap非线程安全；Hashtable和ConcurrentHashMap是线程安全的，但实现机制不同（Hashtable使用全表锁，ConcurrentHashMap在JDK1.7使用分段锁，在JDK1.8使用CAS+synchronized锁住单个桶）。 - **null值处理**：HashMap允许key和value为null；Hashtable和ConcurrentHashMap不允许（引用[5]解释：Hashtable会进行校验并抛出空指针异常，ConcurrentHashMap不允许是因为并发场景下null值容易引起歧义）。 下面，我们将以表格形式对比三者的区别，并详细说明默认初始容量和扩容机制。 ### 对比表格 | **特性** | **HashMap** | **Hashtable** | **ConcurrentHashMap** | |------------------|-------------------|--------------------|-----------------------------| | **线程安全** | 否 | 是（全表锁） | 是（分段锁/CAS+桶锁） | | **初始容量** | 16 | 11 | 16 | | **扩容机制** | 2倍扩容 | 2倍+1扩容 | 2倍扩容（分段/桶级扩容） | | **负载因子** | 0.75 | 0.75 | 0.75 | | **null值支持** | key和value均可为null | 均不允许 | 均不允许 | | **数据结构** | JDK1.8：数组+链表/红黑树 | 数组+链表 | JDK1.8：数组+链表/红黑树 | | **继承关系** | 继承AbstractMap | 继承Dictionary | 实现ConcurrentMap接口 | ### 详细说明 #### 1. HashMap - **初始容量**：默认16，可以通过构造函数指定（但会自动调整为2的幂次方，因为使用位运算代替取模运算）。 - **扩容机制**：当元素数量超过阈值（容量*负载因子）时，触发扩容。扩容后容量变为原来的2倍，然后重新计算每个元素的位置（重新哈希）。在JDK1.8中，扩容时会将链表拆分成两个链表（高位链表和低位链表），然后分别放入新数组的对应位置。 #### 2. Hashtable - **初始容量**：默认11，可以通过构造函数指定（任意正整数）。 - **扩容机制**：当元素数量超过阈值（容量*负载因子）时，触发扩容。新容量为`2 * 旧容量 + 1`。然后重新计算每个元素的位置（重新哈希）。由于使用全表锁，扩容期间整个表不可用。 #### 3. ConcurrentHashMap - **初始容量**：默认16，可以通过构造函数指定（会自动调整为2的幂次方）。 - **扩容机制**： - **JDK1.7**：使用分段锁（Segment），每个段独立扩容，扩容时只锁定当前段，其他段仍可访问。每个段内的扩容规则类似HashMap（2倍扩容）。 - **JDK1.8**：取消分段锁，采用CAS和synchronized锁住单个桶（链表头节点或红黑树根节点）。扩容时，支持多线程同时协助扩容（通过设置ForwardingNode标记），每个线程负责一部分桶的迁移，迁移完成后，旧桶会被标记为转发节点，新请求会转发到新数组。 ### 扩容机制对比示例 - **HashMap扩容公式**： $$ \text{新容量} = \text{旧容量} \times 2 $$ - **Hashtable扩容公式**： $$ \text{新容量} = \text{旧容量} \times 2 + 1 $$ - **ConcurrentHashMap（JDK1.8）扩容公式**： $$ \text{新容量} = \text{旧容量} \times 2 $$ ### 为什么初始容量不同？ - **HashMap和ConcurrentHashMap**：使用2的幂次方作为容量，因为这样可以通过位运算`(n-1) & hash`快速计算索引，效率远高于取模运算。 - **Hashtable**：使用质数（如11）作为初始容量，因为传统取模运算（`hash % length`）在遇到合数时容易产生哈希冲突，而质数可以减少冲突。但Hashtable的扩容机制（2倍+1）会尽量保持容量为奇数（不一定是质数），以减少冲突。 ### 总结 - **选择建议**： - 单线程环境：使用`HashMap`（性能最优）。 - 低并发读写：使用`Collections.synchronizedMap`包装HashMap。 - 高并发读写：使用`ConcurrentHashMap`（性能最好）。 - 避免使用`Hashtable`（过时且性能差）。 --- ### 相关问题 1. **为什么HashMap的初始容量是2的幂次方？** 2. **ConcurrentHashMap在JDK1.8中如何实现线程安全？** 3. **HashMap在JDK1.8中链表转红黑树的条件是什么？** 4. **Hashtable为什么被弃用？** [^1]:HashMap扩容机制以及和HashTable、ConcurrentHashMap理解 [^2]:分析HashTable、HashMap、ConcurrentHashMap的结构、初始化及扩容机制 [^3]:【Java】HashMap、HashTable和ConcurrentHashMap的区别 [^4]:HashTable·HashMap·ConcurrentHashMap 之间的区别 [^5]:HashMap、HashTable、ConcurrentHashMap 、HashSet、TreeMap、LinkedHashMap</think>### HashMap、Hashtable、ConcurrentHashMap 核心区别对比 #### 一、核心参数对比 | **特性** | **HashMap** | **Hashtable** | **ConcurrentHashMap** | |--------------------|--------------------|--------------------|---------------------------| | **默认初始容量** | 16 | 11 | 16 | | **扩容机制** | 2 倍扩容（$2^n$） | $2 \times \text{旧容量} + 1$ | 分段扩容（桶粒度 CAS） | | **负载因子** | 0.75 | 0.75 | 0.75 | | **扩容触发条件** | 元素数 > 容量 × 负载因子 | 同左 | 同左（分段判断） | | **数据结构** | 数组+链表/红黑树 | 数组+链表 | 数组+链表/红黑树（线程安全）| #### 二、扩容机制详解 1. **HashMap** - 扩容公式：$\text{新容量} = 2 \times \text{旧容量}$ - **优化设计**： 采用 $2^n$ 容量，桶索引计算简化为： $$\text{index} = \text{hash} \& (\text{容量} - 1)$$ 避免昂贵的取模运算（如 `hash % capacity`）[^1][^2] - JDK 1.8 优化：链表长度 > 8 且数组长度 ≥ 64 时，链表转红黑树 2. **Hashtable** - 扩容公式：$\text{新容量} = 2 \times \text{旧容量} + 1$ - **设计缺陷**： 全表锁扩容期间完全阻塞读写操作 初始容量 11 是质数，但扩容后失去质数特性（如 11→23→47）[^2][^4] 3. **ConcurrentHashMap** - **JDK 1.7**：分段锁扩容，每个段独立扩容 - **JDK 1.8**： - CAS + `synchronized` 桶锁 - 多线程协同扩容：线程可协助迁移其他桶的数据 - 扩容公式：$\text{新容量} = 2 \times \text{旧容量}$[^1][^3] #### 三、线程安全与性能对比 | **特性** | **HashMap** | **Hashtable** | **ConcurrentHashMap** | |------------------|-------------|---------------------|----------------------------| | **线程安全** | ❌ 不安全 | ✅ 全表锁（性能差） | ✅ 分段锁/CAS（高性能） | | **并发吞吐量** | - | 基准值 1X | JDK1.7: 5-10X; JDK1.8: 10-20X[^3] | | **Null 值支持** | ✅ Key/Value | ❌ 均禁止 | ❌ 均禁止（避免并发歧义）[^5] | #### 四、工程实践建议 1. **单线程场景** - 首选 `HashMap`（性能最优） 2. **低并发读写** - `Collections.synchronizedMap(new HashMap())` 3. **高并发场景** - JDK ≥ 1.8：必选 `ConcurrentHashMap` - 吞吐量对比： $$T_{\text{ConcurrentHashMap}} \approx 10 \times T_{\text{Hashtable}}$$ 4. **过时方案** - 禁用 `Hashtable`（全表锁导致性能瓶颈）[^4] --- ### 扩容过程图解（以 HashMap 为例） ```mermaid graph LR A[当前状态] -->|元素数 > 12| B[触发扩容] B --> C[创建新数组 32x] C --> D[重新哈希] D --> E[链表拆分为高低位链] E --> F[数据迁移完成] ``` > **哈希计算优化**： > HashMap 通过高位扰动减少冲突： > ```java > hash = (h = key.hashCode()) ^ (h >>> 16) > ``` --- ### 相关问题 1. **为什么 HashMap 初始容量是 16 而 Hashtable 是 11？** （分析 $2^n$ 容量位运算优化 vs 质数取模的哈希分布差异）[^2] 2. **ConcurrentHashMap 在 JDK 1.8 中如何实现多线程协同扩容？** （图解 ForwardingNode 和线程任务分配机制） 3. **HashMap 链表转红黑树的阈值为什么是 8？** （基于泊松分布的概率分析：$P(\text{冲突} \geq 8) < 10^{-6}$） 4. **Hashtable 的 $2n+1$ 扩容策略有何优缺点？** （对比质数分布特性与扩容成本） [^1]:HashMap扩容机制以及和HashTable、ConcurrentHashMap理解 [^2]:分析HashTable、HashMap、ConcurrentHashMap的结构、初始化及扩容机制 [^3]:【Java】HashMap、HashTable和ConcurrentHashMap的区别 [^4]:HashTable·HashMap·ConcurrentHashMap 之间的区别 [^5]:HashMap、HashTable、ConcurrentHashMap 、HashSet、TreeMap、LinkedHashMap