HashMap和HashTable和ConcurrentHashMap详解（面试八股）

HashMap

JDK7的实现

// JDK7: 数组 + 链表
Entry<K,V>[] table;
static class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> next;
    int hash;
}

JDK8的实现

// JDK8: 数组 + 链表 + 红黑树
Node<K,V>[] table;
static class Node<K,V> {
    K key;
    V value;
    Node<K,V> next;
    int hash;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    boolean red;
    //    K key;
    //    V value;
    //    Node<K,V> next;
	//    int hash;
}

主要区别

1. 数据结构：

   • JDK7：数组 + 链表
   • JDK8：数组 + 链表 + 红黑树

2. 链表转换：

   • JDK8中，当链表长度超过8时，会转换为红黑树
   • 当红黑树节点数小于6时，会转回链表
   • 树化条件：容量不大于等于64不会进行树化，而是扩容来解决hash冲突

3. 性能优化：

   • JDK8引入红黑树是为了优化链表过长导致的查询性能下降
   • 链表查询时间复杂度O(n)
   • 红黑树查询时间复杂度O(log n)
   • 红黑树占用空间更大
   • 当数据量小时，链表性能更好

4. 插入方式：

   • JDK7：头插法（容易形成环形链表）
   • JDK8：尾插法（解决并发环形链表问题）

基本共有结构

// 核心成员变量
Node<K,V>[] table;     // 哈希桶数组
int threshold;         // 扩容阈值
float loadFactor;      // 负载因子（默认0.75f）
int size;             // 实际元素个数

1. 初始容量为什么必须是2的幂？

**初始容量（默认16）**是HashMap底层数组的长度，必须为2的幂，原因如下：

2. 负载因子（Load Factor）0.75的作用

负载因子是扩容阈值计算的依据，表示哈希表空间利用率与性能的平衡。

实验数据：

• 负载因子=0.75时，哈希冲突的概率约为6%（基于泊松分布），综合性能最优。
• 若设为0.5，扩容频繁（内存浪费）；若设为1.0，冲突严重（链表长，查询慢）。

3. 最小树化容量（MIN_TREEIFY_CAPACITY）64的意义

最小树化容量64表示：只有当哈希表容量≥64时，单个桶的链表长度超过8才会转为红黑树。

示例：

// 初始容量16，插入第9个元素到同一桶
if (size >= 8 && capacity < 64) {
    resize(); // 扩容到32，再尝试分散节点
} else if (size >= 8 && capacity >= 64) {
    treeifyBin(); // 转为红黑树
}

4. 树化与链化阈值（8和6）的设计依据

头插法造成环形链表

![[Pasted image 20250417084926.png]]
![[Pasted image 20250417084937.png]]
这个时候t2苏醒再次扩容就会造成环形链表
![[Pasted image 20250417085035.png]]

/**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
         //获取新的table的长度（扩容后的table）
        int newCapacity = newTable.length;
        //遍历旧的table
        for (Entry<K,V> e : table) {
            while(null != e) {
               // 重新计算原table中的数据在新数组的索引位置，并用头插法进行扩容
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

注意事项

• 非线程安全
• key可以为null
• value可以为null
• 不保证顺序
• 扩容会重新散列

HashTable

基本特性

Hashtable<K,V> table = new Hashtable<>();

• 线程安全（方法都使用synchronized修饰）
• 不允许null键和null值（会抛出NullPointerException()异常）
• 默认初始容量11，负载因子0.75
• 扩容方式：(原容量 * 2 + 1)

1. 初始容量为什么不是 2 的幂次方？

Hashtable 的设计

• Hashtable 的默认初始容量是 11，这是一个质数，而不是 2 的幂次方。
• 选择质数作为初始容量的主要原因是为了减少哈希冲突的概率。质数在取模运算中能够更均匀地分布键值对，即使哈希函数的分布不理想。

HashMap 的设计

• HashMap 的默认初始容量是 16，这是 2 的幂次方。
• 使用 2 的幂次方作为容量的原因是优化性能：HashMap 在计算索引时使用了位运算（& 操作符），而不是取模运算（%）。对于 2 的幂次方容量，位运算可以更快地计算索引位置：

  index = hash(key) & (capacity - 1)
  

  这种优化在性能敏感的场景下非常有效。

2. 为什么 Hashtable 不允许 null 键和 null 值？

Hashtable 的设计

• Hashtable 不允许插入 null 键或 null 值。如果尝试插入 null，会抛出 NullPointerException。
• 这是因为 Hashtable 是 Java 早期版本（JDK 1.0）引入的集合类，当时的设计决策是严格的类型检查和避免潜在的空指针异常。

HashMap 的设计

• HashMap 允许一个 null 键和多个 null 值。
• 这是因为 HashMap 是在 JDK 1.2 引入的，它的设计更加灵活，允许开发者根据需要处理 null。

具体原因

1. 线程安全性

   • Hashtable 是线程安全的，所有方法都用 synchronized 修饰。如果允许 null 键或值，可能会导致多线程环境下的歧义。例如：
     • 如果某个键的值为 null，无法区分是因为该键不存在还是因为该键的值确实是 null。
   • 而 HashMap 是非线程安全的，开发者可以在单线程环境下自行处理 null 的逻辑。

2. 历史背景

   • Hashtable 的设计早于 HashMap，当时的编程风格更倾向于严格的类型检查，避免潜在的错误。
   • HashMap 的设计更加现代化，提供了更大的灵活性。

3. 一致性

   • Hashtable 的设计目标是提供一种严格且安全的集合类，因此不允许 null 键或值以避免歧义。
   • HashMap 的设计目标是提供一种高效且灵活的集合类，因此允许 null。

总结

• Hashtable是旧版本的同步Map实现
• 现代开发中已较少使用，除非是维护老项目
• 需要线程安全时推荐使用ConcurrentHashMap
• 单线程环境使用HashMap性能更好

ConcurrentHashMap

基本特性

ConcurrentHashMap<K,V> map = new ConcurrentHashMap<>();

• 线程安全
• 支持高并发
• 不允许null键和null值
• 默认初始容量16，负载因子0.75

一、JDK7 的锁机制：分段锁（Segment）

1. 核心设计

• 数据结构：采用 Segment 数组 + HashEntry 数组 + 链表 结构。每个 Segment 继承自 ReentrantLock，内部维护一个 HashEntry 数组，每个 HashEntry 是一个链表节点。
• 分段锁：将整个哈希表划分为多个 Segment（默认 16 个），每个 Segment 独立加锁。不同线程可同时操作不同的 Segment，并发度为 Segment 的数量。

2. 线程安全实现

• 写操作：对目标 Segment 加锁（ReentrantLock），其他 Segment 不受影响。例如 put 方法中，线程需先获取 Segment 锁，再进行插入或更新。
• 读操作：无需加锁，通过 volatile 修饰的 HashEntry 字段（value 和 next）保证可见性。

3. 优缺点

• 优点：相比 Hashtable 的全表锁，分段锁显著提升并发性能（默认并发度 16 倍）。
• 缺点：
  • 锁粒度较粗，同一 Segment 内的不同桶仍需竞争同一锁。
  • 扩容仅针对单个 Segment，无法跨段协同。

二、JDK8 的锁机制：CAS + synchronized

1. 核心设计

• 数据结构：采用 数组 + 链表/红黑树，取消 Segment 设计。链表长度 ≥8 且数组长度 ≥64 时，链表转为红黑树，查询效率从 O(n) 提升至 O(logn)。
• 锁粒度：锁定单个桶（数组元素）的头节点，锁粒度更细，冲突概率更低。

2. 线程安全实现

• CAS 无锁化：

  • 空桶插入：当桶为空时，使用 CAS 操作（casTabAt）原子性地插入新节点，避免加锁开销。
  • 状态标记：通过 volatile 变量（如 sizeCtl）控制初始化、扩容等操作，结合 CAS 实现多线程协作。

• synchronized 锁：

  • 非空桶操作：当桶非空时，对头节点加 synchronized 锁，处理链表或红黑树的插入、更新、删除等操作。
  • 扩容协同：扩容期间，通过 ForwardingNode 标记迁移状态，其他线程可协助迁移数据（多线程并行扩容）。

三、CAS + synchronized 的协同优势

1. 无锁化场景：空桶插入通过 CAS 避免锁竞争，适合低冲突场景。
2. 锁降级设计：仅在必要时（非空桶）使用 synchronized，减少锁持有时间。
3. 高并发扩容：通过 ForwardingNode 和 sizeCtl 状态控制，支持多线程协同扩容，避免阻塞。