1. HashMap 的基本特点

在 Java 中，HashMap<K, V> 是基于 数组 + 链表 + 红黑树 结构的 键值映射 容器，具备以下特点：

• 键值对存储 (key-value)
• Key 不能重复
• 支持 null 作为键和值
• 不保证插入顺序
• 非线程安全

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import java.util.HashMap;

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Orange", 3);

        System.out.println("获取 Apple 的值: " + map.get("Apple"));
        System.out.println("是否包含 Key 'Banana': " + map.containsKey("Banana"));
        System.out.println("所有键值对: " + map);
    }
}

2. HashMap 的数据结构

JDK 1.7：数组 + 链表

1
2
3
4
5

class Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
}

• 采用数组+链表存储数据
• 哈希冲突时使用 链表 解决
• 扩容时 重新计算索引（rehash），使用 头插法

JDK 1.8：数组 + 链表 + 红黑树

1
2
3
4
5
6

class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

• 链表长度 ≥ 8 时，转换为红黑树
• 扩容时 使用 尾插法 避免死循环

示例代码

1
2
3
4
5
6
7
8
9
10
11

import java.util.HashMap;

public class HashMapStructure {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        for (int i = 0; i < 20; i++) {
            map.put(i, "Value " + i);
        }
        System.out.println(map);
    }
}

为什么要使用红黑树？

1. 二叉查找树（Binary Search Trees） BST
   

1、每个节点最多只能有两个子节点；
2、左子树的键值小于根的键值（hash值），右子树的键值大于等于
根的键值；
3、对二叉查找树的节点进行查找时，深度为1的节点查找次数为1， 深度为2节点查找次数为2，深度为3的节点查找次数为3，深度为n的节点查找次数为n，因此查找时间复杂度依赖于节点深度，如果节点很深，则查找效率降低；
4、极端情况下，如果键值是顺序增大的，则二叉查找树“退化”为像链表的结构；
5、二叉查找树的查找时间复杂度为O(logn)，但是如果树退化为链表， 则查找时间复杂度为O(n)。

2. 平衡二叉树（Balanced Binary Trees） AVL
   

1、平衡二叉查找树（AVL树）在满足二叉查找树的条件下，还需满足任何节点的两个 子树的高度最大差为1，所以它呈现出是一种左右平衡的状态；（height <=1）
2、是强平衡， 自平衡的
3、平衡二叉树的查找时间复杂度为O(logn)，但是平衡二叉树的插入和删除操作比较复杂，因为插入和删除操作可能会破坏树的平衡，所以在插入和删除操作时，需要通过旋转操作来保持树的平衡。

3. 红黑树（Red-Black Trees）
   

1、每个节点要么是红的要么是黑的；
2、根节点和叶节点（叶节点即指树尾端NIL节点）都是黑的；
3、如果一个结点是红的，那么它的两个子节点都是黑的（不可能连续两个红色节点，但是可以连续两个黑色节点）；
4、任意节点到叶节点的链路中都包含相同数目的黑节点；

4. 红黑树 vs. AVL 树

   比较维度	红黑树（Red-Black Tree）	AVL 树（Balanced Binary Search Tree）
   平衡性	弱平衡（最多偏差 2 倍）	强平衡（左右子树高度差最多 1）
   插入/删除性能	更快，旋转次数少	较慢，插入删除时可能频繁调整
   查询性能	比 AVL 略差，O(log n)	更优，树高更低，O(log n)
   旋转次数	较少（最多 3 次旋转）	较多（最多 5 次旋转）
   适用场景	插入/删除频繁的场景	查找密集的场景
   HashMap 选择	是 HashMap 采用的方案	未被 HashMap 采用

红黑树适用于 HashMap 的原因
1、插入/删除高效：红黑树的旋转次数 少 于 AVL 树，适合频繁插入、删除的场景。
2、较好的平衡性：红黑树保持 “弱平衡”，性能相对稳定，不会变成 退化链表。
3、维护成本低：AVL 需要频繁旋转和调整，而红黑树的调整 更少，插入/删除开销更小。
4、避免 Hash 冲突导致的性能下降：链表结构容易形成“链式”结构，红黑树可以在 链表过长时自动转换，保持查询高效。

5. 红黑树 vs. AVL 树：旋转示例

红黑树插入旋转示例

1
2
3
4
5
6
7

// 假设插入顺序：5 → 10 → 15 → 20 → 25
// 旋转过程（最多 3 次调整）：
   10
  /  \
 5   20
    /  \
   15  25

AVL 树插入旋转示例

1
2
3
4
5
6
7

// 假设插入顺序：5 → 10 → 15 → 20 → 25
// AVL 树为了强平衡，可能需要 5 次调整：
       15
      /  \
     10   20
    /       \
   5        25

红黑树的旋转 次数更少，维护成本更低，适合 高频插入/删除 的场景，因此 HashMap 采用了红黑树。

3. HashMap 的核心参数

示例

1

HashMap<String, Integer> map = new HashMap<>(32, 0.5f);

• 初始容量 = 32
• 负载因子 = 0.5
• 当元素数量超过 32 × 0.5 = 16 时扩容

4. HashMap 的哈希冲突与红黑树优化

JDK 1.8 及以上

• 链表长度 ≥ 8 且数组长度 ≥ 64 转换为 红黑树
• 链表长度 ≤ 6 退化回 链表

5. HashMap 在多线程下的问题

• 死循环导致 CPU 100%
• 并发 put() 可能导致数据丢失
• 并发 get() 可能返回 null

6. ConcurrentHashMap 底层实现详解（JDK 1.7 vs JDK 1.8）

1. JDK 1.7 ConcurrentHashMap 设计

(1) 数据结构

• Segment 数组 + HashEntry 数组 + 链表
• Segment[] 类似 分段 HashMap
• Segment 继承 ReentrantLock，实现 分段锁
• 每个 Segment 维护一个 HashEntry[]，用于存储键值对

(2) 线程安全实现

• 分段锁（Segment）：默认 16 把锁，每把锁负责一部分数据
• 每个 Segment 操作互不影响
• 并发写入时锁住 Segment，而不是整个 Map
• 默认支持 16 个线程同时 put 操作

(3) 存在的问题

1. Segment 过多时，锁竞争依然存在
2. 需要 Segment[] 结构，导致内存浪费
3. 扩容时需要对整个 Segment 进行重新哈希

2. JDK 1.8 ConcurrentHashMap 设计

(1) 数据结构

• Node 数组 + 链表 + 红黑树
• 不再使用 Segment，改为 Node[] 直接存储数据
• 链表长度 ≥ 8 转换为红黑树，优化查询效率
• 支持更高的并发度

(2) 线程安全实现

• CAS（Compare-And-Swap） + volatile 保证可见性
• synchronized 代替 ReentrantLock
• 扩容时，采用并发迁移，避免阻塞所有线程

3. JDK 1.7 vs JDK 1.8 的区别

4. 为什么 JDK 1.8 取消了 Segment？

1. 简化数据结构，减少内存开销
2. 避免 Segment 竞争问题，提高并发性能
3. 利用 CAS + synchronized，比 ReentrantLock 更高效
4. 红黑树优化查询，减少链表遍历的时间复杂度

总结

• JDK 1.7 采用 分段锁（Segment + ReentrantLock），支持高并发但扩容成本高
• JDK 1.8 采用 CAS + synchronized + 红黑树，结构更简洁，性能更优
• 扩容机制 也优化，避免了 Segment 级锁导致的性能瓶颈
• Hash 冲突优化：当链表长度超过 8，转换为 红黑树，查询更快