Java集合框架梳理

一、什么是 Java 集合框架？

Java 集合框架是一个统一的、可扩展的体系结构，用于表示和操作集合。它将集合的抽象与具体实现分离，提供了通用的接口、实现类和算法（如排序、搜索），极大地提高了代码的复用性、可读性和可维护性。

在 JCF 出现之前（Java 1.2 之前），开发者需要使用数组、Vector、Hashtable 等结构，这些结构功能单一，且 API 设计不一致。JCF 解决了这些问题。

二、集合框架的核心体系结构

JCF 主要分为两大接口分支：Collection 和 Map。

1. Collection 接口 (单列数据)

存储一组独立的元素。它有三个主要的子接口：

  • List：有序、可重复 的集合。元素都有对应的顺序索引。
  • Set：无序、不可重复 的集合。类似于数学中的“集合”。
  • Queue/Deque：队列 结构，实现了特定的 FIFO（先进先出）或 LIFO（后进先出）等规则。

2. Map 接口 (双列数据，键值对)

存储一组 键值对 (Key-Value) 映射。Key 是不可重复的，每个 Key 最多映射到一个 Value。

三、核心接口和常用实现类简介

1. List 接口

特点：有序（插入顺序）、可重复、可通过索引访问。

  • ArrayList (最常用)

    • 实现：基于动态数组。
    • 特点：
      • 优点：随机访问（通过 get(index)）速度极快，因为底层是数组。
      • 缺点：在列表中间插入或删除元素效率较低（需要移动后续所有元素）。
    • 使用场景：绝大多数需要列表的情况，尤其是查询多、增删少的场景。
    • ArrayList详细介绍

  • LinkedList

    • 实现：基于双向链表。
    • 特点：
      • 优点：在列表头部和尾部进行插入和删除操作效率非常高。同时实现了 Deque 接口，可以作为队列或栈使用。
      • 缺点：随机访问效率低，需要从头或尾遍历链表。
    • 使用场景：需要频繁在首尾增删元素，或者需要实现队列、栈功能时。
    • [LinkedList详细介绍](#4.2 LinkedList详解)

  • Vector (已过时，但需了解)

    • 古老的实现类，基于动态数组。
    • 所有方法都是同步的（Synchronized），是线程安全的，但因此性能开销大。
    • 已被 ArrayList 取代。如需线程安全，可以使用 Collections.synchronizedList(new ArrayList()) 或 CopyOnWriteArrayList。
    • [Vector详细介绍](#4.3 Vector详解)

2. Set 接口

特点：无序（但某些实现有特定顺序，如 TreeSet）、不可重复。判断重复的依据是 equals() 和 hashCode() 方法。

  • HashSet (最常用)

    • 实现：基于 HashMap（本质上是只存储 Key 的 HashMap）。
    • 特点：无序，查询效率非常高（时间复杂度接近 O(1)）。
    • 使用场景：需要快速去重、不关心元素顺序的场景。
    • [HashSet详细介绍](#4.4 HashSet详解)

  • LinkedHashSet

    • 实现：HashSet 的子类，底层使用链表维护次序。
    • 特点：既保证了元素的唯一性，又维护了元素的插入顺序。
    • 使用场景：既需要去重，又希望保留插入顺序的场景。
    • [LinkedHashSet详细介绍](#4.5 LinkedHashSet详解)

  • TreeSet

    • 实现：基于 TreeMap（红黑树）。
    • 特点：元素可以排序（默认自然排序，如整数升序、字符串字典序）或通过提供的 Comparator 进行定制排序。
    • 使用场景：需要对元素进行自动排序的场景。
    • [TreeMap详细介绍](#4.6 TreeMap详解)

3. Queue/Deque 接口

特点：用于处理“排队”模型。

  • PriorityQueue
    • 特点：一个优先级队列，元素根据自然顺序或 Comparator 进行出队（总是出优先级最高的元素）。
    • 实现：通常基于堆（heap）实现。
    • [PriorityQueue详细介绍](#4.7 PriorityQueue详解)
  • LinkedList：也实现了 Deque 接口，因此可以作为双端队列使用。
  • ArrayDeque：基于动态数组实现的双端队列，效率通常比 LinkedList 作为队列使用时更高。[ArrayDeque详细介绍](#4.8 ArrayDeque详解)

4. Map 接口

特点：存储键值对，Key 不允许重复。

  • HashMap (最常用)
    • 实现：数组 + 链表 + 红黑树（JDK 8+）。
    • 特点：无序，允许 null 作为 Key 和 Value。非线程安全。查询、插入、删除的平均时间复杂度为 O(1)。
    • 工作原理（重要）：
      1. 调用 put(key, value) 时，先计算 key 的 hashCode()。
      2. 通过哈希函数计算出数组下标。
      3. 如果该位置为空，直接放入。
      4. 如果不为空（哈希冲突），则依次比较该位置上链表（或树）中每个元素的 hashCode 和 key（通过 equals() 方法）。
      5. 如果找到相同的 key，则覆盖 value。
      6. 如果没找到，则将新键值对添加到链表末尾（或树中）。当链表长度超过阈值（默认为 8）且数组长度大于 64 时，链表会转换为红黑树以提高性能。
    • 使用场景：绝大多数需要键值对存储的场景。
    • [HashMap详细介绍](#4.9 HashMap详解)
  • LinkedHashMap
    • 实现：HashMap 的子类，增加了双向链表。
    • 特点：既保证了 HashMap 的查询效率，又维护了键值对的插入顺序或访问顺序（LRU 算法的基础）。
    • 使用场景：需要保证迭代顺序与插入顺序一致，或实现 LRU 缓存。
    • [LinkedHashMap详细介绍](#4.10 LinkedHashMap详解)
  • TreeMap
    • 实现：基于红黑树。
    • 特点：Key 是排序的。可以根据 Key 的自然顺序或自定义 Comparator 进行排序。
    • 使用场景：需要根据 Key 的顺序进行遍历的场景。
    • [TreeMap详细介绍](#4.11 TreeMap详解)
  • Hashtable (已过时)
    • 古老的实现类。线程安全（方法同步），但性能差。
    • 不允许 null 作为 Key 或 Value。
    • 已被 ConcurrentHashMap 取代。
    • [Hashtable详细介绍](#4.12 Hashtable详解)
  • ConcurrentHashMap
    • 线程安全（分段锁），但性能差。
    • 不允许 null 作为 Key 或 Value。
    • [ConcurrentHashMap详细介绍](#4.13 ConcurrentHashMap详解)

四、常用实现类详解

4.1 ArrayList详解

1. 基础概念和特性

动态数组：ArrayList 的容量可以根据需要动态增长，与传统的数组不同。
有序集合：元素按照插入顺序存储，可以通过索引访问元素。
允许重复元素：可以存储相同的对象多次。
允许 null 值：可以在 ArrayList 中存储 null 元素。
非线程安全：在多线程环境下需要外部同步机制保证线程安全。

ArrayList vs 数组
  • 数组：固定大小，基本数据类型和对象都能存储
  • ArrayList：动态大小，只能存储对象（自动装箱/拆箱）
ArrayList vs LinkedList
特性 ArrayList LinkedList
底层结构 动态数组 双向链表
随机访问 O(1) O(n)
插入/删除（头部/中间） O(n) O(1)
内存占用 较少（连续内存） 较多（存储指针）
2. 底层实现原理
核心字段
1
2
3
4
5
6
// 存储元素的数组
transient Object[] elementData;
// 实际元素个数
private int size;
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
构造方法
1
2
3
4
5
6
7
8
9
10
11
// 无参构造 - 延迟初始化
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 指定容量构造
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    }
}
3. 关键方法实现
add(E e) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean add(E e) {
    // 确保容量足够
    ensureCapacityInternal(size + 1);
    // 添加元素
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 如果是空数组，取默认容量和所需容量的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // 如果所需容量大于当前容量，则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
扩容机制(grow方法)
1
2
3
4
5
6
7
8
9
10
11
12
13
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 扩容为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果1.5倍还不够，直接用所需容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果超过最大数组大小，使用最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
4. 常见面试问题
Q1: ArrayList如何实现动态扩容？

答案要点：

  • 默认容量为10
  • 每次扩容为原容量的1.5倍
  • 使用Arrays.copyOf()进行数组复制
  • 扩容时机：添加元素时发现容量不足
Q2: ArrayList的线程安全问题

答案要点：

  • ArrayList不是线程安全的
  • 多线程环境下可能出现：
    • ConcurrentModificationException
    • 数据不一致问题
  • 解决方案：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 方案1：使用Collections.synchronizedList()
    List<String> list = Collections.synchronizedList(new ArrayList<>());

    // 方案2：使用Vector（性能较差）
    Vector<String> vector = new Vector<>();

    // 方案3：手动加锁
    synchronized(list) {
        list.add("element");
    }
Q3: ArrayList vs Vector
特性 ArrayList Vector
线程安全 否 是
性能 高 低（同步开销）
扩容倍数 1.5倍 2倍
迭代器 fail-fast fail-fast/fail-safe
Q4: fail-fast机制

概念：当多个线程对集合进行结构上的改变操作时，会抛出ConcurrentModificationException

实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
private class Itr implements Iterator<E> {
    int expectedModCount = modCount;
    
    public E next() {
        checkForComodification();
        // ...
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
5. 性能优化建议
初始化容量
1
2
3
4
5
6
7
8
9
10
11
// 不好的做法：频繁扩容
List<String> list = new ArrayList<>();
for(int i = 0; i < 10000; i++) {
    list.add("item" + i);
}

// 好的做法：预设容量
List<String> list = new ArrayList<>(10000);
for(int i = 0; i < 10000; i++) {
    list.add("item" + i);
}
避免在循环中删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 错误做法：可能跳过元素
for(int i = 0; i < list.size(); i++) {
    if(条件) {
        list.remove(i); // 删除后索引发生变化
    }
}

// 正确做法1：倒序遍历
for(int i = list.size() - 1; i >= 0; i--) {
    if(条件) {
        list.remove(i);
    }
}

// 正确做法2：使用Iterator
Iterator<String> it = list.iterator();
while(it.hasNext()) {
    if(条件) {
        it.remove(); // 使用迭代器的remove方法
    }
}
6. 源码重点分析
modCount字段
1
protected transient int modCount = 0;
  • 记录结构修改次数
  • 用于实现fail-fast机制
  • 每次add/remove操作都会增加
transient关键字
1
transient Object[] elementData;
  • 防止序列化整个数组
  • 节省存储空间（只序列化实际元素）
  • 通过writeObject/readObject自定义序列化
7. 实际应用场景
适用场景
  1. 需要频繁通过索引访问元素
  2. 主要在列表尾部进行插入和删除操作
  3. 元素数量大致可预估的场景
不适用场景
  1. 频繁在列表中间插入或删除元素
  2. 多线程并发修改的场景
  3. 对内存使用要求非常严格的场景
8. 高频面试代码题
如何实现一个简单的ArrayList？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class MyArrayList<E> {
    private Object[] elementData;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }
    
    public void add(E e) {
        ensureCapacity();
        elementData[size++] = e;
    }
    
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (E) elementData[index];
    }
    
    private void ensureCapacity() {
        if (size == elementData.length) {
            int newCapacity = elementData.length * 2;
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
}

4.2 LinkedList详解

1. 基本概念

LinkedList 是 Java 集合框架中的一个双向链表实现，它同时实现了 List 接口和 Deque 接口，因此可以作为列表、队列和双端队列使用。

2. 数据结构
Node 节点结构
1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item;        // 节点值
    Node<E> next;  // 后继节点
    Node<E> prev;  // 前驱节点
    
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
核心字段
1
2
3
transient int size = 0;     // 元素个数
transient Node<E> first;    // 头节点
transient Node<E> last;     // 尾节点
3. 与 ArrayList 的对比
特性 ArrayList LinkedList
底层结构 动态数组 双向链表
随机访问 O(1) O(n)
插入/删除（头部/中间） O(n) O(1)
内存占用 较少（连续内存） 较多（额外指针）
缓存友好性 好（局部性原理） 差（节点分散）
4. 核心方法实现
add(E e) - 尾部添加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean add(E e) {
    linkLast(e);  // 链接到尾部
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;  // 如果链表为空，设置为头节点
    else
        l.next = newNode; // 原尾节点的next指向新节点
    size++;
    modCount++;
}
add(int index, E element) - 指定位置添加
1
2
3
4
5
6
7
8
public void add(int index, E element) {
    checkPositionIndex(index);
    
    if (index == size)
        linkLast(element);  // 如果是尾部，直接链接到尾部
    else
        linkBefore(element, node(index));  // 否则插入到指定节点之前
}
get(int index) - 根据索引获取
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // 优化：根据索引位置决定从头还是从尾开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
remove(int index) - 删除指定位置元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    
    if (prev == null) {
        first = next;  // 删除的是头节点
    } else {
        prev.next = next;
        x.prev = null;
    }
    
    if (next == null) {
        last = prev;   // 删除的是尾节点
    } else {
        next.prev = prev;
        x.next = null;
    }
    
    x.item = null;  // 帮助GC
    size--;
    modCount++;
    return element;
}
5. 常见面试问题
Q1: LinkedList 与 ArrayList 的选择场景？

答案要点：

  • ArrayList 适用场景：

    • 频繁通过索引随机访问元素
    • 主要在列表尾部进行插入和删除操作
    • 对内存使用要求较严格

  • LinkedList 适用场景：

    • 频繁在列表中间进行插入和删除操作
    • 需要实现队列、栈等数据结构
    • 不需要频繁随机访问元素
Q2: LinkedList 是线程安全的吗？

答案：

  • LinkedList 不是线程安全的
  • 多线程环境下需要外部同步
  • 可以使用 Collections.synchronizedList() 包装
Q3: LinkedList 的内存开销？

答案：

  • 每个节点需要额外存储 prev 和 next 指针
  • 节点在内存中不是连续存储，缓存命中率较低
  • 相比 ArrayList 有更高的内存开销
Q4: 为什么 LinkedList 不需要扩容？

答案：

  • LinkedList 基于链表结构，每个节点独立分配内存
  • 添加元素时只需要创建新节点并调整指针
  • 没有容量限制，理论上可以无限扩展
Q5: LinkedList 实现了哪些接口？

答案：

  • List：作为列表使用
  • Deque：作为双端队列使用
  • Cloneable：支持克隆
  • Serializable：支持序列化
6. Deque 接口的使用

由于实现了 Deque 接口，LinkedList 可以当作栈、队列使用：

1
2
3
4
5
6
7
8
9
LinkedList<String> list = new LinkedList<>();

// 作为队列使用（先进先出）
list.offer("element1");     // 入队
String element = list.poll(); // 出队

// 作为栈使用（后进先出）
list.push("element1");      // 入栈
String element = list.pop();  // 出栈
7. 性能特点
时间复杂度
操作 时间复杂度 说明
get(index) O(n) 需要遍历链表
add(E e) O(1) 直接添加到尾部
add(int index, E e) O(n) 需要找到指定位置
remove(index) O(n) 需要找到指定位置
remove(Object o) O(n) 需要遍历查找
空间复杂度
  • 每个节点需要额外的 prev 和 next 指针空间
  • 总体空间复杂度为 O(n)
8. 实际应用建议
使用场景
  1. 需要频繁在列表中间插入或删除元素
  2. 需要实现栈、队列等数据结构
  3. 不需要频繁通过索引访问元素
注意事项
  1. 避免频繁的随机访问操作
  2. 注意内存开销相对较大
  3. 多线程环境下需要同步处理
9. 高频面试代码
手写简单双向链表实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class SimpleLinkedList<E> {
    private Node<E> first;
    private Node<E> last;
    private int size = 0;
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    private void linkLast(E e) {
        Node<E> l = last;
        Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
    }
    
    public E get(int index) {
        return node(index).item;
    }
    
    private Node<E> node(int index) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    }
}

4.3 Vector详解

1. 基本概念

Vector 是 Java 集合框架中的一个传统集合类，它与 ArrayList 非常相似，但具有线程安全的特性。Vector 是 Java 1.0 版本就存在的类，属于较早期的集合实现。

2. 数据结构

Vector 的底层实现与 ArrayList 类似，都是基于动态数组：

1
2
3
protected Object[] elementData;  // 存储元素的数组
protected int elementCount;      // 实际元素个数
protected int capacityIncrement; // 容量增长量
3. 核心特性
线程安全性
  • Vector 的所有公共方法都使用 synchronized 关键字修饰
  • 因此在多线程环境下是安全的
  • 但性能相对较低（同步开销）
动态扩容
  • 默认初始容量为 10
  • 当容量不足时会自动扩容
  • 扩容策略与 ArrayList 不同
4. 关键方法实现
add(E e) 方法
1
2
3
4
5
6
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
get(int index) 方法
1
2
3
4
5
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}
remove(int index) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);
    
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--elementCount] = null; // Let gc do its work
    
    return oldValue;
}
5. 扩容机制
Vector 的扩容策略
1
2
3
4
5
6
7
8
9
10
11
12
13
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 如果 capacityIncrement > 0，则增长 capacityIncrement
    // 否则增长一倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
与 ArrayList 的区别
  • ArrayList: 每次扩容为原容量的 1.5 倍
  • Vector: 如果未指定 capacityIncrement，则扩容为原容量的 2 倍
6. 与 ArrayList 和 LinkedList 的对比
特性 Vector ArrayList LinkedList
线程安全 是 否 否
底层结构 动态数组 动态数组 双向链表
扩容倍数 2倍（默认） 1.5倍 不适用
随机访问 O(1) O(1) O(n)
插入/删除（中间） O(n) O(n) O(1)
性能 低（同步开销） 高 中等
7. 常见面试问题
Q1: Vector 为什么被 ArrayList 取代？

答案要点：

  1. 性能问题：Vector 的所有方法都是同步的，导致性能较差
  2. 设计缺陷：同步粒度太大，即使在单线程环境下也要承担同步开销
  3. 更好的替代方案：
    • 单线程：使用 ArrayList
    • 多线程：使用 Collections.synchronizedList(new ArrayList<>()) 或 CopyOnWriteArrayList
Q2: Vector 是如何保证线程安全的？

答案：

  • Vector 通过在所有公共方法上使用 synchronized 关键字实现线程安全
  • 每个方法在同一时刻只能被一个线程访问
  • 但这种同步方式效率较低，因为即使简单的读操作也需要获取锁
Q3: Vector 与 ArrayList 的主要区别？

答案要点：

  1. 线程安全性：Vector 是线程安全的，ArrayList 不是
  2. 扩容策略：Vector 默认扩容为 2 倍，ArrayList 为 1.5 倍
  3. 性能：Vector 性能较低，ArrayList 性能较高
  4. 遗留性：Vector 是遗留类，ArrayList 是集合框架的一部分
Q4: Vector 现在还应该使用吗？

答案：
一般不推荐使用 Vector，原因如下：

  1. 性能较差（过度同步）
  2. 有更好的替代方案
  3. 属于遗留类

推荐替代方案：

1
2
3
4
5
6
7
8
// 单线程环境
List<String> list = new ArrayList<>();

// 多线程环境 - 需要完全同步
List<String> list = Collections.synchronizedList(new ArrayList<>());

// 多线程环境 - 读多写少
List<String> list = new CopyOnWriteArrayList<>();
Q5: Vector 的 fail-fast 机制？

答案：

  • Vector 同样具有 fail-fast 机制
  • 当多个线程同时修改 Vector 时，可能抛出 ConcurrentModificationException
  • 但 Vector 的同步只能保证单个操作的原子性，不能保证复合操作的原子性
8. Enumerator vs Iterator
Vector 特有的遍历方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Vector<String> vector = new Vector<>();
vector.add("element1");
vector.add("element2");

// 使用 Enumeration（遗留方式）
Enumeration<String> enumeration = vector.elements();
while (enumeration.hasMoreElements()) {
    String element = enumeration.nextElement();
    System.out.println(element);
}

// 使用 Iterator（推荐方式）
Iterator<String> iterator = vector.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}
区别
特性 Enumeration Iterator
引入版本 JDK 1.0 JDK 1.2
方法名 hasMoreElements(), nextElement() hasNext(), next()
删除支持 不支持 支持 remove()
fail-fast 不支持 支持
9. 性能分析
同步开销
1
2
3
4
5
6
7
8
9
10
11
// Vector 的同步开销示例
public synchronized E get(int index) {
    // 整个方法都需要同步
    return elementData(index);
}

// ArrayList 无同步开销
public E get(int index) {
    // 直接访问，无同步
    return elementData(index);
}
实际性能测试

在单线程环境下，Vector 的性能通常比 ArrayList 差 50% 以上。

10. 实际应用建议
何时可能还需要使用 Vector？
  1. 维护遗留代码
  2. 需要与只接受 Vector 的 API 兼容
  3. 确实需要其特定的同步语义
最佳实践
1
2
3
4
5
6
7
8
9
10
11
12
// 不推荐
Vector<String> vector = new Vector<>();

// 推荐
// 单线程
List<String> list = new ArrayList<>();

// 多线程 - 读写都需要同步
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// 多线程 - 读多写少
List<String> cowList = new CopyOnWriteArrayList<>();
11. 高频面试代码题
手写简单的线程安全 ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class SimpleVector<E> {
    private Object[] elementData;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    public SimpleVector() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }
    
    public synchronized boolean add(E e) {
        ensureCapacity();
        elementData[size++] = e;
        return true;
    }
    
    public synchronized E get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (E) elementData[index];
    }
    
    private void ensureCapacity() {
        if (size == elementData.length) {
            int newCapacity = elementData.length * 2;
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
}

4.4 HashSet详解

1. 基本概念

HashSet 是 Java 集合框架中基于 HashMap 实现的 Set 接口的具体实现。它不允许重复元素，允许最多一个 null 元素，不保证元素的插入顺序。

2. 数据结构
底层实现
1
2
3
4
5
// HashSet 内部使用 HashMap 存储元素
private transient HashMap<E,Object> map;

// 用于映射到 HashMap 中的虚拟值
private static final Object PRESENT = new Object();
核心原理
  • HashSet 中的元素作为 HashMap 的 key 存储
  • 所有元素都映射到同一个虚拟值 PRESENT（作为 value）
  • 利用 HashMap key 的唯一性保证 HashSet 元素的唯一性
3. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 默认构造方法
public HashSet() {
    map = new HashMap<>();
}

// 指定初始容量
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

// 指定初始容量和负载因子
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

// 从集合构造
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
4. 核心方法实现
add(E e) 方法
1
2
3
4
public boolean add(E e) {
    // 将元素作为 key 放入 HashMap，值为 PRESENT
    return map.put(e, PRESENT) == null;
}
remove(Object o) 方法
1
2
3
4
public boolean remove(Object o) {
    // 从 HashMap 中移除 key
    return map.remove(o) == PRESENT;
}
contains(Object o) 方法
1
2
3
4
public boolean contains(Object o) {
    // 检查 HashMap 中是否包含该 key
    return map.containsKey(o);
}
size() 和 isEmpty() 方法
1
2
3
4
5
6
7
public int size() {
    return map.size();
}

public boolean isEmpty() {
    return map.isEmpty();
}
5. HashMap 的关键特性（HashSet 依赖）
数组 + 链表 + 红黑树结构
  • 数组：存储元素的主体结构
  • 链表：解决哈希冲突（JDK 8 之前）
  • 红黑树：优化链表过长问题（JDK 8+，链表长度 >= 8 且数组长度 >= 64）
重要参数
1
2
3
4
5
static final int DEFAULT_INITIAL_CAPACITY = 16;    // 默认初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;    // 默认负载因子
static final int TREEIFY_THRESHOLD = 8;            // 链表转红黑树阈值
static final int UNTREEIFY_THRESHOLD = 6;          // 红黑树转链表阈值
static final int MIN_TREEIFY_CAPACITY = 64;        // 最小树化容量
6. 哈希冲突处理
哈希计算
1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
存储位置计算
1
2
// 计算元素在数组中的位置
i = (n - 1) & hash
7. 与其它 Set 实现的对比
特性 HashSet LinkedHashSet TreeSet
底层结构 HashMap LinkedHashMap TreeMap
存储顺序 无序 插入顺序 排序顺序
时间复杂度 O(1) O(1) O(log n)
是否允许null 是 是 否（默认）
线程安全 否 否 否
8. 常见面试问题
Q1: HashSet 如何保证元素唯一性？

答案要点：

  1. 基于 HashMap 的 key 唯一性
  2. 添加元素时调用 HashMap.put() 方法
  3. 如果 key 已存在，会返回旧值，否则返回 null
  4. HashSet 根据返回值判断是否添加成功
1
2
3
4
// HashSet.add() 的核心逻辑
public boolean add(E e) {
    return map.put(e, PRESENT) == null; // 如果已存在返回 false
}
Q2: HashSet 是如何处理 null 值的？

答案：

  1. HashSet 允许存储一个 null 元素
  2. HashMap 允许 null 作为 key
  3. null 的哈希值被定义为 0
  4. 多次添加 null 只会保留一个
Q3: HashSet 是线程安全的吗？

答案：

  • HashSet 不是线程安全的
  • 多线程环境下需要外部同步
  • 可以使用以下方式实现线程安全：
1
2
3
4
5
6
7
8
9
10
11
// 方式1：使用 Collections.synchronizedSet()
Set<String> set = Collections.synchronizedSet(new HashSet<>());

// 方式2：使用 ConcurrentHashMap（Java 8+）
Set<String> set = ConcurrentHashMap.newKeySet();

// 方式3：手动同步
Set<String> set = new HashSet<>();
synchronized(set) {
    set.add("element");
}
Q4: HashSet 的初始容量和负载因子？

答案：

  • 默认初始容量：16
  • 默认负载因子：0.75
  • 扩容时机：元素个数 > 容量 × 负载因子
  • 扩容策略：容量翻倍
Q5: 为什么 HashSet 的负载因子是 0.75？

答案要点：

  1. 时间与空间的权衡：
    • 负载因子太小：浪费空间，但查找效率高
    • 负载因子太大：节省空间，但冲突增多，查找效率下降
  2. 泊松分布统计：
    • 0.75 是在时间和空间成本上寻求平衡的结果
    • 在这个负载因子下，链表长度为 8 的概率非常小（约千万分之六）
Q6: HashSet 和 HashMap 的关系？

答案：

  1. HashSet 内部使用 HashMap 实现
  2. HashSet 的元素作为 HashMap 的 key 存储
  3. 所有元素都映射到同一个虚拟值 PRESENT
  4. 利用 HashMap key 的唯一性保证 Set 的唯一性
Q7: HashSet 的遍历顺序？

答案：

  • HashSet 不保证元素的遍历顺序
  • 顺序可能与插入顺序不同
  • 甚至在多次遍历中顺序可能不同
  • 如果需要保持插入顺序，应使用 LinkedHashSet
9. 性能特点
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
add O(1) O(n)
remove O(1) O(n)
contains O(1) O(n)
size O(1) O(1)
空间复杂度
  • O(n)，其中 n 是元素个数
10. 实际应用建议
使用场景
  1. 需要去重的场景
  2. 快速查找、插入、删除操作
  3. 不关心元素顺序的场景
注意事项
  1. 元素必须正确实现 hashCode() 和 equals() 方法
  2. 存储的元素应该是不可变的，或者在存储期间不改变影响哈希值的字段
  3. 多线程环境下需要同步处理
11. fail-fast 机制

HashSet 同样具有 fail-fast 机制：

1
2
3
4
5
6
7
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    if (someCondition) {
        set.remove(element); // 这会抛出 ConcurrentModificationException
    }
}

正确的做法：

1
2
3
4
5
6
7
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    if (someCondition) {
        iterator.remove(); // 使用迭代器的 remove 方法
    }
}
12. 高频面试代码题
自定义实现简单的 HashSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class SimpleHashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();
    
    public SimpleHashSet() {
        map = new HashMap<>();
    }
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
    
    public int size() {
        return map.size();
    }
}
重写 hashCode() 和 equals() 的正确方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Person {
    private String name;
    private int age;
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

4.5 LinkedHashSet详解

1. 基本概念

LinkedHashSet 是 HashSet 的子类，它通过维护一个运行于所有条目的双向链表来保证迭代顺序。与 HashSet 不同，LinkedHashSet 按照元素的插入顺序进行迭代。

2. 数据结构
继承关系
1
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable
底层实现
  • 基于 LinkedHashMap 实现，而不是 HashMap
  • 维护元素的插入顺序通过双向链表
3. 核心特性
有序性
  • 保持元素的插入顺序
  • 迭代顺序与插入顺序一致
唯一性
  • 不允许重复元素
  • 最多允许一个 null 元素
性能特点
  • 基本操作（add, remove, contains）时间复杂度为 O(1)
  • 比 HashSet 略微慢一些（维护链表的开销）
4. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 默认构造方法
public LinkedHashSet() {
    super(16, .75f, true);  // 调用父类 HashSet 的特殊构造方法
}

// 指定初始容量
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

// 指定初始容量和负载因子
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

// 从集合构造
public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}
5. LinkedHashSet 与 HashSet 的区别
HashSet 构造方法调用
1
2
3
4
5
6
7
8
9
// HashSet 的特殊构造方法（LinkedHashSet 使用）
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

// 普通 HashSet 构造方法
public HashSet() {
    map = new HashMap<>();
}
6. LinkedHashMap 的链表结构
节点结构
1
2
3
4
5
6
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 维护插入顺序的双向链表指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
链表维护
  • before 和 after 指针维护插入顺序
  • 头节点 head 和尾节点 tail 跟踪链表两端
  • 插入新元素时添加到链表尾部
7. 核心方法实现
add(E e) 方法
1
2
3
4
5
6
7
8
9
// 继承自 HashSet，实际调用 LinkedHashMap.put()
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

// LinkedHashMap.put() 中维护链表顺序
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
LinkedHashSet 的迭代
1
2
3
4
5
6
7
public Iterator<E> iterator() {
    return new LinkedHashIterator();
}

private class LinkedHashIterator extends HashIterator {
    // 按照链表顺序遍历
}
8. 与其它 Set 实现的对比
特性 HashSet LinkedHashSet TreeSet
底层结构 HashMap LinkedHashMap TreeMap
存储顺序 无序 插入顺序 排序顺序
时间复杂度 O(1) O(1) O(log n)
空间开销 较小 中等（额外链表指针） 较大（红黑树）
是否允许null 是 是 否（默认）
9. 常见面试问题
Q1: LinkedHashSet 如何维护插入顺序？

答案要点：

  1. 基于 LinkedHashMap 实现
  2. 每个节点除了 HashMap 的链表指针外，还有 before 和 after 指针
  3. 维护一个双向链表记录插入顺序
  4. 插入新元素时，将其添加到双向链表的尾部
1
2
3
4
5
6
7
8
9
10
11
// LinkedHashMap 中的链接操作
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
Q2: LinkedHashSet 与 HashSet 的性能对比？

答案：

操作 HashSet LinkedHashSet 说明
add O(1) O(1) 基本相同
remove O(1) O(1) 基本相同
contains O(1) O(1) 基本相同
迭代 O(n) O(n) LinkedHashSet 更快（顺序访问）
空间 较小 中等 LinkedHashSet 额外存储链表指针
Q3: LinkedHashSet 是线程安全的吗？

答案：

  • LinkedHashSet 不是线程安全的
  • 多线程环境下需要外部同步
  • 解决方案与 HashSet 相同：
1
2
// 使用 Collections.synchronizedSet()
Set<String> set = Collections.synchronizedSet(new LinkedHashSet<>());
Q4: LinkedHashSet 的应用场景？

答案：

  1. 需要去重且保持插入顺序：

    1
    2
    3
    4
    5
    Set<String> uniqueItems = new LinkedHashSet<>();
    uniqueItems.add("item1");
    uniqueItems.add("item2");
    uniqueItems.add("item1"); // 重复，不会添加
    // 遍历时保持插入顺序

  2. 实现 LRU 缓存（通过 accessOrder 模式）：

    1
    2
    3
    4
    5
    6
    // LinkedHashMap 的 accessOrder 模式
    LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<Integer, String>(16, 0.75f, true) {
        protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
            return size() > MAX_ENTRIES;
        }
    };
Q5: LinkedHashSet 与 TreeSet 的选择？

答案对比：

场景 LinkedHashSet TreeSet
去重 + 保持插入顺序 ✅ 推荐 ❌ 不适用
去重 + 排序 ⚠️ 需要额外排序 ✅ 推荐
性能要求高 ✅ O(1) 操作 ⚠️ O(log n) 操作
自定义排序 ❌ 不支持 ✅ 支持 Comparator
Q6: LinkedHashSet 如何处理 null 值？

答案：

  • 允许存储一个 null 元素
  • null 元素也按照插入顺序维护
  • 多次添加 null 只会保留一个
1
2
3
4
5
6
7
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("first");
set.add(null);
set.add("second");
set.add(null); // 不会重复添加

// 遍历顺序：first -> null -> second
10. fail-fast 机制

LinkedHashSet 同样具有 fail-fast 机制：

1
2
3
4
5
6
7
8
9
10
11
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("first");
set.add("second");

Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    if ("first".equals(element)) {
        set.remove(element); // 抛出 ConcurrentModificationException
    }
}

正确的做法：

1
2
3
4
5
6
7
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    if ("first".equals(element)) {
        iterator.remove(); // 使用迭代器的 remove 方法
    }
}
11. 性能分析
时间复杂度
操作 时间复杂度
add O(1)
remove O(1)
contains O(1)
size O(1)
iterator O(1)
空间复杂度
  • O(n)，其中 n 是元素个数
  • 比 HashSet 多出双向链表的存储开销
12. 实际应用建议
使用场景
  1. 需要去重且保持插入顺序的场景
  2. 实现简单的 LRU 缓存
  3. 需要按插入顺序遍历的集合操作
注意事项
  1. 元素必须正确实现 hashCode() 和 equals() 方法
  2. 存储的元素应该是不可变的，或者在存储期间不改变影响哈希值的字段
  3. 多线程环境下需要同步处理
13. 高频面试代码题
手写简单的 LinkedHashSet 实现
1
2
3
4
5
6
7
public class SimpleLinkedHashSet<E> extends HashSet<E> {
    public SimpleLinkedHashSet() {
        super(16, .75f, true); // 调用 HashSet 的 LinkedHashMap 构造方法
    }
    
    // 其他方法继承自 HashSet
}
实现 LRU 缓存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        // accessOrder = true 表示按访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

4.6 TreeMap详解

1. 基本概念

TreeMap 是基于红黑树（Red-Black tree）实现的 SortedMap 接口的具体实现。它能够按照键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序。

2. 数据结构
红黑树特性

红黑树是一种自平衡的二叉搜索树，具有以下特性：

  1. 每个节点要么是红色，要么是黑色
  2. 根节点是黑色
  3. 每个叶子节点（NIL节点）是黑色
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
节点结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;  // 默认为黑色
    
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}
3. 核心字段
1
2
3
4
private transient Entry<K,V> root;           // 根节点
private transient int size = 0;              // 节点数量
private transient int modCount = 0;          // 修改次数
private final Comparator<? super K> comparator; // 比较器
4. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 默认构造方法 - 使用键的自然顺序
public TreeMap() {
    comparator = null;
}

// 使用指定比较器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

// 从 Map 构造
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

// 从 SortedMap 构造
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}
5. 核心操作实现
put(K key, V value) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);  // 插入后调整红黑树
    size++;
    modCount++;
    return null;
}
get(Object key) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p == null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
6. 红黑树平衡操作
左旋操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}
右旋操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}
插入后调整
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;  // 新插入节点为红色

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
7. 有序性相关方法
firstKey() 和 lastKey()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public K firstKey() {
    return key(firstEntry());
}

public K lastKey() {
    return key(lastEntry());
}

final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
ceilingKey()、floorKey()、higherKey()、lowerKey()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public K ceilingKey(K key) {
    return keyOrNull(getCeilingEntry(key));
}

public K floorKey(K key) {
    return keyOrNull(getFloorEntry(key));
}

public K higherKey(K key) {
    return keyOrNull(getHigherEntry(key));
}

public K lowerKey(K key) {
    return keyOrNull(getLowerEntry(key));
}
8. 与其他 Map 实现的对比
特性 HashMap LinkedHashMap TreeMap
底层结构 数组+链表/红黑树 数组+链表/红黑树+双向链表 红黑树
存储顺序 无序 插入顺序/访问顺序 排序顺序
时间复杂度 O(1) O(1) O(log n)
空间开销 较小 中等 较大
是否有序 否 是（插入/访问顺序） 是（排序）
9. 常见面试问题
Q1: TreeMap 如何实现排序？

答案要点：

  1. 基于红黑树实现，天然有序
  2. 通过 Comparable 接口或 Comparator 进行比较
  3. 插入时根据比较结果确定节点位置
  4. 遍历时按照中序遍历（左-根-右）保证有序性
1
2
3
4
5
// 自然排序
TreeMap<Integer, String> map1 = new TreeMap<>();

// 自定义排序
TreeMap<String, String> map2 = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
Q2: TreeMap 的时间复杂度？

答案：

操作 时间复杂度 说明
get/put/remove O(log n) 红黑树的高度为 log n
first/last O(log n) 需要从根节点遍历到最左/最右节点
ceiling/floor O(log n) 需要在树中查找
size O(1) 维护了 size 字段
Q3: TreeMap 是线程安全的吗？

答案：

  • TreeMap 不是线程安全的
  • 多线程环境下需要外部同步
  • 解决方案：
1
2
3
4
5
// 使用 Collections.synchronizedSortedMap()
SortedMap<String, String> map = Collections.synchronizedSortedMap(new TreeMap<>());

// 使用 ConcurrentHashMap（Java 8+）
ConcurrentSkipListMap<String, String> map = new ConcurrentSkipListMap<>();
Q4: TreeMap 与 HashMap 的选择？

答案对比：

场景 TreeMap HashMap
需要排序 ✅ 推荐 ❌ 不适用
快速访问 ⚠️ O(log n) ✅ O(1)
范围查询 ✅ 支持 ❌ 不支持
内存占用 ⚠️ 较大 ✅ 较小
Q5: 红黑树的平衡操作有哪些？

答案：

  1. 变色：改变节点颜色
  2. 左旋：将右子节点提升为父节点
  3. 右旋：将左子节点提升为父节点

插入和删除后可能需要这些操作来维持红黑树的性质。

Q6: TreeMap 如何处理 null 值？

答案：

  • TreeMap 对键的处理：
    • 使用自然排序时，不允许 null 键（会抛出 NullPointerException）
    • 使用自定义比较器时，取决于比较器的实现
  • TreeMap 对值的处理：
    • 允许 null 值
1
2
3
4
5
6
7
8
9
10
11
12
// 使用自然排序 - 抛出异常
TreeMap<String, String> map = new TreeMap<>();
map.put(null, "value"); // NullPointerException

// 使用允许 null 的比较器
TreeMap<String, String> map2 = new TreeMap<>((s1, s2) -> {
    if (s1 == null && s2 == null) return 0;
    if (s1 == null) return -1;
    if (s2 == null) return 1;
    return s1.compareTo(s2);
});
map2.put(null, "value"); // 正常工作
10. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
get O(log n) O(log n)
put O(log n) O(log n)
remove O(log n) O(log n)
containsKey O(log n) O(log n)
空间复杂度
  • O(n)，其中 n 是键值对个数
  • 每个节点需要存储额外的指针（parent, left, right）和颜色信息
11. 实际应用建议
使用场景
  1. 需要按键排序的场景
  2. 需要范围查询的场景
  3. 需要获取第一个/最后一个元素的场景
  4. 需要获取大于/小于某个键的元素的场景
注意事项
  1. 键必须实现 Comparable 接口或提供 Comparator
  2. 性能比 HashMap 差，但提供了有序性
  3. 多线程环境下需要同步处理
12. 高频面试代码题
实现简单的二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class SimpleBST<K extends Comparable<K>, V> {
    private Node<K, V> root;
    
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> left, right;
        
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public void put(K key, V value) {
        root = put(root, key, value);
    }
    
    private Node<K, V> put(Node<K, V> node, K key, V value) {
        if (node == null) return new Node<>(key, value);
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0) 
            node.left = put(node.left, key, value);
        else if (cmp > 0)
            node.right = put(node.right, key, value);
        else
            node.value = value;
            
        return node;
    }
    
    public V get(K key) {
        Node<K, V> node = get(root, key);
        return node == null ? null : node.value;
    }
    
    private Node<K, V> get(Node<K, V> node, K key) {
        if (node == null) return null;
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0)
            return get(node.left, key);
        else if (cmp > 0)
            return get(node.right, key);
        else
            return node;
    }
}

4.7 PriorityQueue详解

1. 基本概念

PriorityQueue 是基于优先堆（priority heap）的一个无界队列实现，它不允许 null 元素，且插入到 PriorityQueue 中的元素必须实现 Comparable 接口，或者在创建队列时提供 Comparator。

2. 数据结构
堆结构

PriorityQueue 使用完全二叉树的数组表示法实现最小堆：

  • 根节点是最小元素（默认情况下）
  • 对于任意节点 i，其左子节点为 2i+1，右子节点为 2i+2
  • 对于任意节点 i（i>0），其父节点为 (i-1)/2
核心字段
1
2
3
4
private transient Object[] queue;  // 存储元素的数组
private int size = 0;              // 实际元素个数
private final Comparator<? super E> comparator;  // 比较器
private transient int modCount = 0; // 修改次数
3. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 默认构造方法
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

// 指定初始容量
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

// 使用指定比较器
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

// 从集合构造
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}
4. 核心操作实现
add(E e) / offer(E e) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);  // 扩容
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);  // 上浮调整
    return true;
}
poll() 方法（出队）
1
2
3
4
5
6
7
8
9
10
11
12
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];  // 取堆顶元素
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);  // 下沉调整
    return result;
}
peek() 方法（查看队首）
1
2
3
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}
5. 堆调整算法
上浮操作（siftUp）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;  // 父节点索引
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)  // 满足堆性质则停止
            break;
        queue[k] = e;  // 父节点下沉
        k = parent;
    }
    queue[k] = key;
}
下沉操作（siftDown）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // 非叶子节点的范围
    while (k < half) {
        int child = (k << 1) + 1; // 左子节点
        Object c = queue[child];
        int right = child + 1;
        // 选择较小的子节点
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        // 如果当前元素小于等于子节点，则满足堆性质
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;  // 子节点上浮
        k = child;
    }
    queue[k] = key;
}
6. 扩容机制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 如果容量小于64，扩容为原来的2倍；否则扩容为原来的1.5倍
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // 检查是否溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
7. 与其它队列实现的对比
特性 PriorityQueue ArrayDeque LinkedList
底层结构 数组（堆） 数组（循环数组） 双向链表
排序特性 优先级排序 FIFO FIFO
插入时间复杂度 O(log n) O(1) O(1)
删除时间复杂度 O(log n) O(1) O(1)
查找最小/最大 O(1) O(n) O(n)
8. 常见面试问题
Q1: PriorityQueue 如何保证优先级顺序？

答案要点：

  1. 基于堆数据结构实现
  2. 默认实现最小堆（最小元素优先）
  3. 插入元素时通过上浮操作维护堆性质
  4. 删除元素时通过下沉操作维护堆性质
  5. 通过 Comparable 或 Comparator 确定元素优先级
1
2
3
4
5
6
7
8
// 默认最小堆
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 最大堆实现
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());

// 自定义比较器
PriorityQueue<String> customPq = new PriorityQueue<>((s1, s2) -> s2.length() - s1.length());
Q2: PriorityQueue 的时间复杂度？

答案：

操作 时间复杂度 说明
offer/add O(log n) 需要上浮调整
poll/remove O(log n) 需要下沉调整
peek/element O(1) 直接访问堆顶
size/isEmpty O(1) 维护了 size 字段
Q3: PriorityQueue 是线程安全的吗？

答案：

  • PriorityQueue 不是线程安全的
  • 多线程环境下需要外部同步
  • 解决方案：
1
2
3
4
5
6
// 使用 synchronized 包装
PriorityQueue<String> pq = new PriorityQueue<>();
PriorityQueue<String> syncPq = Collections.synchronizedQueue(pq);

// 使用阻塞队列
PriorityBlockingQueue<String> blockingPq = new PriorityBlockingQueue<>();
Q4: PriorityQueue 与 TreeSet 的区别？

答案对比：

特性 PriorityQueue TreeSet
底层结构 堆 红黑树
有序性 部分有序（堆性质） 完全有序
重复元素 允许 不允许
时间复杂度 O(log n) O(log n)
空间复杂度 较小 较大
迭代顺序 不保证 保证排序顺序
Q5: PriorityQueue 如何处理 null 值？

答案：

  • PriorityQueue 不允许存储 null 元素
  • 尝试添加 null 会抛出 NullPointerException
  • 这是因为无法对 null 进行比较以确定优先级
1
2
PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer(null); // 抛出 NullPointerException
Q6: PriorityQueue 的初始容量和扩容策略？

答案：

  • 默认初始容量：11
  • 扩容策略：
    • 容量 < 64：扩容为 2 × 原容量 + 2
    • 容量 ≥ 64：扩容为 1.5 × 原容量
  • 最大容量：Integer.MAX_VALUE - 8
9. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
add/offer O(log n) O(log n)
remove/poll O(log n) O(log n)
peek O(1) O(1)
contains O(n) O(n)
remove(Object) O(n) O(n)
空间复杂度
  • O(n)，其中 n 是元素个数
10. 实际应用建议
使用场景
  1. 任务调度：按优先级执行任务
  2. Dijkstra 算法：寻找最短路径
  3. Huffman 编码：构建最优二叉树
  4. Top K 问题：找到前 K 个最大/最小元素
  5. 事件驱动系统：按时间顺序处理事件
注意事项
  1. 元素必须可比较（实现 Comparable 或提供 Comparator）
  2. 不允许 null 元素
  3. 迭代不保证顺序（除了堆顶元素）
  4. 多线程环境下需要同步处理
11. 经典应用场景示例
Top K 问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 找到数组中前 K 个最大的元素
public List<Integer> topKFrequent(int[] nums, int k) {
    // 统计频率
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }
    
    // 使用最小堆维护前 K 个元素
    PriorityQueue<Map.Entry<Integer, Integer>> pq = 
        new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue());
    
    for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
        pq.offer(entry);
        if (pq.size() > k) {
            pq.poll();  // 移除最小频率元素
        }
    }
    
    List<Integer> result = new ArrayList<>();
    while (!pq.isEmpty()) {
        result.add(pq.poll().getKey());
    }
    return result;
}
合并 K 个有序链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    
    // 使用最小堆存储各链表的头节点
    PriorityQueue<ListNode> pq = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
    
    for (ListNode node : lists) {
        if (node != null) {
            pq.offer(node);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        current.next = node;
        current = current.next;
        if (node.next != null) {
            pq.offer(node.next);
        }
    }
    
    return dummy.next;
}
12. 高频面试代码题
手写简单的最小堆实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class SimpleMinHeap<E extends Comparable<E>> {
    private Object[] queue;
    private int size = 0;
    private static final int DEFAULT_CAPACITY = 11;
    
    public SimpleMinHeap() {
        queue = new Object[DEFAULT_CAPACITY];
    }
    
    public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        int i = size;
        if (i >= queue.length) grow();
        size = i + 1;
        if (i == 0) {
            queue[0] = e;
        } else {
            siftUp(i, e);
        }
        return true;
    }
    
    public E poll() {
        if (size == 0) return null;
        int s = --size;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0) siftDown(0, x);
        return result;
    }
    
    private void siftUp(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            E e = (E) queue[parent];
            if (x.compareTo(e) >= 0) break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
    
    private void siftDown(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            E c = (E) queue[child];
            int right = child + 1;
            if (right < size && ((E) queue[right]).compareTo(c) < 0)
                c = (E) queue[child = right];
            if (x.compareTo(c) <= 0) break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }
    
    private void grow() {
        int oldCapacity = queue.length;
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                       (oldCapacity + 2) :
                                       (oldCapacity >> 1));
        queue = Arrays.copyOf(queue, newCapacity);
    }
    
    public E peek() {
        return (size == 0) ? null : (E) queue[0];
    }
    
    public int size() {
        return size;
    }
}

4.8 ArrayDeque详解

1. 基本概念

ArrayDeque（Array Double Ended Queue）是 Java 集合框架中的一个双端队列实现，它基于动态数组实现，支持在两端进行高效的插入和删除操作。ArrayDeque 可以用作栈、队列或双端队列。

2. 数据结构
循环数组结构

ArrayDeque 使用循环数组（环形缓冲区）来存储元素，通过两个指针维护队列的头和尾：

1
2
3
transient Object[] elements;  // 存储元素的数组
transient int head;           // 队列头部索引
transient int tail;           // 队列尾部索引
循环数组原理
  • 数组逻辑上是环形的，当索引到达数组末尾时会回到开头
  • 通过取模运算实现循环：(index + 1) & (elements.length - 1)
  • 当 head == tail 时表示队列为空或满，通过 size 字段区分
3. 核心字段和构造方法
核心字段
1
2
3
4
transient Object[] elements;  // 存储元素的数组
transient int head;           // 队列头部索引
transient int tail;           // 队列尾部索引
private static final int MIN_INITIAL_CAPACITY = 8;  // 最小容量
构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 默认构造方法
public ArrayDeque() {
    elements = new Object[16];
}

// 指定初始容量
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

// 从集合构造
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
容量分配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // 找到大于等于 numElements 的最小 2 的幂
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        
        if (initialCapacity < 0)   // 太大溢出
            initialCapacity >>>= 1; // 回退到最大值
    }
    elements = new Object[initialCapacity];
}
4. 核心操作实现
addFirst(E e) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();  // 扩容
}

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head 右边的元素个数
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);  // 复制 head 右边的元素
    System.arraycopy(elements, 0, a, r, p);  // 复制 head 左边的元素
    elements = a;
    head = 0;
    tail = n;
}
addLast(E e) 方法
1
2
3
4
5
6
7
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();  // 扩容
}
pollFirst() 方法
1
2
3
4
5
6
7
8
9
10
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    if (result == null)
        return null;
    elements[h] = null;     // 帮助 GC
    head = (h + 1) & (elements.length - 1);
    return result;
}
pollLast() 方法
1
2
3
4
5
6
7
8
9
10
public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;     // 帮助 GC
    tail = t;
    return result;
}
5. 循环数组操作技巧
索引计算
1
2
3
4
5
6
7
8
// 向前移动（减1并处理负数）
(head - 1) & (elements.length - 1)

// 向后移动（加1并处理越界）
(tail + 1) & (elements.length - 1)

// 向前移动 n 位
(head - n) & (elements.length - 1)
为什么容量是 2 的幂？
  1. 可以使用位运算代替取模运算，提高性能
  2. (index & (length-1)) 等价于 index % length（当 length 是 2 的幂时）
  3. 简化索引计算逻辑
6. 与其它队列实现的对比
特性 ArrayDeque LinkedList Stack Vector
底层结构 循环数组 双向链表 数组 数组
随机访问 O(1) O(n) O(1) O(1)
头部插入/删除 O(1) O(1) O(1) O(n)
尾部插入/删除 O(1) O(1) O(1) O(1)
内存开销 较少 较多 中等 中等
扩容策略 2倍 不需要 2倍 2倍
7. 常见面试问题
Q1: ArrayDeque 为什么比 LinkedList 更高效？

答案要点：

  1. 内存局部性：ArrayDeque 使用连续内存存储，缓存命中率高
  2. 内存开销：不需要存储额外的指针（prev/next）
  3. 操作效率：基于数组的随机访问比链表遍历更快
  4. GC友好：连续内存分配，减少内存碎片
1
2
3
4
5
// ArrayDeque 的内存布局（连续）
[elem1][elem2][elem3][elem4][elem5]

// LinkedList 的内存布局（分散）
[elem1] -> [elem2] -> [elem3] -> [elem4] -> [elem5]
Q2: ArrayDeque 的时间复杂度？

答案：

操作 时间复杂度 说明
addFirst/addLast O(1) 平摊
pollFirst/pollLast O(1)
peekFirst/peekLast O(1)
size/isEmpty O(1)
contains O(n) 需要遍历
Q3: ArrayDeque 是线程安全的吗？

答案：

  • ArrayDeque 不是线程安全的
  • 多线程环境下需要外部同步
  • 解决方案：
1
2
3
4
5
6
// 使用 synchronized 包装
Deque<String> deque = new ArrayDeque<>();
Deque<String> syncDeque = Collections.synchronizedDeque(deque);

// 使用阻塞队列
LinkedBlockingDeque<String> blockingDeque = new LinkedBlockingDeque<>();
Q4: ArrayDeque 与 Stack 的比较？

答案对比：

特性 ArrayDeque Stack
继承关系 独立类 继承 Vector
性能 更好 较差（同步开销）
线程安全 否 是（但不推荐）
官方推荐 ✅ 推荐 ❌ 不推荐 
1
2
3
4
5
6
7
8
9
10
11
// 推荐使用 ArrayDeque 作为栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
Integer top = stack.pop();

// 不推荐使用 Stack 类
Stack<Integer> oldStack = new Stack<>();
oldStack.push(1);
oldStack.push(2);
Integer top2 = oldStack.pop();
Q5: ArrayDeque 如何处理 null 值？

答案：

  • ArrayDeque 不允许存储 null 元素
  • 所有插入 null 的操作都会抛出 NullPointerException
  • 这是因为 null 被用作判断队列是否为空的标志
1
2
ArrayDeque<String> deque = new ArrayDeque<>();
deque.offer(null); // 抛出 NullPointerException
Q6: ArrayDeque 的扩容机制？

答案：

  1. 触发时机：当 head == tail 且数组已满时
  2. 扩容策略：容量翻倍
  3. 数据重排：重新排列元素使其连续存储
  4. 性能考虑：扩容操作是 O(n) 的，但平摊后仍是 O(1)
1
2
3
4
private void doubleCapacity() {
    // 重新分配 2 倍容量的新数组
    // 将原数组元素重新排列为连续存储
}
8. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
addFirst/addLast O(1) O(n)（扩容时）
pollFirst/pollLast O(1) O(1)
peekFirst/peekLast O(1) O(1)
size O(1) O(1)
空间复杂度
  • O(n)，其中 n 是元素个数
  • 实际占用空间可能略大于 n（预留空间）
9. 实际应用建议
使用场景
  1. 作为栈使用：比传统 Stack 性能更好
  2. 作为队列使用：比 LinkedList 性能更好
  3. 双端队列操作：需要两端高效操作的场景
  4. BFS/DFS 算法：图遍历算法中的辅助数据结构
注意事项
  1. 不允许存储 null 元素
  2. 非线程安全，多线程环境需要同步
  3. 扩容时会有性能波动（但平摊后仍是 O(1)）
  4. 迭代顺序从 head 到 tail
10. 经典应用场景示例
用作栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class StackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        
        // 出栈
        while (!stack.isEmpty()) {
            System.out.println(stack.pop()); // 输出: 3, 2, 1
        }
    }
}
用作队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class QueueExample {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();
        
        // 入队
        queue.offer("first");
        queue.offer("second");
        queue.offer("third");
        
        // 出队
        while (!queue.isEmpty()) {
            System.out.println(queue.poll()); // 输出: first, second, third
        }
    }
}
双端队列操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        
        // 两端添加
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(0);
        deque.addLast(3);
        
        // 两端删除
        System.out.println(deque.pollFirst()); // 0
        System.out.println(deque.pollLast());  // 3
        System.out.println(deque.pollFirst()); // 1
        System.out.println(deque.pollFirst()); // 2
    }
}
11. 高频面试代码题
手写简单的循环数组实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class SimpleArrayDeque<E> {
    private Object[] elements;
    private int head = 0;
    private int tail = 0;
    private static final int DEFAULT_CAPACITY = 16;
    
    public SimpleArrayDeque() {
        elements = new Object[DEFAULT_CAPACITY];
    }
    
    public void addFirst(E e) {
        if (e == null) throw new NullPointerException();
        head = (head - 1) & (elements.length - 1);
        elements[head] = e;
        if (head == tail) resize();
    }
    
    public void addLast(E e) {
        if (e == null) throw new NullPointerException();
        elements[tail] = e;
        tail = (tail + 1) & (elements.length - 1);
        if (head == tail) resize();
    }
    
    public E pollFirst() {
        E result = (E) elements[head];
        if (result == null) return null;
        elements[head] = null;
        head = (head + 1) & (elements.length - 1);
        return result;
    }
    
    public E pollLast() {
        tail = (tail - 1) & (elements.length - 1);
        E result = (E) elements[tail];
        if (result == null) return null;
        elements[tail] = null;
        return result;
    }
    
    private void resize() {
        int p = head;
        int n = elements.length;
        int r = n - p;
        int newCapacity = n << 1;
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }
}
用 ArrayDeque 实现 BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class BFSTraversal {
    public void bfs(TreeNode root) {
        if (root == null) return;
        
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node.val);
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
}

4.9 HashMap详解

1. 基本概念

HashMap 是 Java 集合框架中最重要的数据结构之一，它基于哈希表实现，用于存储键值对（key-value pairs）。HashMap 允许 null 键和 null 值，不保证映射的顺序，特别是它不保证该顺序恒久不变。

2. 数据结构演进
JDK 1.7 及之前：数组 + 链表
  • 使用 Entry 数组存储数据
  • 哈希冲突通过链表解决
JDK 1.8 及之后：数组 + 链表 + 红黑树
  • 引入红黑树优化链表过长问题
  • 链表长度 >= 8 且数组长度 >= 64 时转为红黑树
  • 红黑树节点数 <= 6 时转回链表
3. 核心字段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30; // 2^30

// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树化容量
static final int MIN_TREEIFY_CAPACITY = 64;

// 存储数据的数组
transient Node<K,V>[] table;

// 键值对数量
transient int size;

// 修改次数
transient int modCount;

// 扩容阈值
int threshold;

// 负载因子
final float loadFactor;
4. Node 节点结构
1
2
3
4
5
6
7
8
9
10
11
12
13
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    // 哈希值
    final K key;       // 键
    V value;           // 值
    Node<K,V> next;    // 指向下一个节点的指针
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}
5. 红黑树节点结构
1
2
3
4
5
6
7
8
9
10
11
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父节点
    TreeNode<K,V> left;    // 左子节点
    TreeNode<K,V> right;   // 右子节点
    TreeNode<K,V> prev;    // 删除时需要的前驱节点
    boolean red;           // 颜色标志
    
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}
6. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 默认构造方法
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 其他字段使用默认值
}

// 指定初始容量
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 指定初始容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

// 从 Map 构造
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
7. 核心方法实现
hash() 方法
1
2
3
4
5
static final int hash(Object key) {
    int h;
    // 高16位与低16位异或，减少哈希冲突
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
put(K key, V value) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果 table 为空或长度为 0，则进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶为空，直接放入新节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果第一个节点就是要找的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果是红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 如果是链表节点
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 插入到链表尾部
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度 >= 8，转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果找到相同的 key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果找到了相同的 key，更新 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果 size 超过阈值，进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
get(Object key) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 检查第一个节点
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 遍历链表或红黑树
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
resize() 扩容方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // 如果容量已达最大值，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 阈值也翻倍
    }
    else if (oldThr > 0) // 使用 threshold 作为初始容量
        newCap = oldThr;
    else {               // 使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 创建新数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 重新哈希所有节点
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) // 单个节点
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) // 红黑树节点
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 链表节点
                    Node<K,V> loHead = null, loTail = null;  // 低位链表
                    Node<K,V> hiHead = null, hiTail = null;  // 高位链表
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 根据 hash 值决定放在低位还是高位
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 设置低位链表
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 设置高位链表
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
8. 红黑树相关操作
treeifyBin() 链表转红黑树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果数组长度小于 MIN_TREEIFY_CAPACITY，只扩容不转树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 将链表节点转换为树节点
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 树化操作
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}
9. 与其它 Map 实现的对比
特性 HashMap TreeMap LinkedHashMap
底层结构 数组+链表/红黑树 红黑树 数组+链表/红黑树+双向链表
时间复杂度 O(1) O(log n) O(1)
有序性 无序 排序顺序 插入顺序
线程安全 否 否 否
适用场景 快速查找 排序查找 保持插入顺序
10. 常见面试问题
Q1: HashMap 的工作原理？

答案要点：

  1. 基于哈希表实现，使用数组存储数据
  2. 通过键的 hashCode() 计算哈希值，确定存储位置
  3. 哈希冲突通过链表或红黑树解决
  4. 负载因子控制扩容时机
Q2: JDK 1.8 中 HashMap 的优化？

答案：

  1. 引入红黑树：链表长度 >= 8 时转为红黑树，提高查找效率
  2. 优化哈希算法：高16位与低16位异或，减少哈希冲突
  3. 扩容优化：扩容时元素位置要么不变，要么移动到原位置+原容量的位置
  4. 并发安全：修复了并发修改时的死循环问题
Q3: HashMap 是线程安全的吗？

答案：

  • HashMap 不是线程安全的
  • 多线程环境下可能出现：
    • 数据不一致
    • 死循环（JDK 1.7）
    • 丢失更新

解决方案：

1
2
3
4
5
6
7
8
9
10
11
// 1. 使用 Collections.synchronizedMap()
Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());

// 2. 使用 ConcurrentHashMap
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();

// 3. 手动同步
Map<String, String> map = new HashMap<>();
synchronized(map) {
    map.put("key", "value");
}
Q4: HashMap 的容量为什么是 2 的幂？

答案要点：

  1. 哈希计算优化：使用位运算 (n-1) & hash 代替取模运算，提高性能
  2. 均匀分布：保证哈希值在数组中均匀分布
  3. 扩容便利：扩容时元素位置要么不变，要么移动原容量位置
Q5: HashMap 的负载因子为什么是 0.75？

答案：

  1. 时间和空间的权衡：
    • 负载因子太小：浪费空间，但查找效率高
    • 负载因子太大：节省空间，但冲突增多，查找效率下降
  2. 泊松分布统计：
    • 0.75 是在时间和空间成本上寻求平衡的结果
    • 在这个负载因子下，链表长度为 8 的概率非常小
Q6: HashMap 如何处理 hash 冲突？

答案：

  1. 链表法：JDK 1.8 之前使用链表存储冲突元素
  2. 链表+红黑树：JDK 1.8 引入红黑树优化
    • 链表长度 >= 8 且数组长度 >= 64 时转为红黑树
    • 红黑树节点数 <= 6 时转回链表
Q7: HashMap 的扩容机制？

答案：

  1. 触发条件：size > capacity × loadFactor
  2. 扩容策略：容量翻倍
  3. 数据迁移：重新计算每个元素的位置
  4. JDK 1.8 优化：扩容时元素位置要么不变，要么移动到原位置+原容量的位置
Q8: HashMap 允许 null 键吗？

答案：

  • HashMap 允许一个 null 键和多个 null 值
  • null 键的哈希值被定义为 0
  • null 键存储在数组的第 0 个位置
1
2
3
4
HashMap<String, String> map = new HashMap<>();
map.put(null, "value1");     // 允许
map.put(null, "value2");     // 覆盖前一个值
map.put("key", null);        // 允许
11. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
get/put/remove O(1) O(n)
containsKey O(1) O(n)
size/isEmpty O(1) O(1)
空间复杂度
  • O(n)，其中 n 是键值对个数
12. 实际应用建议
使用场景
  1. 需要快速查找、插入、删除操作的场景
  2. 不关心元素顺序的场景
  3. 缓存实现
  4. 索引构建
注意事项
  1. 键必须正确实现 hashCode() 和 equals() 方法
  2. 存储的键应该是不可变的，或者在存储期间不改变影响哈希值的字段
  3. 预估容量大小，避免频繁扩容
  4. 多线程环境下需要同步处理
13. 高频面试代码题
自定义实现简单的 HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class SimpleHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;
    
    private Node<K, V>[] table;
    private int size;
    private int threshold;
    
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
        
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
    public SimpleHashMap() {
        table = new Node[DEFAULT_CAPACITY];
        threshold = (int) (DEFAULT_CAPACITY * LOAD_FACTOR);
    }
    
    private int hash(K key) {
        return key == null ? 0 : key.hashCode() & 0x7fffffff;
    }
    
    public V put(K key, V value) {
        int hash = hash(key);
        int index = hash % table.length;
        
        Node<K, V> node = table[index];
        if (node == null) {
            table[index] = new Node<>(hash, key, value, null);
        } else {
            while (node != null) {
                if ((node.key == key) || 
                    (node.key != null && node.key.equals(key))) {
                    V oldValue = node.value;
                    node.value = value;
                    return oldValue;
                }
                node = node.next;
            }
            table[index] = new Node<>(hash, key, value, table[index]);
        }
        
        size++;
        if (size > threshold) {
            resize();
        }
        return null;
    }
    
    public V get(K key) {
        int hash = hash(key);
        int index = hash % table.length;
        
        Node<K, V> node = table[index];
        while (node != null) {
            if ((node.key == key) || 
                (node.key != null && node.key.equals(key))) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }
    
    private void resize() {
        Node<K, V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        int newCapacity = oldCapacity << 1;
        
        @SuppressWarnings("unchecked")
        Node<K, V>[] newTable = new Node[newCapacity];
        table = newTable;
        threshold = (int) (newCapacity * LOAD_FACTOR);
        
        for (int i = 0; i < oldCapacity; i++) {
            Node<K, V> node = oldTable[i];
            while (node != null) {
                Node<K, V> next = node.next;
                int index = node.hash % newCapacity;
                node.next = newTable[index];
                newTable[index] = node;
                node = next;
            }
        }
    }
    
    public int size() {
        return size;
    }
}
正确重写 hashCode() 和 equals() 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Person {
    private String name;
    private int age;
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

4.10 LinkedHashMap详解

1. 基本概念

LinkedHashMap 是 HashMap 的子类，它通过维护一个运行于所有条目的双向链表来保证迭代顺序。它可以按照插入顺序或访问顺序进行迭代，是 HashMap 和 LinkedList 特性的结合。

2. 数据结构
继承关系
1
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
双向链表结构

LinkedHashMap 在 HashMap 的基础上增加了双向链表来维护顺序：

1
2
3
4
5
6
// 头节点和尾节点
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

// 迭代顺序模式
final boolean accessOrder;  // true 为访问顺序，false 为插入顺序
Entry 节点结构
1
2
3
4
5
6
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 维护顺序的双向链表指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
3. 核心字段
1
2
3
4
5
6
7
8
// 双向链表的头尾节点
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

// 迭代顺序控制
// true: 访问顺序 (access-order)
// false: 插入顺序 (insertion-order)
final boolean accessOrder;
4. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 默认构造方法 - 插入顺序
public LinkedHashMap() {
    super();
    accessOrder = false;
}

// 指定初始容量
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

// 指定初始容量和负载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 指定初始容量、负载因子和访问顺序
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

// 从 Map 构造
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}
5. 核心方法实现
newNode() 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);  // 链接到链表尾部
    return p;
}

// 链接到链表尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
afterNodeAccess() 方法 - 访问顺序模式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            last = b;
        else
            a.before = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}
afterNodeInsertion() 方法 - 插入后处理
1
2
3
4
5
6
7
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
removeEldestEntry() 方法
1
2
3
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;  // 默认不删除最老的条目
}
6. 三种迭代模式
1. 插入顺序（默认）
1
2
3
4
5
6
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("first", 1);
map.put("second", 2);
map.put("third", 3);

// 迭代顺序：first -> second -> third
2. 访问顺序
1
2
3
4
5
6
7
8
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("first", 1);
map.put("second", 2);
map.put("third", 3);

map.get("first");  // 访问 first

// 迭代顺序：second -> third -> first
3. LRU 模式（访问顺序 + 自定义删除策略）
1
2
3
4
5
LinkedHashMap<String, Integer> lruCache = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > MAX_ENTRIES;
    }
};
7. 与其它 Map 实现的对比
特性 HashMap LinkedHashMap TreeMap
底层结构 数组+链表/红黑树 数组+链表/红黑树+双向链表 红黑树
存储顺序 无序 插入顺序/访问顺序 排序顺序
时间复杂度 O(1) O(1) O(log n)
空间开销 较小 中等（额外链表指针） 较大
LRU 支持 否 是 否
8. 常见面试问题
Q1: LinkedHashMap 如何维护插入顺序？

答案要点：

  1. 继承 HashMap 的所有特性
  2. 每个节点增加 before 和 after 指针
  3. 维护 head 和 tail 指针跟踪链表两端
  4. 插入新节点时调用 linkNodeLast() 添加到链表尾部
1
2
3
4
5
6
7
// 插入节点时的处理
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);  // 关键：链接到链表尾部
    return p;
}
Q2: LinkedHashMap 的访问顺序模式是如何实现的？

答案：

  1. 构造时设置 accessOrder = true
  2. 访问元素时调用 afterNodeAccess() 方法
  3. 将被访问的节点移动到链表尾部
1
2
3
4
5
6
7
8
9
// 访问节点后调用
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        // 将节点移动到链表尾部
        // ... 移动逻辑
        tail = p;
    }
}
Q3: LinkedHashMap 如何实现 LRU 缓存？

答案：
通过重写 removeEldestEntry() 方法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cacheSize;
    
    public LRUCache(int cacheSize) {
        // accessOrder = true 表示按访问顺序维护
        super(16, 0.75f, true);
        this.cacheSize = cacheSize;
    }
    
    // 当 map 中的元素超过 cacheSize 时，删除最老的元素
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}
Q4: LinkedHashMap 与 HashMap 的性能对比？

答案：

操作 HashMap LinkedHashMap 说明
get/put O(1) O(1) 基本相同
remove O(1) O(1) 基本相同
迭代 O(n) O(n) LinkedHashMap 更快（顺序访问）
空间 较小 中等 LinkedHashMap 额外存储链表指针
Q5: LinkedHashMap 是线程安全的吗？

答案：

  • LinkedHashMap 不是线程安全的
  • 多线程环境下需要外部同步
  • 解决方案与 HashMap 相同：
1
2
3
4
5
// 使用 Collections.synchronizedMap()
Map<String, String> map = Collections.synchronizedMap(new LinkedHashMap<>());

// 使用 ConcurrentHashMap（但会失去顺序特性）
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();
Q6: LinkedHashMap 如何处理扩容？

答案：
LinkedHashMap 继承了 HashMap 的扩容机制：

  1. 触发条件：size > capacity × loadFactor
  2. 扩容策略：容量翻倍
  3. 数据迁移：重新计算每个元素的位置
  4. 链表维护：保持原有顺序不变
9. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
get/put/remove O(1) O(n)
containsKey O(1) O(n)
iteration O(n) O(n)
空间复杂度
  • O(n)，其中 n 是键值对个数
  • 比 HashMap 多出双向链表的存储开销
10. 实际应用建议
使用场景
  1. 需要保持插入顺序的场景
  2. LRU 缓存实现
  3. 需要按访问顺序处理元素的场景
  4. 实现固定大小的缓存
注意事项
  1. 键必须正确实现 hashCode() 和 equals() 方法
  2. 存储的键应该是不可变的，或者在存储期间不改变影响哈希值的字段
  3. 多线程环境下需要同步处理
  4. 访问顺序模式下，get() 操作也会影响顺序
11. 经典应用场景示例
LRU 缓存实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        // accessOrder = true 表示按访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当缓存大小超过容量时，删除最老的条目
        return size() > capacity;
    }
    
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        System.out.println(cache); // {1=one, 2=two, 3=three}
        
        cache.get(1); // 访问 1，将其移到末尾
        cache.put(4, "four"); // 超过容量，删除最老的 2
        System.out.println(cache); // {3=three, 1=one, 4=four}
    }
}
按插入顺序处理数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class InsertionOrderExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("first", 1);
        map.put("second", 2);
        map.put("third", 3);
        map.put("fourth", 4);
        
        // 按插入顺序遍历
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // 输出：
        // first: 1
        // second: 2
        // third: 3
        // fourth: 4
    }
}
12. 高频面试代码题
手写简单的 LinkedHashMap 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class SimpleLinkedHashMap<K, V> extends HashMap<K, V> {
    // 双向链表节点
    static class LinkedNode<K, V> extends Node<K, V> {
        LinkedNode<K, V> before, after;
        
        LinkedNode(int hash, K key, V value, Node<K, V> next) {
            super(hash, key, value, next);
        }
    }
    
    private LinkedNode<K, V> head;
    private LinkedNode<K, V> tail;
    private final boolean accessOrder;
    
    public SimpleLinkedHashMap() {
        this.accessOrder = false;
    }
    
    public SimpleLinkedHashMap(boolean accessOrder) {
        this.accessOrder = accessOrder;
    }
    
    Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
        LinkedNode<K, V> p = new LinkedNode<>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }
    
    private void linkNodeLast(LinkedNode<K, V> p) {
        LinkedNode<K, V> last = tail;
        tail = p;
        if (last == null) {
            head = p;
        } else {
            p.before = last;
            last.after = p;
        }
    }
    
    public void afterNodeAccess(Node<K, V> e) {
        LinkedNode<K, V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedNode<K, V> p = (LinkedNode<K, V>) e;
            LinkedNode<K, V> b = p.before;
            LinkedNode<K, V> a = p.after;
            
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
                
            if (a == null)
                last = b;
            else
                a.before = b;
                
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
        }
    }
}
实现带过期时间的缓存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class ExpiringCache<K, V> extends LinkedHashMap<K, CacheEntry<V>> {
    private final long expireTime;
    
    public ExpiringCache(long expireTime) {
        super(16, 0.75f, true);
        this.expireTime = expireTime;
    }
    
    public void put(K key, V value) {
        put(key, new CacheEntry<>(value, System.currentTimeMillis()));
    }
    
    public V get(Object key) {
        CacheEntry<V> entry = super.get(key);
        if (entry == null) return null;
        
        if (System.currentTimeMillis() - entry.timestamp > expireTime) {
            remove(key);
            return null;
        }
        return entry.value;
    }
    
    static class CacheEntry<V> {
        V value;
        long timestamp;
        
        CacheEntry(V value, long timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }
}

4.11 TreeMap详解

1. 基本概念

TreeMap 是基于红黑树（Red-Black tree）实现的 SortedMap 接口的具体实现。它能够按照键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序。

2. 数据结构
红黑树特性

红黑树是一种自平衡的二叉搜索树，具有以下特性：

  1. 每个节点要么是红色，要么是黑色
  2. 根节点是黑色
  3. 每个叶子节点（NIL节点）是黑色
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
节点结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;  // 默认为黑色
    
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}
3. 核心字段
1
2
3
4
private transient Entry<K,V> root;           // 根节点
private transient int size = 0;              // 节点数量
private transient int modCount = 0;          // 修改次数
private final Comparator<? super K> comparator; // 比较器
4. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 默认构造方法 - 使用键的自然顺序
public TreeMap() {
    comparator = null;
}

// 使用指定比较器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

// 从 Map 构造
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

// 从 SortedMap 构造
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}
5. 核心操作实现
put(K key, V value) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);  // 插入后调整红黑树
    size++;
    modCount++;
    return null;
}
get(Object key) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p == null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
6. 红黑树平衡操作
左旋操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}
右旋操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}
插入后调整
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;  // 新插入节点为红色

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
7. 有序性相关方法
firstKey() 和 lastKey()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public K firstKey() {
    return key(firstEntry());
}

public K lastKey() {
    return key(lastEntry());
}

final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
ceilingKey()、floorKey()、higherKey()、lowerKey()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public K ceilingKey(K key) {
    return keyOrNull(getCeilingEntry(key));
}

public K floorKey(K key) {
    return keyOrNull(getFloorEntry(key));
}

public K higherKey(K key) {
    return keyOrNull(getHigherEntry(key));
}

public K lowerKey(K key) {
    return keyOrNull(getLowerEntry(key));
}
8. 与其他 Map 实现的对比
特性 HashMap LinkedHashMap TreeMap
底层结构 数组+链表/红黑树 数组+链表/红黑树+双向链表 红黑树
存储顺序 无序 插入顺序/访问顺序 排序顺序
时间复杂度 O(1) O(1) O(log n)
空间开销 较小 中等 较大
是否有序 否 是（插入/访问顺序） 是（排序）
9. 常见面试问题
Q1: TreeMap 如何实现排序？

答案要点：

  1. 基于红黑树实现，天然有序
  2. 通过 Comparable 接口或 Comparator 进行比较
  3. 插入时根据比较结果确定节点位置
  4. 遍历时按照中序遍历（左-根-右）保证有序性
1
2
3
4
5
// 自然排序
TreeMap<Integer, String> map1 = new TreeMap<>();

// 自定义排序
TreeMap<String, String> map2 = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
Q2: TreeMap 的时间复杂度？

答案：

操作 时间复杂度 说明
get/put/remove O(log n) 红黑树的高度为 log n
first/last O(log n) 需要从根节点遍历到最左/最右节点
ceiling/floor O(log n) 需要在树中查找
size O(1) 维护了 size 字段
Q3: TreeMap 是线程安全的吗？

答案：

  • TreeMap 不是线程安全的
  • 多线程环境下需要外部同步
  • 解决方案：
1
2
3
4
5
// 使用 Collections.synchronizedSortedMap()
SortedMap<String, String> map = Collections.synchronizedSortedMap(new TreeMap<>());

// 使用 ConcurrentHashMap（Java 8+）
ConcurrentSkipListMap<String, String> map = new ConcurrentSkipListMap<>();
Q4: TreeMap 与 HashMap 的选择？

答案对比：

场景 TreeMap HashMap
需要排序 ✅ 推荐 ❌ 不适用
快速访问 ⚠️ O(log n) ✅ O(1)
范围查询 ✅ 支持 ❌ 不支持
内存占用 ⚠️ 较大 ✅ 较小
Q5: 红黑树的平衡操作有哪些？

答案：

  1. 变色：改变节点颜色
  2. 左旋：将右子节点提升为父节点
  3. 右旋：将左子节点提升为父节点

插入和删除后可能需要这些操作来维持红黑树的性质。

Q6: TreeMap 如何处理 null 值？

答案：

  • TreeMap 对键的处理：
    • 使用自然排序时，不允许 null 键（会抛出 NullPointerException）
    • 使用自定义比较器时，取决于比较器的实现
  • TreeMap 对值的处理：
    • 允许 null 值
1
2
3
4
5
6
7
8
9
10
11
12
// 使用自然排序 - 抛出异常
TreeMap<String, String> map = new TreeMap<>();
map.put(null, "value"); // NullPointerException

// 使用允许 null 的比较器
TreeMap<String, String> map2 = new TreeMap<>((s1, s2) -> {
    if (s1 == null && s2 == null) return 0;
    if (s1 == null) return -1;
    if (s2 == null) return 1;
    return s1.compareTo(s2);
});
map2.put(null, "value"); // 正常工作
10. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
get O(log n) O(log n)
put O(log n) O(log n)
remove O(log n) O(log n)
containsKey O(log n) O(log n)
空间复杂度
  • O(n)，其中 n 是键值对个数
  • 每个节点需要存储额外的指针（parent, left, right）和颜色信息
11. 实际应用建议
使用场景
  1. 需要按键排序的场景
  2. 需要范围查询的场景
  3. 需要获取第一个/最后一个元素的场景
  4. 需要获取大于/小于某个键的元素的场景
注意事项
  1. 键必须实现 Comparable 接口或提供 Comparator
  2. 性能比 HashMap 差，但提供了有序性
  3. 多线程环境下需要同步处理
12. 高频面试代码题
实现简单的二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class SimpleBST<K extends Comparable<K>, V> {
    private Node<K, V> root;
    
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> left, right;
        
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public void put(K key, V value) {
        root = put(root, key, value);
    }
    
    private Node<K, V> put(Node<K, V> node, K key, V value) {
        if (node == null) return new Node<>(key, value);
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0) 
            node.left = put(node.left, key, value);
        else if (cmp > 0)
            node.right = put(node.right, key, value);
        else
            node.value = value;
            
        return node;
    }
    
    public V get(K key) {
        Node<K, V> node = get(root, key);
        return node == null ? null : node.value;
    }
    
    private Node<K, V> get(Node<K, V> node, K key) {
        if (node == null) return null;
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0)
            return get(node.left, key);
        else if (cmp > 0)
            return get(node.right, key);
        else
            return node;
    }
}
实现范围查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class RangeQueryExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, "one");
        map.put(3, "three");
        map.put(5, "five");
        map.put(7, "seven");
        map.put(9, "nine");
        
        // 获取 [3, 7] 范围内的键值对
        SortedMap<Integer, String> subMap = map.subMap(3, true, 7, true);
        System.out.println(subMap); // {3=three, 5=five, 7=seven}
        
        // 获取小于等于 5 的键值对
        SortedMap<Integer, String> headMap = map.headMap(5, true);
        System.out.println(headMap); // {1=one, 3=three, 5=five}
        
        // 获取大于 5 的键值对
        SortedMap<Integer, String> tailMap = map.tailMap(5, false);
        System.out.println(tailMap); // {7=seven, 9=nine}
    }
}

4.12 Hashtable详解

1. 基本概念

Hashtable 是 Java 集合框架中的一个传统哈希表实现，它继承自 Dictionary 类并实现了 Map 接口。Hashtable 是线程安全的，不允许 null 键和 null 值，这与现代的 HashMap 有所不同。

2. 数据结构
底层结构

Hashtable 使用数组 + 链表的结构存储数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 存储数据的数组
private transient Entry<?,?>[] table;

// 键值对数量
private transient int count;

// 扩容阈值
private int threshold;

// 负载因子
private float loadFactor;

// 修改次数
private transient int modCount;
Entry 节点结构
1
2
3
4
5
6
7
8
9
10
11
12
13
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
    
    protected Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}
3. 核心字段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 默认初始容量
private static final int DEFAULT_CAPACITY = 11;

// 默认负载因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 存储数据的数组
private transient Entry<?,?>[] table;

// 键值对数量
private transient int count;

// 扩容阈值
private int threshold;

// 负载因子
private float loadFactor;
4. 构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 默认构造方法
public Hashtable() {
    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}

// 指定初始容量
public Hashtable(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 指定初始容量和负载因子
public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: " + loadFactor);
    
    if (initialCapacity == 0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

// 从 Map 构造
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAll(t);
}
5. 核心方法实现
put(K key, V value) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public synchronized V put(K key, V value) {
    // Hashtable 不允许 null 键和 null 值
    if (value == null) {
        throw new NullPointerException();
    }
    
    // 确保 key 不为 null
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    
    // 遍历链表查找是否已存在相同的 key
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    
    // 添加新节点
    addEntry(hash, key, value, index);
    return null;
}

private void addEntry(int hash, K key, V value, int index) {
    Entry<?,?> tab[] = table;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    
    // 创建新节点并插入到链表头部
    tab[index] = new Entry<>(hash, key, value, entry);
    count++;
    
    // 检查是否需要扩容
    if (count >= threshold) {
        rehash();
    }
}
get(Object key) 方法
1
2
3
4
5
6
7
8
9
10
11
12
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}
remove(Object key) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    
    for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}
6. 线程安全性
synchronized 关键字

Hashtable 的所有公共方法都使用 synchronized 关键字修饰：

1
2
3
4
5
public synchronized V put(K key, V value) { ... }
public synchronized V get(Object key) { ... }
public synchronized V remove(Object key) { ... }
public synchronized int size() { ... }
public synchronized boolean isEmpty() { ... }
线程安全的代价
  • 每个方法都需要获取对象锁
  • 在高并发环境下性能较差
  • 同一时刻只有一个线程能访问 Hashtable
7. 与 HashMap 的对比
特性 Hashtable HashMap
线程安全 是 否
null 键/值 不允许 允许一个 null 键，多个 null 值
继承关系 继承 Dictionary 继承 AbstractMap
初始容量 11 16
扩容策略 2倍+1 2倍
哈希计算 key.hashCode() hash(key.hashCode())
迭代器 不支持 fail-fast 支持 fail-fast
性能 较低 较高
8. 扩容机制
rehash() 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    
    // 新容量为原容量的 2 倍 + 1
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    
    // 重新哈希所有节点
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}
9. 常见面试问题
Q1: Hashtable 与 HashMap 的主要区别？

答案要点：

  1. 线程安全性：

    • Hashtable 是线程安全的（所有方法都用 synchronized 修饰）
    • HashMap 不是线程安全的

  2. null 值处理：

    • Hashtable 不允许 null 键和 null 值
    • HashMap 允许一个 null 键和多个 null 值

  3. 继承关系：

    • Hashtable 继承自 Dictionary 类
    • HashMap 继承自 AbstractMap 类

  4. 初始容量和扩容：

    • Hashtable 默认初始容量为 11，扩容为 2×原容量+1
    • HashMap 默认初始容量为 16，扩容为 2×原容量

  5. 哈希计算：

    • Hashtable 直接使用 key.hashCode()
    • HashMap 使用 hash(key.hashCode()) 优化哈希分布
Q2: Hashtable 为什么被 HashMap 取代？

答案：

  1. 性能问题：Hashtable 的同步粒度太大，导致性能较差
  2. 设计缺陷：
    • 不允许 null 值，使用不够灵活
    • 扩容策略不够高效
  3. 更好的替代方案：
    • 单线程：使用 HashMap
    • 多线程：使用 ConcurrentHashMap
Q3: Hashtable 是如何保证线程安全的？

答案：

  • Hashtable 通过在所有公共方法上使用 synchronized 关键字实现线程安全
  • 每个方法在同一时刻只能被一个线程访问
  • 但这种同步方式效率较低，因为即使简单的读操作也需要获取锁
Q4: Hashtable 的扩容策略？

答案：

  • 触发条件：count >= threshold（容量 × 负载因子）
  • 扩容公式：newCapacity = oldCapacity × 2 + 1
  • 最大容量：MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）
1
2
// 扩容代码片段
int newCapacity = (oldCapacity << 1) + 1;  // 2倍+1
Q5: Hashtable 现在还应该使用吗？

答案：
一般不推荐使用 Hashtable，原因如下：

  1. 性能较差（过度同步）
  2. 有更好的替代方案
  3. 属于遗留类

推荐替代方案：

1
2
3
4
5
6
7
8
// 单线程环境
Map<String, String> map = new HashMap<>();

// 多线程环境 - 需要完全同步
Map<String, String> map = Collections.synchronizedMap(new HashMap<>());

// 多线程环境 - 高性能
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();
Q6: Hashtable 的哈希计算？

答案：

1
int index = (hash & 0x7FFFFFFF) % tab.length;
  1. hash & 0x7FFFFFFF：将哈希值转换为正数
  2. % tab.length：取模运算确定数组索引
  3. 与 HashMap 的 hash & (length-1) 相比效率较低
10. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
get/put/remove O(1) O(n)
containsKey O(1) O(n)
size/isEmpty O(1) O(1)
空间复杂度
  • O(n)，其中 n 是键值对个数
11. 实际应用建议
何时可能还需要使用 Hashtable？
  1. 维护遗留代码
  2. 需要与只接受 Hashtable 的 API 兼容
  3. 确实需要其特定的同步语义
最佳实践
1
2
3
4
5
6
7
8
9
10
11
12
// 不推荐
Hashtable<String, String> hashtable = new Hashtable<>();

// 推荐
// 单线程
Map<String, String> map = new HashMap<>();

// 多线程 - 读写都需要同步
Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());

// 多线程 - 高性能
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();
12. 高频面试代码题
手写简单的线程安全哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class SimpleHashtable<K, V> {
    private Entry<K, V>[] table;
    private int count;
    private int threshold;
    private float loadFactor;
    private static final int DEFAULT_CAPACITY = 11;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    static class Entry<K, V> {
        final int hash;
        final K key;
        V value;
        Entry<K, V> next;
        
        Entry(int hash, K key, V value, Entry<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
    public SimpleHashtable() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    
    public SimpleHashtable(int initialCapacity, float loadFactor) {
        table = new Entry[initialCapacity];
        this.loadFactor = loadFactor;
        threshold = (int) (initialCapacity * loadFactor);
    }
    
    public synchronized V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException();
        }
        
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % table.length;
        
        for (Entry<K, V> e = table[index]; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        
        addEntry(hash, key, value, index);
        return null;
    }
    
    private void addEntry(int hash, K key, V value, int index) {
        Entry<K, V> entry = table[index];
        table[index] = new Entry<>(hash, key, value, entry);
        count++;
        
        if (count >= threshold) {
            rehash();
        }
    }
    
    public synchronized V get(Object key) {
        if (key == null) {
            throw new NullPointerException();
        }
        
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % table.length;
        
        for (Entry<K, V> e = table[index]; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }
    
    private void rehash() {
        int oldCapacity = table.length;
        Entry<K, V>[] oldTable = table;
        
        int newCapacity = (oldCapacity << 1) + 1;
        Entry<K, V>[] newTable = new Entry[newCapacity];
        
        for (int i = oldCapacity; i-- > 0;) {
            for (Entry<K, V> old = oldTable[i]; old != null;) {
                Entry<K, V> e = old;
                old = old.next;
                
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = newTable[index];
                newTable[index] = e;
            }
        }
        
        table = newTable;
        threshold = (int) (newCapacity * loadFactor);
    }
}

4.13 ConcurrentHashMap详解

1. 基本概念

ConcurrentHashMap 是 Java 并发包（java.util.concurrent）中的线程安全哈希表实现，它支持高并发的读写操作，是替代 Hashtable 和 Collections.synchronizedMap() 的首选方案。

2. 版本演进
JDK 1.7 及之前：分段锁（Segment）
  • 将数据分成多个段（Segment），每段独立加锁
  • 提高并发度，减少锁竞争
JDK 1.8 及之后：CAS + synchronized
  • 底层结构与 HashMap 相同（数组 + 链表 + 红黑树）
  • 使用 CAS 操作和 synchronized 关键字实现线程安全
  • 性能更优，实现更简单
3. JDK 1.8 核心数据结构
Node 节点
1
2
3
4
5
6
7
8
9
10
11
12
13
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    
    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
}
核心字段
1
2
3
4
5
6
7
8
9
10
11
12
13
// 存储数据的数组
transient volatile Node<K,V>[] table;

// 扩容时使用的新数组
private transient volatile Node<K,V>[] nextTable;

// 容器计数
private transient volatile int sizeCtl;

// 扩容相关字段
private transient volatile int transferIndex;
private transient volatile int baseCount;
private transient volatile long cellsBusy;
4. 核心机制
sizeCtl 字段含义
1
2
3
4
5
// sizeCtl 的不同含义：
// -1: 正在初始化
// -N: 有 N-1 个线程正在扩容
// 0: 默认值，使用默认容量
// >0: 下次扩容的阈值或初始化容量
CAS 操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 使用 Unsafe 类进行原子操作
private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
private static final long SIZECTL;
private static final long TRANSFERINDEX;
private static final long BASECOUNT;

static {
    try {
        SIZECTL = U.objectFieldOffset(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
        // ... 其他字段偏移量
    } catch (Exception e) {
        throw new Error(e);
    }
}

// CAS 操作示例
private final boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
5. 核心方法实现
put(K key, V value) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public V put(K key, V value) {
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());  // 扰动函数
    int binCount = 0;
    
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 初始化数组
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // CAS 插入到空桶
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        }
        // 正在扩容，帮助扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 对桶加锁
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 链表节点
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    // 红黑树节点
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                // 链表转红黑树
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}
get(Object key) 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 直接命中
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // 正在迁移或红黑树
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // 链表遍历
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}
initTable() 初始化数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        // 有其他线程正在初始化
        if ((sc = sizeCtl) < 0)
            Thread.yield();
        // CAS 设置 sizeCtl 为 -1，表示正在初始化
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);  // 0.75 * n
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}
6. 扩容机制
transfer() 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // 计算每个线程处理的桶数量
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE;
    
    if (nextTab == null) {
        try {
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false;
    
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        // 分配任务
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
                                         nextBound = (nextIndex > stride ?
                                                      nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        
        if (i < 0 || i >= n || i + n >= nextn) {
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n;
            }
        }
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)
            advance = true;
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    // 处理链表节点
                    if (fh >= 0) {
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        for (Node<K,V> p = f; p != lastRun; p = p.next) {
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    // 处理红黑树节点
                    else if (f instanceof TreeBin) {
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null, null);
                            if ((h & n) == 0) {
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else
                                    loTail.next = p;
                                loTail = p;
                                ++lc;
                            }
                            else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin<K,V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}
7. 与其它并发 Map 的对比
特性 ConcurrentHashMap Hashtable Collections.synchronizedMap
线程安全 是 是 是
锁粒度 细粒度（CAS+synchronized） 粗粒度（整个对象） 粗粒度（整个对象）
并发性能 高 低 低
null 值支持 否 否 是
迭代器 弱一致性 枚举器 弱一致性
8. 常见面试问题
Q1: ConcurrentHashMap 的线程安全是如何实现的？

答案要点：

  1. JDK 1.7：分段锁（Segment）

    • 将数据分成多个段，每段独立加锁
    • 提高并发度，减少锁竞争

  2. JDK 1.8：CAS + synchronized

    • 对空桶使用 CAS 操作插入
    • 对非空桶使用 synchronized 锁住头节点
    • 粒度更细，性能更好
Q2: ConcurrentHashMap 为什么不允许 null 值？

答案：

1
2
// put 方法中检查
if (key == null || value == null) throw new NullPointerException();

原因：

  1. 歧义问题：get() 返回 null 无法区分是键不存在还是值为 null
  2. 一致性：与 Hashtable 保持一致的行为
Q3: ConcurrentHashMap 的 get() 方法为什么不需要加锁？

答案：

  1. volatile 保证可见性：

    1
    2
    3
    4
    static class Node<K,V> implements Map.Entry<K,V> {
        volatile V val;
        volatile Node<K,V> next;
    }

  2. 原子性操作：Node 的属性使用 volatile 修饰，保证了读取的可见性

  3. 弱一致性：允许读取到稍旧的数据，但保证不会出错

Q4: ConcurrentHashMap 的扩容机制？

答案：

  1. 触发条件：链表长度 >= 8 且数组长度 < 64 时扩容
  2. 扩容策略：容量翻倍
  3. 多线程协助：其他线程访问时会帮助扩容
  4. 渐进式扩容：不是一次性完成，而是分批次进行
Q5: ConcurrentHashMap 与 Hashtable 的性能对比？

答案：

操作 ConcurrentHashMap Hashtable
get 无锁 需要锁
put 部分锁 需要锁
并发度 高 低
吞吐量 高 低
Q6: ConcurrentHashMap 的 size() 方法如何实现？

答案：
JDK 1.8 中的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

使用 baseCount + CounterCell 数组来统计，避免全局锁。

9. 性能分析
时间复杂度
操作 平均时间复杂度 最坏时间复杂度
get O(1) O(n)
put O(1) O(n)
remove O(1) O(n)
空间复杂度
  • O(n)，其中 n 是键值对个数
10. 实际应用建议
使用场景
  1. 高并发读写场景
  2. 缓存实现
  3. 需要线程安全的 Map
  4. 替代 Hashtable 的场景
注意事项
  1. 不允许 null 键和 null 值
  2. 迭代器是弱一致性的，不会抛出 ConcurrentModificationException
  3. size() 方法返回的是近似值
  4. 不同版本实现差异较大，注意兼容性
11. 经典应用场景示例
缓存实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class SimpleCache<K, V> {
    private final ConcurrentHashMap<K, V> cache = new ConcurrentHashMap<>();
    private final int maxSize;
    
    public SimpleCache(int maxSize) {
        this.maxSize = maxSize;
    }
    
    public V get(K key) {
        return cache.get(key);
    }
    
    public V put(K key, V value) {
        if (cache.size() >= maxSize) {
            // 简单的淘汰策略：移除第一个元素
            Iterator<K> iterator = cache.keySet().iterator();
            if (iterator.hasNext()) {
                cache.remove(iterator.next());
            }
        }
        return cache.put(key, value);
    }
}
计数器应用
1
2
3
4
5
6
7
8
9
10
11
12
13
public class WordCount {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Long> wordCount = new ConcurrentHashMap<>();
        String[] words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
        
        // 使用 computeIfAbsent 和 computeIfPresent
        for (String word : words) {
            wordCount.compute(word, (k, v) -> (v == null) ? 1L : v + 1);
        }
        
        System.out.println(wordCount); // {apple=3, banana=2, cherry=1}
    }
}
12. 高频面试代码题
手写简单的 ConcurrentHashMap（简化版）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class SimpleConcurrentHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private volatile Node<K, V>[] table;
    private volatile int size = 0;
    
    static class Node<K, V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K, V> next;
        
        Node(int hash, K key, V val, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }
    
    public SimpleConcurrentHashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }
    
    private int hash(K key) {
        return key.hashCode() & 0x7fffffff;
    }
    
    public V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException();
        }
        
        int hash = hash(key);
        int index = hash % table.length;
        
        synchronized (this) {
            Node<K, V> head = table[index];
            if (head == null) {
                table[index] = new Node<>(hash, key, value, null);
                size++;
                return null;
            }
            
            Node<K, V> current = head;
            while (current != null) {
                if (current.hash == hash && current.key.equals(key)) {
                    V oldValue = current.val;
                    current.val = value;
                    return oldValue;
                }
                current = current.next;
            }
            
            table[index] = new Node<>(hash, key, value, head);
            size++;
            return null;
        }
    }
    
    public V get(K key) {
        int hash = hash(key);
        int index = hash % table.length;
        
        Node<K, V> current = table[index];
        while (current != null) {
            if (current.hash == hash && current.key.equals(key)) {
                return current.val;
            }
            current = current.next;
        }
        return null;
    }
    
    public int size() {
        return size;
    }
}

五、如何选择集合类？

这是一个非常常见的面试题和实践问题。选择依据主要基于以下几点：

  1. 是否需要键值对？

    • 否 -> 选择 Collection 接口下的实现。
      • 元素是否允许重复？
        • 是 -> List
          • 是否频繁在中间增删？
            • 是 -> LinkedList
            • 否 -> ArrayList (默认选择)
        • 否 -> Set
          • 是否需要排序？
            • 是 -> TreeSet
            • 否 -> 是否需要保持插入顺序？
              • 是 -> LinkedHashSet
              • 否 -> HashSet (默认选择)
    • 是 -> 选择 Map 接口下的实现。
      • 是否需要排序？
        • 是 -> TreeMap
        • 否 -> 是否需要保持插入顺序？
          • 是 -> LinkedHashMap
          • 否 -> HashMap (默认选择)

  2. 是否需要线程安全？

    • 如果集合在多线程环境下使用，不能简单地使用 ArrayList 或 HashMap。
    • 解决方案：
      • 使用 java.util.concurrent 包下的线程安全集合类，如 ConcurrentHashMap、CopyOnWriteArrayList。（推荐）
      • 使用 Collections.synchronizedList(list)、Collections.synchronizedMap(map) 等包装方法，将非线程安全的集合包装成线程安全的。（性能较差）

六、工具类：Collections

Collections 是一个工具类，提供了大量静态方法用于操作集合（排序、搜索、同步、不可变集合等）。

  • 排序：Collections.sort(list) / Collections.sort(list, comparator)
  • 打乱：Collections.shuffle(list)
  • 反转：Collections.reverse(list)
  • 线程安全包装：Collections.synchronizedList(list), Collections.synchronizedMap(map)
  • 不可变（只读）集合：Collections.unmodifiableList(list), Collections.unmodifiableMap(map) (创建后不能被修改)

七、总结与最佳实践

  1. 掌握体系结构：理解 Collection 和 Map 两大分支及其子接口的区别。

  2. 精通实现原理：特别是 ArrayList、LinkedList、HashMap 的底层实现和区别，这是面试核心。

  3. 正确选择集合：根据“是否键值对”、“是否允许重复”、“是否要求有序”、“是否需要排序”、“是否线程安全”等条件来选择最合适的集合类。

  4. 使用泛型：始终使用泛型来保证类型安全，避免运行时 ClassCastException。

    1
    2
    3
    4
    // Good
    List<String> list = new ArrayList<>();
    // Bad (Raw type, avoid it!)
    List list = new ArrayList();

  5. 覆盖 equals 和 hashCode：如果你自定义类的对象要作为 HashSet 的元素或 HashMap 的 Key，必须正确重写 equals() 和 hashCode() 方法，并且要保证两个方法的一致性（即 equals 为 true 的两个对象，其 hashCode 必须相同）。

希望这份详细的解析能帮助你彻底理解 Java 集合框架！