Java 集合框架完全指南

本文系统性地介绍 Java 集合框架的核心概念、实现原理和设计模式。内容涵盖集合框架体系结构、列表与队列机制、哈希表家族的扩缩容策略、缓存淘汰算法实现以及系统级扩缩容设计。通过深入分析源码实现和性能特征，帮助理解各集合类的适用场景和最佳实践。

第一章：全景导图

文章结构

mindmap
  root((Java集合框架完全指南))
    集合框架体系
      Iterable接口
      Collection体系
      Map体系
      Sorted接口
      Navigable接口
      抽象类层次
    列表与队列
      ArrayList扩缩容
      队列六操作
      PriorityQueue
      DelayQueue
      Deque体系
    哈希表家族
      HashMap结构
      扩容机制
      扰动函数
      树化反树化
      ConcurrentHashMap
      LinkedHashMap
      EnumSet/Map
      IdentityHashMap
      WeakHashMap
    缓存淘汰策略
      LRU缓存
      LFU缓存
      LinkedHashMap实现
      Guava Cache
      Caffeine Cache
    系统级扩缩容
      分片扩容
      一致性哈希
      动态扩缩容
      负载均衡

模式总览

模式名	口诀	覆盖场景
扩容因子1.5倍	扩容1.5倍，平衡空间时间	ArrayList扩容、StringBuilder扩容
队列六操作	add/offer/put，peek，poll/take	所有队列实现的标准操作
优先级堆	小顶堆TopK，大顶堆调度	PriorityQueue、任务调度
延迟队列	getDelay负值出队，compareTo排序	DelayQueue、缓存过期、订单超时
扰动函数	高16异或低16，分散哈希冲突	HashMap哈希优化
2的幂容量	位运算取余，快速计算索引	HashMap、ConcurrentHashMap
树化阈值8	泊松分布概率，红黑树优化	HashMap性能优化
反树化阈值6	低于阈值退化，避免频繁转换	HashMap内存优化
LRU缓存	访问移末尾， eldest移除	LinkedHashMap、Guava Cache
位向量存储	枚举位运算，O(1)操作	EnumSet、RegularEnumSet
数组存储映射	枚举索引映射，遍历有序	EnumMap
引用相等	==而非equals，深拷贝序列化	IdentityHashMap
弱引用键	弱引用GC，自动清理	WeakHashMap、元数据关联
写时复制	读快写慢，迭代一致	CopyOnWriteArrayList

第二章：集合框架体系

UML 类图

classDiagram
    class Iterable {
        <<interface>>
        +iterator() Iterator~T~
        +forEach(Consumer~? super T~) void
    }
    
    class Collection {
        <<interface>>
        +size() int
        +isEmpty() boolean
        +contains(Object) boolean
        +iterator() Iterator~T~
        +toArray() Object[]
        +add(E) boolean
        +remove(Object) boolean
        +containsAll(Collection~?) boolean
        +addAll(Collection~? extends E~) boolean
        +removeAll(Collection~?) boolean
        +retainAll(Collection~?) boolean
        +clear() void
        +stream() Stream~T~
    }
    
    class List {
        <<interface>>
        +add(int, E) void
        +addAll(int, Collection~? extends E~) boolean
        +get(int) E
        +set(int, E) E
        +remove(int) E
        +indexOf(Object) int
        +lastIndexOf(Object) int
        +listIterator() ListIterator~E~
        +subList(int, int) List~E~
    }
    
    class Set {
        <<interface>>
    }
    
    class Queue {
        <<interface>>
        +add(E) boolean
        +offer(E) boolean
        +remove() E
        +poll() E
        +element() E
        +peek() E
    }
    
    class Deque {
        <<interface>>
        +addFirst(E) void
        +addLast(E) void
        +offerFirst(E) boolean
        +offerLast(E) boolean
        +removeFirst() E
        +removeLast() E
        +pollFirst() E
        +pollLast() E
        +getFirst() E
        +getLast() E
        +peekFirst() E
        +peekLast() E
        +removeFirstOccurrence(Object) boolean
        +removeLastOccurrence(Object) boolean
    }
    
    class Map {
        <<interface>>
        +size() int
        +isEmpty() boolean
        +containsKey(Object) boolean
        +containsValue(Object) boolean
        +get(Object) V
        +put(K, V) V
        +remove(Object) V
        +putAll(Map~? extends K, ? extends V~) void
        +clear() void
        +keySet() Set~K~
        +values() Collection~V~
        +entrySet() Set~Map.Entry~K,V~~
    }
    
    class SortedSet {
        <<interface>>
        +comparator() Comparator~? super E~
        +subSet(E, E) SortedSet~E~
        +headSet(E) SortedSet~E~
        +tailSet(E) SortedSet~E~
        +first() E
        +last() E
    }
    
    class SortedMap {
        <<interface>>
        +comparator() Comparator~? super K~
        +subMap(K, K) SortedMap~K,V~
        +headMap(K) SortedMap~K,V~
        +tailMap(K) SortedMap~K,V~
        +firstKey() K
        +lastKey() K
    }
    
    class NavigableSet {
        <<interface>>
        +lower(E) E
        +floor(E) E
        +ceiling(E) E
        +higher(E) E
        +pollFirst() E
        +pollLast() E
        +descendingIterator() Iterator~E~
        +descendingSet() NavigableSet~E~
        +subSet(E, boolean, E, boolean) NavigableSet~E~
        +headSet(E, boolean) NavigableSet~E~
        +tailSet(E, boolean) NavigableSet~E~
    }
    
    class NavigableMap {
        <<interface>>
        +lower(K) K
        +floor(K) K
        +ceiling(K) K
        +higher(K) K
        +lowerEntry(K) Map.Entry~K,V~
        +floorEntry(K) Map.Entry~K,V~
        +ceilingEntry(K) Map.Entry~K,V~
        +higherEntry(K) Map.Entry~K,V~
        +firstEntry() Map.Entry~K,V~
        +lastEntry() Map.Entry~K,V~
        +pollFirstEntry() Map.Entry~K,V~
        +pollLastEntry() Map.Entry~K,V~
        +descendingMap() NavigableMap~K,V~
        +navigableKeySet() NavigableSet~K~
        +subMap(K, boolean, K, boolean) NavigableMap~K,V~
        +headMap(K, boolean) NavigableMap~K,V~
        +tailMap(K, boolean) NavigableMap~K,V~
    }
    
    class AbstractCollection {
        <<abstract>>
        +iterator() Iterator~T~
        +size() int
    }
    
    class AbstractList {
        <<abstract>>
    }
    
    class AbstractSequentialList {
        <<abstract>>
    }
    
    class AbstractSet {
        <<abstract>>
    }
    
    class AbstractMap {
        <<abstract>>
    }
    
    class AbstractQueue {
        <<abstract>>
    }
    
    class ArrayList {
        -elementData Object[]
        -size int
        +ArrayList()
        +ArrayList(int)
        +ensureCapacity(int)
        +trimToSize()
    }
    
    class LinkedList {
        -first Node~E~
        -last Node~E~
        +LinkedList()
        +addFirst(E)
        +addLast(E)
    }
    
    class HashSet {
        -map HashMap~E,Object~
        +HashSet()
        +HashSet(int)
        +HashSet(int, float)
    }
    
    class LinkedHashSet {
        +LinkedHashSet()
        +LinkedHashSet(int)
        +LinkedHashSet(int, float)
    }
    
    class TreeSet {
        -m NavigableMap~E,Object~
        +TreeSet()
        +TreeSet(Comparator~? super E~)
    }
    
    class PriorityQueue {
        -queue Object[]
        +PriorityQueue()
        +PriorityQueue(int)
        +PriorityQueue(Comparator~? super E~)
    }
    
    class DelayQueue {
        -q PriorityQueue~E extends Delayed~
        +DelayQueue()
        +put(E)
        +take() E
    }
    
    class ArrayDeque {
        -elements Object[]
        -head int
        -tail int
        +ArrayDeque()
        +addFirst(E)
        +addLast(E)
    }
    
    class HashMap {
        -table Node~K,V~[]
        -size int
        -loadFactor float
        -threshold int
        +HashMap()
        +HashMap(int)
        +HashMap(int, float)
        +put(K, V) V
        +get(Object) V
    }
    
    class LinkedHashMap {
        -accessOrder boolean
        +LinkedHashMap()
        +LinkedHashMap(int, float, boolean)
        +removeEldestEntry(Map.Entry)
    }
    
    class WeakHashMap {
        -table Entry~K,V~[]
        +WeakHashMap()
        +WeakHashMap(int)
    }
    
    class ConcurrentHashMap {
        -table Node~K,V~[]
        -sizeCtl long
        +ConcurrentHashMap()
        +put(K, V) V
        +get(Object) V
    }
    
    class EnumSet {
        +noneOf(Class~E~)
        +of(E...)
        +allOf(Class~E~)
        +range(E, E)
        +complementOf(EnumSet~E~)
    }
    
    class EnumMap {
        -keyUniverse K[]
        -vals Object[]
        +EnumMap(Class~K~)
        +put(K, V) V
        +get(Object) V
    }
    
    class IdentityHashMap {
        -table Object[]
        +IdentityHashMap()
        +put(K, V) V
    }
    
    class TreeMap {
        -root Entry~K,V~
        -comparator Comparator~? super K~
        +TreeMap()
        +TreeMap(Comparator~? super K~)
    }
    
    Iterable <|.. Collection
    Iterable <|.. Map
    Collection <|-- List
    Collection <|-- Set
    Collection <|-- Queue
    Collection <|-- AbstractCollection
    List <|-- SortedSet
    SortedSet <|-- NavigableSet
    Set <|-- SortedSet
    Queue <|-- Deque
    Map <|-- SortedMap
    SortedMap <|-- NavigableMap
    AbstractCollection <|-- AbstractList
    AbstractCollection <|-- AbstractSet
    AbstractCollection <|-- AbstractQueue
    AbstractList <|-- ArrayList
    AbstractList <|-- AbstractSequentialList
    AbstractSequentialList <|-- LinkedList
    AbstractSet <|-- HashSet
    HashSet <|-- LinkedHashSet
    AbstractSet <|-- TreeSet
    AbstractQueue <|-- PriorityQueue
    AbstractQueue <|-- ArrayDeque
    Deque <|-- LinkedList
    Deque <|-- ArrayDeque
    Queue <|-- PriorityQueue
    PriorityQueue <|-- DelayQueue
    AbstractMap <|-- HashMap
    AbstractMap <|-- TreeMap
    AbstractMap <|-- WeakHashMap
    AbstractMap <|-- IdentityHashMap
    HashMap <|-- LinkedHashMap
    HashMap <|-- ConcurrentHashMap

核心接口说明

Sorted 接口

SortedSet 和 SortedMap 提供了基于全序关系（total ordering）的有序集合操作。

接口特性

• 引入版本：JDK 1.2
• 核心概念：维护元素的全序关系
• 三类操作：范围子集、首尾元素、比较器

// SortedSet 示例
SortedSet<Integer> sortedSet = new TreeSet<>();
sortedSet.addAll(Arrays.asList(1, 3, 5, 7, 9));

// 获取比较器
Comparator<? super Integer> comparator = sortedSet.comparator();
System.out.println("Comparator: " + comparator);

// 范围子集 [3, 7)
SortedSet<Integer> subSet = sortedSet.subSet(3, 7);
System.out.println("SubSet [3, 7): " + subSet); // [3, 5]

// 前缀子集 [0, 5)
SortedSet<Integer> headSet = sortedSet.headSet(5);
System.out.println("HeadSet [0, 5): " + headSet); // [1, 3]

// 后缀子集 [7, ∞)
SortedSet<Integer> tailSet = sortedSet.tailSet(7);
System.out.println("TailSet [7, ∞): " + tailSet); // [7, 9]

// 首尾元素
System.out.println("First: " + sortedSet.first()); // 1
System.out.println("Last: " + sortedSet.last()); // 9

// SortedMap 示例
SortedMap<Integer, String> sortedMap = new TreeMap<>();
sortedMap.put(1, "A");
sortedMap.put(3, "C");
sortedMap.put(5, "E");
sortedMap.put(7, "G");
sortedMap.put(9, "I");

// 范围子集 [3, 7)
SortedMap<Integer, String> subMap = sortedMap.subMap(3, 7);
System.out.println("SubMap [3, 7): " + subMap); // {3=C, 5=E}

// 前缀子集 [0, 5)
SortedMap<Integer, String> headMap = sortedMap.headMap(5);
System.out.println("HeadMap [0, 5): " + headMap); // {1=A, 3=C}

// 后缀子集 [7, ∞)
SortedMap<Integer, String> tailMap = sortedMap.tailMap(7);
System.out.println("TailMap [7, ∞): " + tailMap); // {7=G, 9=I}

// 首尾键值
System.out.println("FirstKey: " + sortedMap.firstKey()); // 1
System.out.println("LastKey: " + sortedMap.lastKey()); // 9

Navigable 接口

NavigableSet 和 NavigableMap 扩展了 Sorted 接口，提供了导航方法（navigation methods）用于查找邻近元素。

接口特性

• 引入版本：JDK 1.6
• 核心方法：lower、floor、ceiling、higher
• 扩展功能：降序视图、精确范围视图

导航方法

NavigableSet<Integer> navigableSet = new TreeSet<>();
navigableSet.addAll(Arrays.asList(1, 3, 5, 7, 9));

// lower(E e): 返回严格小于 e 的最大元素
System.out.println("lower(5): " + navigableSet.lower(5)); // 3

// floor(E e): 返回小于等于 e 的最大元素
System.out.println("floor(5): " + navigableSet.floor(5)); // 5

// ceiling(E e): 返回大于等于 e 的最小元素
System.out.println("ceiling(5): " + navigableSet.ceiling(5)); // 5

// higher(E e): 返回严格大于 e 的最小元素
System.out.println("higher(5): " + navigableSet.higher(5)); // 7

// 非存在元素测试
System.out.println("lower(4): " + navigableSet.lower(4)); // 3
System.out.println("floor(4): " + navigableSet.floor(4)); // 3
System.out.println("ceiling(4): " + navigableSet.ceiling(4)); // 5
System.out.println("higher(4): " + navigableSet.higher(4)); // 5

NavigableMap<Integer, String> navigableMap = new TreeMap<>();
navigableMap.put(1, "A");
navigableMap.put(3, "C");
navigableMap.put(5, "E");
navigableMap.put(7, "G");
navigableMap.put(9, "I");

// 导航方法
System.out.println("lowerEntry(5): " + navigableMap.lowerEntry(5)); // 3=C
System.out.println("floorEntry(5): " + navigableMap.floorEntry(5)); // 5=E
System.out.println("ceilingEntry(5): " + navigableMap.ceilingEntry(5)); // 5=E
System.out.println("higherEntry(5): " + navigableMap.higherEntry(5)); // 7=E

// pollFirstEntry 和 pollLastEntry
Map.Entry<Integer, String> first = navigableMap.pollFirstEntry();
System.out.println("Polled first: " + first); // 1=A
System.out.println("Remaining: " + navigableMap); // {3=C, 5=E, 7=G, 9=I}

范围视图

NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));

// 精确范围视图：[3, 7]（包含边界）
NavigableSet<Integer> inclusiveRange = set.subSet(3, true, 7, true);
System.out.println("Inclusive [3, 7]: " + inclusiveRange); // [3, 4, 5, 6, 7]

// 半开范围视图：[3, 7)（左闭右开）
NavigableSet<Integer> halfOpenRange = set.subSet(3, true, 7, false);
System.out.println("HalfOpen [3, 7): " + halfOpenRange); // [3, 4, 5, 6]

// 开区间视图：(3, 7)（不包含边界）
NavigableSet<Integer> openRange = set.subSet(3, false, 7, false);
System.out.println("Open (3, 7): " + openRange); // [4, 5, 6]

NavigableMap<Integer, String> map = new TreeMap<>();
for (int i = 1; i <= 9; i++) {
    map.put(i, String.valueOf((char) (64 + i)));
}

// 精确范围视图：[3, 7]
NavigableMap<Integer, String> inclusiveRange = map.subMap(3, true, 7, true);
System.out.println("Inclusive [3, 7]: " + inclusiveRange); // {3=C, 4=D, 5=E, 6=F, 7=G}

降序视图

NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));

// 降序视图
NavigableSet<Integer> descendingSet = set.descendingSet();
System.out.println("Descending: " + descendingSet); // [9, 7, 5, 3, 1]

// 降序迭代器
Iterator<Integer> descendingIterator = set.descendingIterator();
System.out.print("Descending iteration: ");
while (descendingIterator.hasNext()) {
    System.out.print(descendingIterator.next() + " ");
}
// 输出: 9 7 5 3 1

NavigableMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(3, "C");
map.put(5, "E");

// 降序视图
NavigableMap<Integer, String> descendingMap = map.descendingMap();
System.out.println("Descending: " + descendingMap); // {5=E, 3=C, 1=A}

AbstractList 与 AbstractSequentialList

AbstractList

• 定位：随机访问列表的抽象基类
• 核心方法：get(int index)、size()
• 实现类：ArrayList、Vector、AbstractList 的子类

AbstractSequentialList

• 定位：顺序访问列表的抽象基类
• 核心方法：listIterator(int index)
• 实现类：LinkedList

区别总结

特性	AbstractList	AbstractSequentialList
访问方式	随机访问	顺序访问
核心方法	get(int index)	listIterator(int index)
性能特征	O(1) 索引访问	O(n) 索引访问
典型实现	ArrayList	LinkedList

// AbstractList 子类实现示例
class MyArrayList<E> extends AbstractList<E> {
    private Object[] elementData;
    private int size;
    
    public MyArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity];
        this.size = 0;
    }
    
    @Override
    public E get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (E) elementData[index];
    }
    
    @Override
    public int size() {
        return size;
    }
    
    @Override
    public boolean add(E e) {
        ensureCapacity(size + 1);
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length) {
            Object[] newData = new Object[elementData.length * 2];
            System.arraycopy(elementData, 0, newData, 0, size);
            elementData = newData;
        }
    }
}

// AbstractSequentialList 子类实现示例
class MyLinkedList<E> extends AbstractSequentialList<E> {
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        
        Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
    
    private Node<E> first;
    private Node<E> last;
    private int size;
    
    @Override
    public ListIterator<E> listIterator(int index) {
        return new ListItr(index);
    }
    
    @Override
    public int size() {
        return size;
    }
    
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        
        ListItr(int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException();
            }
            if (index < (size >> 1)) {
                next = first;
                for (int i = 0; i < index; i++) {
                    next = next.next;
                }
            } else {
                next = null;
                for (int i = size - 1; i >= index; i--) {
                    next = (next == null) ? last : next.prev;
                }
            }
            nextIndex = index;
        }
        
        @Override
        public boolean hasNext() {
            return nextIndex < size;
        }
        
        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
        
        @Override
        public boolean hasPrevious() {
            return nextIndex > 0;
        }
        
        @Override
        public E previous() {
            if (!hasPrevious()) {
                throw new NoSuchElementException();
            }
            lastReturned = (next == null) ? last : next.prev;
            next = lastReturned;
            nextIndex--;
            return lastReturned.item;
        }
        
        @Override
        public int nextIndex() {
            return nextIndex;
        }
        
        @Override
        public int previousIndex() {
            return nextIndex - 1;
        }
        
        @Override
        public void set(E e) {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            lastReturned.item = e;
        }
        
        @Override
        public void add(E e) {
            lastReturned = null;
            if (next == null) {
                linkLast(e);
            } else {
                linkBefore(e, next);
            }
            nextIndex++;
        }
        
        @Override
        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned) {
                next = lastNext;
            } else {
                nextIndex--;
            }
            lastReturned = null;
        }
    }
    
    private 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;
        }
        size++;
    }
    
    private void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null) {
            first = newNode;
        } else {
            pred.next = newNode;
        }
        size++;
    }
    
    private void unlink(Node<E> x) {
        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;
        size--;
    }
}

🔑 模式提炼：抽象基类选择

当实现自定义集合时，根据访问模式选择合适的抽象基类：随机访问选择 AbstractList，顺序访问选择 AbstractSequentialList。这确保了实现类能够提供最优的性能特征。

fail-fast 与 fail-safe 机制

Java 集合框架提供了两种迭代器行为机制：fail-fast（快速失败）和 fail-safe（安全失败）。

fail-fast 原理

fail-fast 是 Java 集合的默认行为，通过 modCount 字段实现。每次集合结构发生修改（增加、删除元素）时，modCount 会递增。迭代器在创建时记录当前的 modCount 值为 expectedModCount，每次调用 next() 时都会检查两者是否一致。

// ArrayList 的迭代器实现（简化）
private class Itr implements Iterator<E> {
    int cursor;
    int lastRet = -1;
    int expectedModCount = modCount; // 创建时记录 modCount

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification(); // 每次调用 next() 都检查
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

触发条件

fail-fast 异常在以下情况触发：

1. 在迭代过程中，通过集合本身（而非迭代器的方法）修改集合结构
2. 多线程环境下，一个线程在迭代时，另一个线程修改了集合

// 错误示例：在迭代时通过集合本身删除元素
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (String item : list) {
    if ("B".equals(item)) {
        list.remove("B"); // 抛出 ConcurrentModificationException
    }
}

正确的迭代器删除方式

// 正确示例：使用迭代器的 remove() 方法
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if ("B".equals(item)) {
        iterator.remove(); // 正确：通过迭代器删除
    }
}

// 或者使用 removeIf（Java 8+）
list.removeIf("B"::equals);

fail-safe 机制

fail-safe 机制不会抛出 ConcurrentModificationException，因为它操作的是集合的快照副本。

代表实现

• CopyOnWriteArrayList：迭代时复制整个数组
• ConcurrentHashMap：迭代器基于创建时的快照
• CopyOnWriteArraySet：基于 CopyOnWriteArrayList

// CopyOnWriteArrayList 示例
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (String item : list) {
    if ("B".equals(item)) {
        list.remove("B"); // 不会抛出异常
    }
}
System.out.println(list); // 输出：[A, C]

fail-safe 原理

// CopyOnWriteArrayList 的迭代器（简化）
static final class COWIterator<E> implements ListIterator<E> {
    private final Object[] snapshot; // 快照数组
    private int cursor;

    COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements; // 保存创建时的数组快照
    }

    public boolean hasNext() {
        return cursor < snapshot.length;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (!hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++]; // 遍历快照，不检查 modCount
    }
}

机制对比

特性	fail-fast	fail-safe
异常行为	抛出 ConcurrentModificationException	不抛出异常
数据一致性	反映迭代时的实时状态	反映迭代器创建时的快照
内存开销	低	高（需要复制数据）
性能	高	低（复制操作）
典型实现	ArrayList、HashMap、LinkedList	CopyOnWriteArrayList、ConcurrentHashMap
适用场景	单线程或需要检测并发修改	多线程且允许弱一致性

注意事项

1. fail-fast 不保证一定抛出异常：这是 Java 文档明确说明的，仅作为一种 best-effort 的 bug 检测机制
2. fail-safe 存在数据不一致：迭代期间集合的修改不会反映到迭代器中
3. 性能权衡：fail-safe 机制通过牺牲内存和性能换取安全性

🔑 模式提炼： fail-fast 是一种防御性编程机制，用于快速发现并发修改错误。fail-safe 则适用于多线程场景，通过快照机制避免并发修改异常，但需要权衡内存和性能开销。

第三章：列表与队列

3.1 ArrayList 扩缩容机制

内部结构

ArrayList 内部维护两个核心字段：

public class ArrayList<E> extends AbstractList<E> {
    // 存储元素的数组
    transient Object[] elementData;
    
    // 实际元素数量
    private int size;
    
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
}

关键特性

• elementData：动态数组，可能大于实际元素数量
• size：实际元素数量，始终 ≤ elementData.length
• 空构造器创建时，elementData 为空数组，首次添加时扩容到 10

扩容因子 1.5 倍

ArrayList 的扩容因子为 1.5 倍，即新容量 = 旧容量 + (旧容量 >> 1)。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    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);
}

为什么选择 1.5 倍？

1. vs 2 倍扩容

扩容因子	优点	缺点
2 倍	位运算简单	内存浪费严重，扩容后可能长期空闲
1.5 倍	内存利用率高	计算略复杂（加右移）

2. vs 黄金比例 (1.618)

• 黄金比例在理论上是最优的，但 1.5 倍实现更简单
• 1.5 倍已经足够接近最优解，避免了复杂的浮点运算

3. 均摊分析

假设初始容量为 1，插入 n 个元素：

扩容次数：log₂(n)
总拷贝次数：1 + 2 + 4 + ... + n/2 = n - 1
均摊拷贝次数：(n - 1) / n ≈ 1

因此，均摊时间复杂度为 O(1)。

集合初始容量选择指南

合理设置集合的初始容量可以避免不必要的扩容操作，提高性能。根据对元素数量的了解程度，选择不同的容量设置策略。

容量选择决策表

元素数量了解程度	推荐策略	理由
确切已知	设置为元素数量	避免任何扩容，性能最优
可估算范围	设置为估算值	减少扩容次数，预留少量空间
完全未知	使用默认值	避免过度预分配浪费内存

** ArrayList 容量选择**

// 错误示例：使用默认容量，导致多次扩容
List<Integer> list = new ArrayList<>(); // 默认容量 10
for (int i = 0; i < 1000; i++) {
    list.add(i);
}
// 扩容次数：log₂(1000) ≈ 10 次

// 正确示例：设置初始容量为 1000，避免扩容
List<Integer> list = new ArrayList<>(1000);
for (int i = 0; i < 1000; i++) {
    list.add(i);
}
// 扩容次数：0 次

HashMap 容量选择

HashMap 的初始容量需要考虑负载因子（默认 0.75）。为了避免扩容，初始容量应设置为 元素数量 / 0.75 + 1。

// 错误示例：直接设置为元素数量，仍会扩容
Map<String, Integer> map = new HashMap<>(1000);
for (int i = 0; i < 1000; i++) {
    map.put("key" + i, i);
}
// 实际触发扩容阈值：1000 * 0.75 = 750
// 扩容次数：1 次

// 正确示例：考虑负载因子，避免扩容
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75) + 1;
Map<String, Integer> map = new HashMap<>(initialCapacity);
for (int i = 0; i < 1000; i++) {
    map.put("key" + i, i);
}
// 扩容次数：0 次

StringBuilder 容量选择

StringBuilder 的初始容量需要考虑额外空间。已知字符串长度为 n 时，初始容量应设置为 n + 16（16 是 StringBuilder 的默认额外空间）。

// 错误示例：使用默认容量，导致多次扩容
StringBuilder sb = new StringBuilder(); // 默认容量 16
for (int i = 0; i < 1000; i++) {
    sb.append("Item ").append(i).append("\n");
}
// 扩容次数：约 10 次

// 正确示例：预估最终长度，设置初始容量
int estimatedLength = 1000 * 10; // 每行约 10 字符
StringBuilder sb = new StringBuilder(estimatedLength + 16);
for (int i = 0; i < 1000; i++) {
    sb.append("Item ").append(i).append("\n");
}
// 扩容次数：0 次

容量设置对比

场景	错误设置	正确设置	性能提升
ArrayList 存储 1000 元素	new ArrayList<>()	new ArrayList<>(1000)	避免约 10 次扩容
HashMap 存储 1000 键值对	new HashMap<>(1000)	new HashMap<>(1334)	避免扩容
StringBuilder 拼接 10000 字符	new StringBuilder()	new StringBuilder(10016)	避免约 13 次扩容

注意事项

1. 避免过度预分配：如果预估的容量远大于实际使用，会造成内存浪费
2. 考虑增长空间：如果集合会持续增长，可以预留 20%-30% 的额外空间
3. 权衡内存与性能：内存紧张时使用默认值，性能敏感时精确设置容量
4. 使用工具方法：Guava 提供了 Maps.newHashMapWithExpectedSize() 等工具方法

// Guava 工具方法示例
import com.google.common.collect.Maps;

// 自动计算合适的初始容量
Map<String, Integer> map = Maps.newHashMapWithExpectedSize(1000);

🔑 模式提炼： 集合初始容量的设置体现了"预分配优化"的思想。在能够预估元素数量的情况下，合理设置初始容量可以显著提高性能，避免扩容带来的性能损耗。

扩容流程

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) {
    modCount++;
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

扩容示例

ArrayList<Integer> list = new ArrayList<>(); // elementData = []
list.add(1); // 扩容到 10，elementData = [1, null, null, ...]
// 依次添加到第 10 个元素
list.add(2);
list.add(3);
// ...
list.add(10); // elementData = [1, 2, 3, ..., 10]

list.add(11); // 触发扩容：10 → 15
// elementData = [1, 2, 3, ..., 10, 11, null, null, null, null]

list.add(16); // 触发扩容：15 → 22

缩容机制

ArrayList 不会自动缩容，即使删除了大量元素。需要手动调用 trimToSize() 方法。

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0) 
            ? EMPTY_ELEMENTDATA 
            : Arrays.copyOf(elementData, size);
    }
}

缩容示例

ArrayList<Integer> list = new ArrayList<>(100);
list.add(1);
list.add(2);
list.add(3);

System.out.println("Before trim: " + list.size()); // 3
System.out.println("Capacity: " + getCapacity(list)); // 100

list.trimToSize();

System.out.println("After trim: " + list.size()); // 3
System.out.println("Capacity: " + getCapacity(list)); // 3

获取容量的反射方法

public static int getCapacity(ArrayList<?> list) {
    try {
        Field field = ArrayList.class.getDeclaredField("elementData");
        field.setAccessible(true);
        Object[] elementData = (Object[]) field.get(list);
        return elementData.length;
    } catch (Exception e) {
        throw new RuntimeException(e);
    }
}

注意事项

• 频繁的扩容和缩容会影响性能
• 如果已知大致容量，建议在构造时指定初始容量
• trimToSize() 适用于内存敏感场景，但可能触发后续扩容

🔑 模式提炼：容量预分配

当已知集合大致容量时，使用带容量的构造器可以避免多次扩容。适用于批量数据导入、已知大小的数据处理等场景。

3.2 队列的六个操作

Java 队列接口定义了六个核心操作，分为三类：插入、检查、移除。

操作分类

操作类型	抛出异常	返回特殊值
插入	add(E)	offer(E)
检查	element()	peek()
移除	remove()	poll()

阻塞与非阻塞

阻塞队列（BlockingQueue）额外提供了两个阻塞操作：

操作类型	阻塞方法
插入	put(E)
移除	take()

操作详解

插入操作

Queue<String> queue = new LinkedList<>();

// add(E): 队列满时抛出 IllegalStateException
try {
    queue.add("A");
    queue.add("B");
    queue.add("C");
    System.out.println("Queue: " + queue); // [A, B, C]
} catch (IllegalStateException e) {
    System.out.println("Queue is full");
}

// offer(E): 队列满时返回 false
boolean success = queue.offer("D");
System.out.println("Offer result: " + success); // true

检查操作

// element(): 队列空时抛出 NoSuchElementException
try {
    String head = queue.element();
    System.out.println("Head: " + head); // A
} catch (NoSuchElementException e) {
    System.out.println("Queue is empty");
}

// peek(): 队列空时返回 null
String head = queue.peek();
System.out.println("Peek: " + head); // A

移除操作

// remove(): 队列空时抛出 NoSuchElementException
try {
    String removed = queue.remove();
    System.out.println("Removed: " + removed); // A
    System.out.println("Queue: " + queue); // [B, C, D]
} catch (NoSuchElementException e) {
    System.out.println("Queue is empty");
}

// poll(): 队列空时返回 null
String removed = queue.poll();
System.out.println("Polled: " + removed); // B
System.out.println("Queue: " + queue); // [C, D]

阻塞操作

BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(3);

// put(E): 队列满时阻塞
new Thread(() -> {
    try {
        blockingQueue.put("A");
        System.out.println("Put A");
        blockingQueue.put("B");
        System.out.println("Put B");
        blockingQueue.put("C");
        System.out.println("Put C");
        blockingQueue.put("D"); // 阻塞，直到有空间
        System.out.println("Put D");
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

// take(): 队列空时阻塞
new Thread(() -> {
    try {
        Thread.sleep(1000);
        String taken = blockingQueue.take();
        System.out.println("Taken: " + taken); // A
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

操作选择建议

场景	推荐方法
正常流程，容量充足	add() / element() / remove()
容量受限，需要容错	offer() / peek() / poll()
生产者-消费者模式	put() / take()
定时等待	offer(E, long, TimeUnit) / poll(long, TimeUnit)

🔑 模式提炼：队列操作六法

根据业务场景选择合适的队列操作：正常流程用异常版本，容量受限用特殊值版本，并发场景用阻塞版本。这确保了代码的健壮性和可预测性。

3.3 PriorityQueue

PriorityQueue 是基于二叉堆（Binary Heap）实现的优先级队列，元素按照自然顺序或指定的 Comparator 排序。

基本特性

• 数据结构：最小堆（min-heap），堆顶是最小元素
• 排序方式：自然顺序或自定义 Comparator
• 时间复杂度：插入 O(log n)，删除 O(log n)，查找 O(1)
• 线程安全：非线程安全，并发场景使用 PriorityBlockingQueue

基本使用

// 自然顺序（升序）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(2);
minHeap.add(8);
minHeap.add(1);

System.out.println("Min heap: " + minHeap); // [1, 2, 8, 5]
System.out.println("Peek: " + minHeap.peek()); // 1
System.out.println("Poll: " + minHeap.poll()); // 1
System.out.println("After poll: " + minHeap); // [2, 5, 8]

// 自定义 Comparator（降序）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(5);
maxHeap.add(2);
maxHeap.add(8);
maxHeap.add(1);

System.out.println("Max heap: " + maxHeap); // [8, 5, 2, 1]
System.out.println("Peek: " + maxHeap.peek()); // 8

// 自定义对象排序
class Task implements Comparable<Task> {
    String name;
    int priority;
    
    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
    
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
    
    @Override
    public String toString() {
        return name + "(" + priority + ")";
    }
}

PriorityQueue<Task> taskQueue = new PriorityQueue<>();
taskQueue.add(new Task("Task A", 3));
taskQueue.add(new Task("Task B", 1));
taskQueue.add(new Task("Task C", 2));

System.out.println("Task queue: " + taskQueue); // [Task B(1), Task A(3), Task C(2)]
System.out.println("Next task: " + taskQueue.poll()); // Task B(1)

Top-K 问题

场景：找出前 K 个最大的元素

public static List<Integer> topKLargest(int[] nums, int k) {
    // 使用最小堆，保持堆大小为 k
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // 移除最小的元素
        }
    }
    
    // 堆中剩余的就是前 k 个最大的元素
    List<Integer> result = new ArrayList<>(minHeap);
    Collections.sort(result, Collections.reverseOrder());
    return result;
}

// 测试
int[] nums = {3, 2, 1, 5, 6, 4};
int k = 2;
System.out.println("Top " + k + " largest: " + topKLargest(nums, k)); // [6, 5]

场景：合并 K 个有序链表

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public ListNode mergeKLists(ListNode[] lists) {
    // 优先队列：按节点值排序
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        (a, b) -> Integer.compare(a.val, b.val)
    );
    
    // 将所有链表的头节点加入堆
    for (ListNode head : lists) {
        if (head != null) {
            minHeap.offer(head);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (!minHeap.isEmpty()) {
        // 取出最小的节点
        ListNode node = minHeap.poll();
        current.next = node;
        current = current.next;
        
        // 将该节点的下一个节点加入堆
        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }
    
    return dummy.next;
}

任务调度

场景：按优先级执行任务

class ScheduledTask implements Comparable<ScheduledTask> {
    String name;
    int priority;
    Runnable task;
    
    ScheduledTask(String name, int priority, Runnable task) {
        this.name = name;
        this.priority = priority;
        this.task = task;
    }
    
    @Override
    public int compareTo(ScheduledTask other) {
        // 优先级越高（数值越小）越先执行
        return Integer.compare(this.priority, other.priority);
    }
    
    public void execute() {
        System.out.println("Executing: " + name + " (priority: " + priority + ")");
        task.run();
    }
}

public class TaskScheduler {
    private final PriorityQueue<ScheduledTask> taskQueue;
    
    public TaskScheduler() {
        this.taskQueue = new PriorityQueue<>();
    }
    
    public void schedule(String name, int priority, Runnable task) {
        taskQueue.offer(new ScheduledTask(name, priority, task));
    }
    
    public void run() {
        while (!taskQueue.isEmpty()) {
            ScheduledTask task = taskQueue.poll();
            task.execute();
        }
    }
}

// 使用示例
TaskScheduler scheduler = new TaskScheduler();
scheduler.schedule("Task A", 3, () -> System.out.println("Task A running"));
scheduler.schedule("Task B", 1, () -> System.out.println("Task B running"));
scheduler.schedule("Task C", 2, () -> System.out.println("Task C running"));

scheduler.run();
// 输出：
// Executing: Task B (priority: 1)
// Task B running
// Executing: Task C (priority: 2)
// Task C running
// Executing: Task A (priority: 3)
// Task A running

🔑 模式提炼：优先级堆

当需要按优先级处理数据时，PriorityQueue 提供了高效的实现。适用于 Top-K 问题、任务调度、事件驱动系统等场景。

3.4 DelayQueue

DelayQueue 是一个无界阻塞队列，只有当元素的延迟时间到期时才能从队列中取出。元素必须实现 Delayed 接口。

Delayed 接口

public interface Delayed extends Comparable<Delayed> {
    /**
     * 返回剩余延迟时间（负值表示已到期）
     * @param unit 时间单位
     * @return 剩余延迟时间
     */
    long getDelay(TimeUnit unit);
}

基本使用

class DelayedElement implements Delayed {
    private final String name;
    private final long delayTime;
    private final long expireTime;
    
    public DelayedElement(String name, long delay, TimeUnit unit) {
        this.name = name;
        this.delayTime = unit.toMillis(delay);
        this.expireTime = System.currentTimeMillis() + this.delayTime;
    }
    
    @Override
    public long getDelay(TimeUnit unit) {
        long remaining = expireTime - System.currentTimeMillis();
        return unit.convert(remaining, TimeUnit.MILLISECONDS);
    }
    
    @Override
    public int compareTo(Delayed other) {
        if (this == other) {
            return 0;
        }
        
        DelayedElement otherElement = (DelayedElement) other;
        long diff = this.expireTime - otherElement.expireTime;
        return (diff < 0) ? -1 : (diff > 0) ? 1 : 0;
    }
    
    @Override
    public String toString() {
        return name + " (expires in " + getDelay(TimeUnit.MILLISECONDS) + "ms)";
    }
}

public class DelayQueueExample {
    public static void main(String[] args) throws InterruptedException {
        DelayQueue<DelayedElement> delayQueue = new DelayQueue<>();
        
        // 添加延迟元素
        delayQueue.put(new DelayedElement("Element A", 3, TimeUnit.SECONDS));
        delayQueue.put(new DelayedElement("Element B", 1, TimeUnit.SECONDS));
        delayQueue.put(new DelayedElement("Element C", 2, TimeUnit.SECONDS));
        
        System.out.println("Elements added to delay queue");
        
        // 取出元素（会阻塞直到延迟到期）
        while (!delayQueue.isEmpty()) {
            DelayedElement element = delayQueue.take();
            System.out.println("Taken: " + element);
        }
    }
}

// 输出：
// Elements added to delay queue
// Taken: Element B (expires in -1000ms)
// Taken: Element C (expires in -2000ms)
// Taken: Element A (expires in -3000ms)

缓存过期实现

class CacheItem<K, V> implements Delayed {
    private final K key;
    private final V value;
    private final long expireTime;
    
    public CacheItem(K key, V value, long ttl, TimeUnit unit) {
        this.key = key;
        this.value = value;
        this.expireTime = System.currentTimeMillis() + unit.toMillis(ttl);
    }
    
    @Override
    public long getDelay(TimeUnit unit) {
        long remaining = expireTime - System.currentTimeMillis();
        return unit.convert(remaining, TimeUnit.MILLISECONDS);
    }
    
    @Override
    public int compareTo(Delayed other) {
        if (this == other) {
            return 0;
        }
        
        CacheItem<?, ?> otherItem = (CacheItem<?, ?>) other;
        long diff = this.expireTime - otherItem.expireTime;
        return (diff < 0) ? -1 : (diff > 0) ? 1 : 0;
    }
    
    public K getKey() {
        return key;
    }
    
    public V getValue() {
        return value;
    }
}

public class ExpiringCache<K, V> {
    private final ConcurrentHashMap<K, V> cache;
    private final DelayQueue<CacheItem<K, V>> expirationQueue;
    private final ScheduledExecutorService cleanupExecutor;
    
    public ExpiringCache() {
        this.cache = new ConcurrentHashMap<>();
        this.expirationQueue = new DelayQueue<>();
        this.cleanupExecutor = Executors.newSingleThreadScheduledExecutor();
        
        // 启动清理线程
        cleanupExecutor.scheduleAtFixedRate(this::cleanup, 1, 1, TimeUnit.SECONDS);
    }
    
    public void put(K key, V value, long ttl, TimeUnit unit) {
        CacheItem<K, V> item = new CacheItem<>(key, value, ttl, unit);
        cache.put(key, value);
        expirationQueue.put(item);
    }
    
    public V get(K key) {
        return cache.get(key);
    }
    
    private void cleanup() {
        CacheItem<K, V> item;
        while ((item = expirationQueue.poll()) != null) {
            cache.remove(item.getKey());
            System.out.println("Expired: " + item.getKey());
        }
    }
    
    public void shutdown() {
        cleanupExecutor.shutdown();
    }
}

// 使用示例
ExpiringCache<String, String> cache = new ExpiringCache<>();
cache.put("key1", "value1", 2, TimeUnit.SECONDS);
cache.put("key2", "value2", 3, TimeUnit.SECONDS);

System.out.println("key1: " + cache.get("key1")); // value1
Thread.sleep(2500);
System.out.println("key1: " + cache.get("key1")); // null

cache.shutdown();

订单超时取消

class Order implements Delayed {
    private final String orderId;
    private final long expireTime;
    
    public Order(String orderId, long timeout, TimeUnit unit) {
        this.orderId = orderId;
        this.expireTime = System.currentTimeMillis() + unit.toMillis(timeout);
    }
    
    @Override
    public long getDelay(TimeUnit unit) {
        long remaining = expireTime - System.currentTimeMillis();
        return unit.convert(remaining, TimeUnit.MILLISECONDS);
    }
    
    @Override
    public int compareTo(Delayed other) {
        if (this == other) {
            return 0;
        }
        
        Order otherOrder = (Order) other;
        long diff = this.expireTime - otherOrder.expireTime;
        return (diff < 0) ? -1 : (diff > 0) ? 1 : 0;
    }
    
    public String getOrderId() {
        return orderId;
    }
}

public class OrderTimeoutService {
    private final DelayQueue<Order> timeoutQueue;
    private final ScheduledExecutorService timeoutExecutor;
    
    public OrderTimeoutService() {
        this.timeoutQueue = new DelayQueue<>();
        this.timeoutExecutor = Executors.newSingleThreadScheduledExecutor();
        
        // 启动超时检查线程
        timeoutExecutor.execute(this::checkTimeout);
    }
    
    public void placeOrder(String orderId, long timeout, TimeUnit unit) {
        System.out.println("Order placed: " + orderId);
        timeoutQueue.put(new Order(orderId, timeout, unit));
    }
    
    public void payOrder(String orderId) {
        // 支付成功后，从超时队列中移除
        // 实际实现需要维护订单状态
        System.out.println("Order paid: " + orderId);
    }
    
    private void checkTimeout() {
        while (!Thread.currentThread().isInterrupted()) {
            try {
                Order order = timeoutQueue.take();
                System.out.println("Order timeout: " + order.getOrderId());
                // 执行取消订单逻辑
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                break;
            }
        }
    }
    
    public void shutdown() {
        timeoutExecutor.shutdown();
    }
}

// 使用示例
OrderTimeoutService service = new OrderTimeoutService();
service.placeOrder("ORD001", 5, TimeUnit.SECONDS);
service.placeOrder("ORD002", 3, TimeUnit.SECONDS);

Thread.sleep(6000);
service.shutdown();

🔑 模式提炼：延迟队列

当需要基于时间延迟处理任务时，DelayQueue 提供了优雅的解决方案。适用于缓存过期、订单超时、定时任务调度等场景。

第四章：哈希表家族

4.1 HashMap 内部结构

HashMap 是 Java 中最常用的键值对集合，其内部结构在 Java 8 中引入了红黑树优化。

Java 8+ 内部结构

HashMap 内部结构（桶数组 + 链表 + 红黑树）

┌─────────────────────────────────────────────────────────────┐
│                    HashMap 桶数组                             │
│  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐       │
│  │ Bucket 0│  │ Bucket 1│  │ Bucket 2│  │ Bucket 3│  ...  │
│  └────┬────┘  └────┬────┘  └────┬────┘  └────┬────┘       │
│       │            │            │            │              │
│       ▼            ▼            ▼            ▼              │
│  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐       │
│  │  null   │  │  Node   │  │  Node   │  │ TreeNode │       │
│  └─────────┘  └────┬────┘  └────┬────┘  └────┬────┘       │
│                     │            │            │              │
│                     ▼            ▼            ▼              │
│                ┌─────────┐  ┌─────────┐  ┌─────────┐       │
│                │  Node   │  │  Node   │  │ TreeNode │       │
│                └────┬────┘  └────┬────┘  └────┬────┘       │
│                     │            │            │              │
│                     ▼            ▼            ▼              │
│                ┌─────────┐  ┌─────────┐  ┌─────────┐       │
│                │  Node   │  │  null   │  │ TreeNode │       │
│                └────┬────┘  └─────────┘  └────┬────┘       │
│                     │                         │              │
│                     ▼                         ▼              │
│                ┌─────────┐              ┌─────────┐         │
│                │  null   │              │ TreeNode │         │
│                └─────────┘              └────┬────┘         │
│                                                 │            │
│                                                 ▼            │
│                                            ┌─────────┐      │
│                                            │TreeNode  │      │
│                                            └────┬────┘      │
│                                                 │            │
│                                                 ▼            │
│                                            ┌─────────┐      │
│                                            │  null   │      │
│                                            └─────────┘      │
└─────────────────────────────────────────────────────────────┘

Node 结构（链表节点）
┌─────────────────────────────────────────┐
│  int    hash     // 哈希值               │
│  K       key      // 键                  │
│  V       value    // 值                  │
│  Node<K,V> next   // 下一个节点          │
└─────────────────────────────────────────┘

TreeNode 结构（红黑树节点）
┌─────────────────────────────────────────┐
│  int    hash     // 哈希值               │
│  K       key      // 键                  │
│  V       value    // 值                  │
│  TreeNode<K,V> parent // 父节点          │
│  TreeNode<K,V> left   // 左子节点        │
│  TreeNode<K,V> right  // 右子节点        │
│  TreeNode<K,V> prev   // 前驱节点（用于删除）│
│  boolean red          // 红黑颜色         │
└─────────────────────────────────────────┘

核心字段

public class HashMap<K, V> extends AbstractMap<K, V> {
    // 桶数组，初始化为空数组，第一次 put 时扩容
    transient Node<K, V>[] table;
    
    // 实际键值对数量
    transient int size;
    
    // 扩容阈值 = capacity * loadFactor
    int threshold;
    
    // 负载因子，默认 0.75
    final float loadFactor;
    
    // 默认初始容量 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    // 最大容量 2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 树化阈值：链表长度 >= 8 时转换为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    
    // 反树化阈值：红黑树节点数 <= 6 时转换为链表
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // 最小树化容量：64（避免扩容时频繁树化）
    static final int MIN_TREEIFY_CAPACITY = 64;
}

4.2 HashMap 关键参数表

参数	默认值	说明
初始容量	16	桶数组的初始大小，必须是 2 的幂
负载因子	0.75	扩容阈值 = 容量 × 负载因子
树化阈值	8	链表长度 ≥ 8 时转换为红黑树
反树化阈值	6	红黑树节点数 ≤ 6 时转换为链表
最小树化容量	64	容量 ≥ 64 时才允许树化

参数选择原理

1. 负载因子 0.75

   • 0.75 是时间和空间的平衡点
   • 负载因子过高：哈希冲突增加，查询性能下降
   • 负载因子过低：空间浪费严重

2. 树化阈值 8

   • 基于泊松分布计算，链表长度 ≥ 8 的概率极低
   • 树化是为了优化极端情况下的性能

3. 反树化阈值 6

   • 避免 7-8 之间的频繁转换
   • 提供一定的缓冲空间

4.3 HashMap 扩容流程

扩容触发条件

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, i;
    
    // 初始化桶数组
    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 {
        // 处理哈希冲突
        // ...
    }
    
    // 检查是否需要扩容
    if (++size > threshold) {
        resize();
    }
    
    return null;
}

resize 方法

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;
        }
        // 新容量 = 旧容量 × 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) {
            newThr = oldThr << 1; // 新阈值 = 旧阈值 × 2
        }
    } else if (oldThr > 0) {
        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 < MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 创建新数组
    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;
                        // 原索引不变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null) {
                                loHead = e;
                            } else {
                                loTail.next = e;
                            }
                            loTail = e;
                        }
                        // 原索引 + oldCap
                        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;
}

重新分配优化

扩容时，节点的索引计算不需要重新哈希，而是通过位运算快速确定：

// 原索引
int oldIndex = hash & (oldCap - 1);

// 新索引：要么不变，要么 = oldIndex + oldCap
int newIndex = (hash & oldCap) == 0 ? oldIndex : oldIndex + oldCap;

原理

• oldCap 是 2 的幂，其二进制表示只有一个 1
• hash & oldCap 检查 hash 的对应位是 0 还是 1
• 如果是 0，新索引不变
• 如果是 1，新索引 = 原索引 + oldCap

示例

假设 oldCap = 16 (0b10000)

hash = 0b00101 (5)
hash & oldCap = 0b00101 & 0b10000 = 0b00000 (0)
新索引 = 5 & 15 = 5 (不变)

hash = 0b10101 (21)
hash & oldCap = 0b10101 & 0b10000 = 0b10000 (16)
新索引 = 21 & 31 = 21 = 5 + 16 (原索引 + oldCap)

为什么容量必须是 2 的幂

1. 快速取余

   // 普通取余
   index = hash % capacity;
   
   // 位运算取余（要求 capacity 是 2 的幂）
   index = hash & (capacity - 1);

2. 扩容优化

   • 容量是 2 的幂，扩容时只需要左移一位
   • 节点重新分配时，只需要检查 hash 的一个位

3. 哈希分布均匀

   • 2 的幂确保哈希值能够均匀分布到各个桶
   • 避免某些桶过度拥挤

4.4 扰动函数

扰动函数用于优化哈希值的分布，减少哈希冲突。

static final int hash(Object key) {
    int h;
    // 高 16 位与低 16 位异或
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

原理

• 假设容量为 16，索引计算只使用 hash 的低 4 位
• 如果只使用低位，高位的差异会被忽略
• 异或操作将高位信息混合到低位，增加随机性

示例

假设 capacity = 16 (0b10000)

hash = 0b1111111100000000 (65280)
hashCode = 65280

扰动前：
index = 65280 & 15 = 0b1111111100000000 & 0b1111 = 0b0000 = 0

扰动后：
h >>> 16 = 0b1111111100000000 >>> 16 = 0b11111111 (255)
hash = 65280 ^ 255 = 0b1111111100000000 ^ 0b0000000011111111 = 0b1111111111111111 (65535)
index = 65535 & 15 = 0b1111111111111111 & 0b1111 = 0b1111 = 15

效果

• 扰动前，所有 hash 只有低 4 位不同，容易冲突
• 扰动后，高位信息被利用，哈希分布更均匀

4.5 树化与反树化

树化条件

final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index;
    Node<K, V> e;
    
    // 检查容量是否达到最小树化容量
    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);
        }
    }
}

泊松分布解释阈值 8

根据泊松分布，在负载因子 0.75 下，链表长度达到 8 的概率非常低：

P(k) = (λ^k * e^(-λ)) / k!

其中 λ = 0.75

k=0: 47.2%
k=1: 35.4%
k=2: 13.3%
k=3: 3.3%
k=4: 0.62%
k=5: 0.094%
k=6: 0.012%
k=7: 0.0013%
k=8: 0.00016% (极低)

因此，链表长度达到 8 是极端情况，此时树化可以显著提升查询性能。

反树化阈值 6

final Node<K, V> untreeify(HashMap<K, V> map) {
    Node<K, V> hd = null, tl = null;
    for (Node<K, V> q = this; q != null; q = q.next) {
        // 将红黑树节点转换为链表节点
        Node<K, V> p = map.replacementNode(q, null);
        if (tl == null) {
            hd = p;
        } else {
            tl.next = p;
        }
        tl = p;
    }
    return hd;
}

为什么反树化阈值是 6？

• 树化阈值是 8，反树化阈值是 6
• 避免 7-8 之间的频繁转换（8 树化，7 反树化，8 树化…）
• 提供一定的缓冲空间，减少转换开销

4.6 ConcurrentHashMap 扩容

分段迁移

ConcurrentHashMap 的扩容采用多线程分段迁移策略，提高扩容效率。

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 {
            // 创建新数组，容量为 2 倍
            nextTab = (Node<K, V>[])new Node<?, ?>[n << 1];
        } 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, sizeCtl = -1, sc = sizeCtl)) {
                if (sc == -1) {
                    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);
                    } 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;
                            K pk = e.key;
                            V pv = e.val;
                            if ((h & n) == 0) {
                                if ((e.prev = loTail) == null) {
                                    lo = e;
                                } else {
                                    loTail.next = e;
                                }
                                loTail = e;
                                ++lc;
                            } else {
                                if ((e.prev = hiTail) == null) {
                                    hi = e;
                                } else {
                                    hiTail.next = e;
                                }
                                hiTail = e;
                                ++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);
                    }
                }
            }
        }
    }
}

sizeCtl 字段含义

// sizeCtl 的不同值表示不同状态

// 负数：表示正在初始化或扩容
// -1：正在初始化
// -N：表示有 N-1 个线程正在扩容

// 正数：
// 0：默认值，表示未初始化
// >0：表示扩容阈值（类似 HashMap 的 threshold）

扩容流程

1. 检测到 size > threshold
2. 设置 sizeCtl 为负数，标记扩容状态
3. 多线程分段迁移桶数组
4. 迁移完成后，更新 sizeCtl 为新的阈值

JDK 7 与 JDK 8 的实现对比

ConcurrentHashMap 在 JDK 7 和 JDK 8 中经历了重大架构调整，从分段锁演进为更细粒度的锁机制。

JDK 7 分段锁架构

JDK 7 采用分段锁（Segment）设计，将数据分成多个段（默认 16 个），每个段是一个独立的 HashMap，使用 ReentrantLock 保护。

// JDK 7 ConcurrentHashMap 结构（简化）
static final class Segment<K, V> extends ReentrantLock {
    transient volatile HashEntry<K, V>[] table;
    transient int count;
    transient int modCount;
    transient int threshold;
    final float loadFactor;
}

static final class HashEntry<K, V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K, V> next;
}

JDK 8 CAS + synchronized 架构

JDK 8 摒弃了 Segment，采用数组 + 链表 + 红黑树结构，使用 CAS + synchronized 实现更细粒度的锁控制。

// JDK 8 ConcurrentHashMap 结构（简化）
static final class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K, V> next;
}

static final class TreeNode<K, V> extends Node<K, V> {
    TreeNode<K, V> parent;
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;
    boolean red;
}

实现对比

特性	JDK 7	JDK 8
锁机制	ReentrantLock（分段锁）	CAS + synchronized
锁粒度	Segment 级别（默认 16 个）	桶级别（Node 级别）
数据结构	Segment 数组 + HashEntry 链表	Node 数组 + 链表 + 红黑树
并发度	固定为 Segment 数量	理论上为桶数量
扩容方式	Segment 独立扩容	多线程协作扩容
内存占用	较高（Segment 数组开销）	较低（无额外数组）
查询性能	需要两次哈希定位	一次哈希定位

锁粒度对比

// JDK 7：锁整个 Segment
Segment<K, V> s = segmentFor(hash);
s.lock(); // 锁住整个 Segment
try {
    HashEntry<K, V>[] tab = s.table;
    // 操作整个 Segment 的数据
} finally {
    s.unlock();
}

// JDK 8：只锁单个桶
Node<K, V>[] tab = table;
int n = tab.length;
Node<K, V> f = tabAt(tab, (n - 1) & hash);
if (f == null) {
    // CAS 设置新节点
    if (casTabAt(tab, i, null, new Node<K, V>(hash, key, val, null))) {
        break;
    }
} else {
    synchronized (f) { // 只锁当前桶的头节点
        // 操作当前桶的链表或红黑树
    }
}

并发度提升

JDK 7 的并发度受限于 Segment 数量（默认 16），即使有更多线程也无法充分利用。JDK 8 将锁粒度细化到桶级别，理论上并发度等于桶数量，大幅提升了高并发场景下的性能。

🔑 模式提炼： JDK 8 的改进体现了"锁粒度细化"的设计思想，将粗粒度锁拆分为多个细粒度锁，减少线程竞争，提高并发性能。

4.7 LinkedHashMap

LinkedHashMap 在 HashMap 的基础上增加了顺序保持功能，可以按照插入顺序或访问顺序遍历元素。

保持插入顺序

// LinkedHashMap 默认按插入顺序遍历
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

// 遍历顺序：A -> B -> C
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// LinkedHashSet 同理
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
System.out.println(set); // [A, B, C]

保持访问顺序（LRU 缓存）

// accessOrder=true：按访问顺序遍历
LinkedHashMap<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3; // 缓存大小限制为 3
    }
};

lruCache.put("A", 1);
lruCache.put("B", 2);
lruCache.put("C", 3);

// 访问 "A"，将其移到末尾
lruCache.get("A");

// 添加 "D"，触发 eldest 移除（"B" 是最久未访问的）
lruCache.put("D", 4);

// 当前顺序：C -> A -> D
System.out.println(lruCache.keySet()); // [C, A, D]

LRU 缓存实现

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// 使用示例
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("key1", "value1");
cache.put("key2", "value2");
cache.put("key3", "value3");

cache.get("key1"); // 访问 key1
cache.put("key4", "value4"); // 添加 key4，移除 key2（最久未访问）

System.out.println(cache.keySet()); // [key3, key1, key4]

性能对比

特性	HashMap	LinkedHashMap
插入/删除	O(1)	O(1)
查找	O(1)	O(1)
遍历顺序	无序	插入顺序/访问顺序
内存开销	较小	较大（维护双向链表）

🔑 模式提炼：有序集合与 LRU 缓存

当需要保持元素顺序或实现 LRU 缓存时，LinkedHashMap/LinkedHashSet 提供了比手动维护顺序更优雅的解决方案。适用于历史记录、最近访问列表、缓存淘汰等场景。

4.8 EnumSet

EnumSet 是专为枚举类型设计的高性能 Set，使用位向量（Bit Vector）存储，空间和时间效率极高。

EnumSet 的限制

• 只能包含枚举值，且所有值必须属于同一个枚举
• 不允许添加 null 值，尝试添加会抛出 NullPointerException
• 不是线程安全的，如果需要则需外部同步
• 元素按照枚举中声明的顺序存储
• 使用 fail-safe 迭代器，在迭代时修改集合不会抛出 ConcurrentModificationException

创建与使用

enum Day {
    MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY
}

// 创建 EnumSet
EnumSet<Day> weekdays = EnumSet.of(Day.MONDAY, Day.TUESDAY, Day.WEDNESDAY, 
                                   Day.THURSDAY, Day.FRIDAY);
EnumSet<Day> weekend = EnumSet.of(Day.SATURDAY, Day.SUNDAY);

// 范围创建
EnumSet<Day> allDays = EnumSet.allOf(Day.class);
EnumSet<Day> noDays = EnumSet.noneOf(Day.class);

// 补集操作
EnumSet<Day> complement = EnumSet.complementOf(weekdays); // weekend

// 集合操作
EnumSet<Day> workDays = EnumSet.range(Day.MONDAY, Day.FRIDAY);
System.out.println(workDays.add(Day.SATURDAY)); // false (已满)
System.out.println(workDays.remove(Day.SUNDAY)); // true

JDK 实现细节

JDK 提供两个默认参考实现：

• RegularEnumSet：当枚举值数量 ≤ 64 时，使用单个 long 值作为位向量
• JumboEnumSet：当枚举值数量 > 64 时，使用 long 数组作为位向量

EnumSet<InsPayOrderStatusEnum> BAD_FINAL_STATUSES = EnumSet.of(FAILED, CLOSED, BOUNCED);

性能优势

// EnumSet vs HashSet
enum Color { RED, GREEN, BLUE, YELLOW }

// EnumSet: 使用单个 long 值存储（64位可存储64个枚举）
EnumSet<Color> enumSet = EnumSet.of(Color.RED, Color.GREEN);
// 内部结构：long = 0b0011 (位向量)

// HashSet: 使用数组+链表存储
HashSet<Color> hashSet = new HashSet<>();
hashSet.add(Color.RED);
hashSet.add(Color.GREEN);
// 内部结构：Node[] 数组 + 链表节点

// 性能测试
EnumSet<Color> es = EnumSet.allOf(Color.class);
HashSet<Color> hs = new HashSet<>(Arrays.asList(Color.values()));

// EnumSet 的 contains 操作：位运算 O(1)
// HashSet 的 contains 操作：哈希计算 + 链表遍历 O(1) 平均

🔑 模式提炼：枚举专用集合

当集合元素类型是枚举时，EnumSet/EnumMap 提供了比通用集合更好的性能和更紧凑的内存占用。适用于标志位集合、状态机、配置管理等场景。

4.9 EnumMap

EnumMap 是专为枚举类型设计的高性能 Map，使用数组存储，键必须是枚举类型。

创建与使用

enum Operation {
    ADD, SUBTRACT, MULTIPLY, DIVIDE
}

EnumMap<Operation, String> descriptions = new EnumMap<>(Operation.class);
descriptions.put(Operation.ADD, "加法");
descriptions.put(Operation.SUBTRACT, "减法");
descriptions.put(Operation.MULTIPLY, "乘法");
descriptions.put(Operation.DIVIDE, "除法");

// 遍历（保证按枚举声明顺序）
for (Map.Entry<Operation, String> entry : descriptions.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

高级用法

// 复制构造器
Map<DayOfWeek, String> ordinaryMap = new HashMap<>();
ordinaryMap.put(DayOfWeek.MONDAY, "Soccer");
EnumMap<DayOfWeek, String> enumMap = new EnumMap<>(ordinaryMap);

// 双参数的 remove
activityMap.put(DayOfWeek.MONDAY, "Soccer");
assertThat(activityMap.remove(DayOfWeek.MONDAY, "Hiking")).isEqualTo(false);
assertThat(activityMap.remove(DayOfWeek.MONDAY, "Soccer")).isEqualTo(true);

性能优势

使用 Enum 作为 key 使得可以做一些额外的性能优化，比如更快的哈希计算，因为所有可能的键都是预先知道的。

因为枚举的顺序已经被事先知道了，所以可以进行某些极致的优化。

EnumMap 是一个有序 map，它的视图会按照枚举顺序迭代。虽然 LinkedHashMap 和 TreeMap 也可以提供类似的行为，但 EnumMap 的性能更优。

4.10 IdentityHashMap

IdentityHashMap 的用法和 HashMap 的用法差不多，它们之间最大的区别就是 IdentityHashMap 判断两个 key 是否相等，是通过严格相等即（key1 == key2）来判断的，而 HashMap 是通过 equals() 方法和 hashCode() 这两个方法来判断 key 是否相等的。

用途

• 需要比对独一无二的对象，如全局的 class，可以用 IdentityHashMap 来控制唯一性
• 深拷贝的时候需要容忍相同的值不同引用的对象

使用示例

// 普通 HashMap：基于 equals() 和 hashCode()
HashMap<String, String> hashMap = new HashMap<>();
String key1 = new String("test");
String key2 = new String("test");
hashMap.put(key1, "value1");
hashMap.put(key2, "value2");
System.out.println(hashMap.size()); // 1（key1.equals(key2) 返回 true）

// IdentityHashMap：基于引用相等
IdentityHashMap<String, String> identityMap = new IdentityHashMap<>();
identityMap.put(key1, "value1");
identityMap.put(key2, "value2");
System.out.println(identityMap.size()); // 2（key1 != key2）

实际应用场景

深拷贝场景

// 深拷贝时需要区分相同值的不同引用
IdentityHashMap<Object, Object> visited = new IdentityHashMap<>();

public Object deepCopy(Object obj) {
    if (obj == null) return null;
    
    // 检查是否已经复制过（基于引用）
    if (visited.containsKey(obj)) {
        return visited.get(obj);
    }
    
    Object copy = createCopy(obj);
    visited.put(obj, copy); // 记录已复制的对象
    
    // 递归复制引用
    for (Object ref : getReferences(obj)) {
        copyReference(copy, deepCopy(ref));
    }
    
    return copy;
}

序列化场景

// 序列化时需要维护对象引用关系
IdentityHashMap<Object, Integer> objectMap = new IdentityHashMap<>();

public void serialize(Object obj, ObjectOutputStream out) throws IOException {
    // 为每个对象分配唯一 ID（基于引用）
    int id = objectMap.size();
    objectMap.put(obj, id);
    
    out.writeObject(id);
    // 序列化对象内容...
}

public Object deserialize(ObjectInputStream in) throws IOException, ClassNotFoundException {
    int id = in.readInt();
    // 根据 ID 反序列化对象...
}

🔑 模式提炼：引用语义映射

当需要基于对象引用而非对象相等性进行映射时，IdentityHashMap 提供了精确的引用语义。适用于深拷贝、序列化、对象跟踪等场景。

4.11 WeakHashMap

WeakHashMap 是一个使用弱引用作为键的 HashMap。当键不再被外部引用时，它可以被垃圾回收器回收，对应的键值对也会自动从 Map 中移除。

弱引用机制

// 普通 HashMap：键被强引用
HashMap<String, String> strongMap = new HashMap<>();
String key = new String("test");
strongMap.put(key, "value");
key = null; // key 仍被 Map 引用，不会被 GC

// WeakHashMap：键被弱引用
WeakHashMap<String, String> weakMap = new WeakHashMap<>();
key = new String("test");
weakMap.put(key, "value");
key = null; // key 不再被强引用，GC 时会被回收

System.gc(); // 触发 GC
System.out.println(weakMap.size()); // 可能输出 0

实际应用场景

缓存实现

public class WeakCache<K, V> {
    private WeakHashMap<K, V> cache = new WeakHashMap<>();
    
    public void put(K key, V value) {
        cache.put(key, value);
    }
    
    public V get(K key) {
        return cache.get(key);
    }
    
    public int size() {
        return cache.size();
    }
}

// 使用场景：缓存大对象，当内存不足时自动释放
WeakCache<String, byte[]> imageCache = new WeakCache<>();
imageCache.put("image1", loadLargeImage("image1.jpg"));
// 当内存紧张时，这些大对象会被自动回收

对象元数据关联

// 为对象附加元数据，不阻止对象被回收
WeakHashMap<Object, Map<String, Object>> metadataMap = new WeakHashMap<>();

public void attachMetadata(Object obj, String key, Object value) {
    metadataMap.computeIfAbsent(obj, k -> new HashMap<>()).put(key, value);
}

public Object getMetadata(Object obj, String key) {
    Map<String, Object> metadata = metadataMap.get(obj);
    return metadata != null ? metadata.get(key) : null;
}

// 当 obj 不再被使用时，其元数据也会自动清理

注意事项

// 错误示例：使用字符串字面量作为键
WeakHashMap<String, String> map = new WeakHashMap<>();
map.put("test", "value"); // "test" 是字符串常量，不会被 GC
System.gc();
System.out.println(map.size()); // 仍然是 1

// 正确示例：使用新创建的对象作为键
map.put(new String("test"), "value");
System.gc();
System.out.println(map.size()); // 可能是 0

🔑 模式提炼：自动清理缓存

当需要缓存数据但不希望缓存阻止对象被垃圾回收时，WeakHashMap 提供了自动清理机制。适用于对象元数据、临时缓存、监听器注册等场景。

第五章：有序集合与并发集合

5.1 TreeSet 与 TreeMap

TreeSet 和 TreeMap 基于红黑树实现，提供自动排序和范围查询能力。红黑树是一种自平衡二叉搜索树，确保所有操作的时间复杂度为 O(log n)。

TreeSet 基本用法：

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // 自然排序（升序）
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(5);
        numbers.add(2);
        numbers.add(8);
        numbers.add(1);
        numbers.add(3);
        
        // 自动排序输出：[1, 2, 3, 5, 8]
        System.out.println(numbers);
        
        // 范围查询：获取大于等于3的元素
        System.out.println(numbers.tailSet(3)); // [3, 5, 8]
        
        // 范围查询：获取小于5的元素
        System.out.println(numbers.headSet(5)); // [1, 2, 3]
        
        // 范围查询：获取2到8之间的元素（包含2，不包含8）
        System.out.println(numbers.subSet(2, 8)); // [2, 3, 5]
        
        // 获取第一个和最后一个元素
        System.out.println("First: " + numbers.first()); // 1
        System.out.println("Last: " + numbers.last()); // 8
    }
}

TreeMap 基本用法：

import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        scores.put("David", 88);
        
        // 按键自动排序输出
        System.out.println(scores);
        // {Alice=95, Bob=87, Charlie=92, David=88}
        
        // 范围查询：获取键在"Bob"到"David"之间的条目
        Map<String, Integer> subMap = scores.subMap("Bob", "David");
        System.out.println(subMap); // {Bob=87, Charlie=92}
        
        // 获取第一个和最后一个键
        System.out.println("First key: " + scores.firstKey()); // Alice
        System.out.println("Last key: " + scores.lastKey()); // David
        
        // 获取大于等于"Charlie"的所有条目
        Map<String, Integer> tailMap = scores.tailMap("Charlie");
        System.out.println(tailMap); // {Charlie=92, David=88}
    }
}

自定义排序：

import java.util.Comparator;
import java.util.TreeSet;

public class CustomSortExample {
    public static void main(String[] args) {
        // 降序排序
        TreeSet<Integer> descendingNumbers = new TreeSet<>(
            Comparator.reverseOrder()
        );
        descendingNumbers.add(5);
        descendingNumbers.add(2);
        descendingNumbers.add(8);
        
        System.out.println(descendingNumbers); // [8, 5, 2]
        
        // 按字符串长度排序
        TreeSet<String> byLength = new TreeSet<>(
            Comparator.comparingInt(String::length)
        );
        byLength.add("apple");
        byLength.add("banana");
        byLength.add("pear");
        byLength.add("kiwi");
        
        System.out.println(byLength); // [pear, kiwi, apple, banana]
    }
}

5.2 TreeSet/TreeMap 应用场景

排行榜实现：

import java.util.TreeSet;

class Player implements Comparable<Player> {
    private String name;
    private int score;
    
    public Player(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    public String getName() {
        return name;
    }
    
    public int getScore() {
        return score;
    }
    
    @Override
    public int compareTo(Player other) {
        // 分数降序排序
        int scoreCompare = Integer.compare(other.score, this.score);
        if (scoreCompare != 0) {
            return scoreCompare;
        }
        // 分数相同则按名字升序
        return this.name.compareTo(other.name);
    }
    
    @Override
    public String toString() {
        return name + ": " + score;
    }
}

public class LeaderboardExample {
    public static void main(String[] args) {
        TreeSet<Player> leaderboard = new TreeSet<>();
        
        leaderboard.add(new Player("Alice", 95));
        leaderboard.add(new Player("Bob", 87));
        leaderboard.add(new Player("Charlie", 95));
        leaderboard.add(new Player("David", 88));
        
        // 输出排行榜（自动排序）
        System.out.println("=== 排行榜 ===");
        int rank = 1;
        for (Player player : leaderboard) {
            System.out.println(rank + ". " + player);
            rank++;
        }
        
        // 获取前3名
        System.out.println("\n=== 前3名 ===");
        TreeSet<Player> top3 = new TreeSet<>(leaderboard);
        while (top3.size() > 3) {
            top3.pollLast();
        }
        rank = 1;
        for (Player player : top3) {
            System.out.println(rank + ". " + player);
            rank++;
        }
        
        // 查询分数在90分以上的玩家
        System.out.println("\n=== 90分以上 ===");
        Player threshold = new Player("", 90);
        for (Player player : leaderboard) {
            if (player.compareTo(threshold) >= 0) {
                System.out.println(player);
            }
        }
    }
}

区间查询应用：

import java.util.TreeMap;
import java.util.Map;

public class PriceRangeQuery {
    public static void main(String[] args) {
        TreeMap<Integer, String> products = new TreeMap<>();
        products.put(100, "Product A");
        products.put(250, "Product B");
        products.put(500, "Product C");
        products.put(800, "Product D");
        products.put(1200, "Product E");
        
        // 查询价格在200到600之间的产品
        System.out.println("=== 价格区间 200-600 ===");
        Map<Integer, String> rangeProducts = products.subMap(200, 600);
        for (Map.Entry<Integer, String> entry : rangeProducts.entrySet()) {
            System.out.println("¥" + entry.getKey() + ": " + entry.getValue());
        }
        
        // 查询价格大于等于500的产品
        System.out.println("\n=== 价格 >= 500 ===");
        Map<Integer, String> expensiveProducts = products.tailMap(500);
        for (Map.Entry<Integer, String> entry : expensiveProducts.entrySet()) {
            System.out.println("¥" + entry.getKey() + ": " + entry.getValue());
        }
        
        // 查询价格小于500的产品
        System.out.println("\n=== 价格 < 500 ===");
        Map<Integer, String> cheapProducts = products.headMap(500);
        for (Map.Entry<Integer, String> entry : cheapProducts.entrySet()) {
            System.out.println("¥" + entry.getKey() + ": " + entry.getValue());
        }
    }
}

🔑 模式提炼： 自动排序数据结构适用于需要维护有序状态、频繁范围查询的场景。红黑树保证 O(log n) 的操作复杂度，但插入和删除性能低于哈希表。

5.3 CopyOnWriteArrayList

CopyOnWriteArrayList 采用写时复制策略，保证读操作的无锁性和强一致性。写操作时会创建底层数组的新副本，修改完成后原子性地替换引用。

基本用法：

import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteExample {
    public static void main(String[] args) {
        List<String> list = new CopyOnWriteArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        
        // 读操作无需加锁
        for (String item : list) {
            System.out.println(item);
        }
        
        // 写操作会复制整个数组
        list.add("D");
        
        // 迭代器遍历
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            System.out.println(item);
            // iterator.remove() 会抛出 UnsupportedOperationException
            // iterator.remove(); // ❌ 不支持
        }
    }
}

读一致性问题：

CopyOnWriteArrayList 的迭代器基于创建时的数组快照，可能出现三种读不一致情况：

import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class ConsistencyExample {
    public static void main(String[] args) {
        List<String> list = new CopyOnWriteArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        
        // 情况1：迭代器创建后，其他线程修改列表，迭代器看不到新数据
        Iterator<String> iterator1 = list.iterator();
        list.add("D"); // 迭代器1看不到"D"
        
        // 情况2：迭代器遍历过程中，其他线程修改列表
        Iterator<String> iterator2 = list.iterator();
        while (iterator2.hasNext()) {
            String item = iterator2.next();
            System.out.println(item);
            if (item.equals("B")) {
                list.add("E"); // 迭代器2看不到"E"
            }
        }
        
        // 情况3：多次获取迭代器，每次都是新的快照
        Iterator<String> iterator3a = list.iterator();
        list.add("F");
        Iterator<String> iterator3b = list.iterator();
        // iterator3a看不到"F"，iterator3b可以看到"F"
    }
}

适用场景：

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class EventListenerExample {
    // 事件监听器列表：读多写少场景
    private final List<EventListener> listeners = new CopyOnWriteArrayList<>();
    
    public void addListener(EventListener listener) {
        listeners.add(listener);
    }
    
    public void removeListener(EventListener listener) {
        listeners.remove(listener);
    }
    
    // 事件通知：频繁读操作
    public void fireEvent(Event event) {
        for (EventListener listener : listeners) {
            listener.onEvent(event);
        }
    }
}

interface EventListener {
    void onEvent(Event event);
}

class Event {
    private String type;
    
    public Event(String type) {
        this.type = type;
    }
    
    public String getType() {
        return type;
    }
}

注意事项：

1. 迭代器的 remove() 方法会抛出 UnsupportedOperationException
2. 写操作会复制整个数组，内存开销较大
3. 适用于读多写少、数据量不大的场景
4. 不能保证实时一致性，只能保证最终一致性

🔑 模式提炼： 写时复制适用于读多写少、数据量小的场景。通过空间换时间，实现读操作的无锁强一致性，但写操作性能较差且内存开销大。

5.4 ConcurrentSkipListSet/Map

ConcurrentSkipListSet 和 ConcurrentSkipListMap 基于跳表结构实现，提供 O(log n) 时间复杂度的有序操作，并保证线程安全。

跳表结构：

跳表是一种多层链表结构，通过索引层加速查找。底层链表包含所有元素，上层链表作为索引，通过"跳跃"快速定位目标元素。

ConcurrentSkipListSet 基本用法：

import java.util.concurrent.ConcurrentSkipListSet;

public class ConcurrentSkipListSetExample {
    public static void main(String[] args) {
        ConcurrentSkipListSet<Integer> set = new ConcurrentSkipListSet<>();
        
        // 并发添加元素
        set.add(5);
        set.add(2);
        set.add(8);
        set.add(1);
        set.add(3);
        
        // 自动排序输出
        System.out.println(set); // [1, 2, 3, 5, 8]
        
        // 范围查询
        System.out.println("tailSet(3): " + set.tailSet(3)); // [3, 5, 8]
        System.out.println("headSet(5): " + set.headSet(5)); // [1, 2, 3]
        
        // 并发删除
        set.remove(5);
        System.out.println("After remove(5): " + set); // [1, 2, 3, 8]
    }
}

ConcurrentSkipListMap 基本用法：

import java.util.Map;
import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentSkipListMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new ConcurrentSkipListMap<>();
        
        // 并发添加键值对
        map.put("Alice", 95);
        map.put("Bob", 87);
        map.put("Charlie", 92);
        map.put("David", 88);
        
        // 按键自动排序
        System.out.println(map);
        // {Alice=95, Bob=87, Charlie=92, David=88}
        
        // 范围查询
        Map<String, Integer> subMap = map.subMap("Bob", "David");
        System.out.println("subMap: " + subMap); // {Bob=87, Charlie=92}
        
        // 获取第一个和最后一个键
        System.out.println("firstKey: " + map.firstKey()); // Alice
        System.out.println("lastKey: " + map.lastKey()); // David
    }
}

5.5 ConcurrentSkipListMap 应用

高并发排行榜实现：

import java.util.Map;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

class ConcurrentPlayer implements Comparable<ConcurrentPlayer> {
    private String name;
    private int score;
    
    public ConcurrentPlayer(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    public String getName() {
        return name;
    }
    
    public int getScore() {
        return score;
    }
    
    public void setScore(int score) {
        this.score = score;
    }
    
    @Override
    public int compareTo(ConcurrentPlayer other) {
        int scoreCompare = Integer.compare(other.score, this.score);
        if (scoreCompare != 0) {
            return scoreCompare;
        }
        return this.name.compareTo(other.name);
    }
    
    @Override
    public String toString() {
        return name + ": " + score;
    }
}

public class ConcurrentLeaderboard {
    private final ConcurrentSkipListMap<ConcurrentPlayer, String> leaderboard = 
        new ConcurrentSkipListMap<>();
    
    public void updateScore(String name, int score) {
        ConcurrentPlayer player = findPlayer(name);
        if (player != null) {
            leaderboard.remove(player);
            player.setScore(score);
            leaderboard.put(player, "");
        } else {
            leaderboard.put(new ConcurrentPlayer(name, score), "");
        }
    }
    
    private ConcurrentPlayer findPlayer(String name) {
        for (ConcurrentPlayer player : leaderboard.keySet()) {
            if (player.getName().equals(name)) {
                return player;
            }
        }
        return null;
    }
    
    public void printTopN(int n) {
        System.out.println("=== Top " + n + " ===");
        int rank = 1;
        for (ConcurrentPlayer player : leaderboard.keySet()) {
            if (rank > n) break;
            System.out.println(rank + ". " + player);
            rank++;
        }
    }
    
    public static void main(String[] args) throws InterruptedException {
        ConcurrentLeaderboard leaderboard = new ConcurrentLeaderboard();
        
        // 并发更新分数
        ExecutorService executor = Executors.newFixedThreadPool(10);
        for (int i = 0; i < 100; i++) {
            final int index = i;
            executor.submit(() -> {
                String name = "Player" + (index % 10);
                int score = (int) (Math.random() * 100);
                leaderboard.updateScore(name, score);
            });
        }
        
        executor.shutdown();
        executor.awaitTermination(5, TimeUnit.SECONDS);
        
        leaderboard.printTopN(5);
    }
}

时间窗口查询：

import java.time.LocalDateTime;
import java.util.Map;
import java.util.concurrent.ConcurrentSkipListMap;

public class TimeWindowQuery {
    private final ConcurrentSkipListMap<LocalDateTime, String> events = 
        new ConcurrentSkipListMap<>();
    
    public void addEvent(LocalDateTime time, String event) {
        events.put(time, event);
    }
    
    public Map<LocalDateTime, String> getEventsInWindow(
            LocalDateTime start, LocalDateTime end) {
        return events.subMap(start, end);
    }
    
    public Map<LocalDateTime, String> getEventsAfter(LocalDateTime time) {
        return events.tailMap(time);
    }
    
    public Map<LocalDateTime, String> getEventsBefore(LocalDateTime time) {
        return events.headMap(time);
    }
    
    public static void main(String[] args) {
        TimeWindowQuery query = new TimeWindowQuery();
        
        LocalDateTime now = LocalDateTime.now();
        query.addEvent(now.minusHours(2), "Event 2 hours ago");
        query.addEvent(now.minusHours(1), "Event 1 hour ago");
        query.addEvent(now.minusMinutes(30), "Event 30 minutes ago");
        query.addEvent(now, "Event now");
        
        // 查询最近1小时的事件
        LocalDateTime oneHourAgo = now.minusHours(1);
        Map<LocalDateTime, String> recentEvents = 
            query.getEventsAfter(oneHourAgo);
        
        System.out.println("=== Events in last hour ===");
        for (Map.Entry<LocalDateTime, String> entry : recentEvents.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

性能特点对比：

特性	ConcurrentSkipListMap	TreeMap	ConcurrentHashMap
线程安全	是	否	是
有序性	是（自然排序）	是（自然排序）	否
时间复杂度	O(log n)	O(log n)	O(1) 平均
内存开销	较高	较低	较低
适用场景	高并发有序数据	单线程有序数据	高并发无序数据

🔑 模式提炼： 跳表结构提供有序且线程安全的集合操作，适用于高并发场景下的排行榜、时间窗口查询等需求。相比红黑树，跳表的实现更简单且支持无锁并发。

第六章：缓存淘汰策略

6.1 LRU（Least Recently Used）

LRU（Least Recently Used）是一种缓存淘汰策略，当缓存满时，优先淘汰最近最少使用的数据。核心思想是：最近被访问的数据将来被访问的概率更高。

LinkedHashMap 实现 LRU：

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    
    public LRUCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true); // accessOrder = true
        this.maxCapacity = maxCapacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }
    
    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}
        
        // 访问 key 1，使其变为最近使用
        cache.get(1);
        System.out.println(cache); // {2=Two, 3=Three, 1=One}
        
        // 添加新元素，淘汰最久未使用的 key 2
        cache.put(4, "Four");
        System.out.println(cache); // {3=Three, 1=One, 4=Four}
    }
}

6.2 LRU 手动实现

手动实现 LRU 需要结合 HashMap 的 O(1) 查询特性和双向链表的维护顺序能力。

完整实现：

import java.util.HashMap;
import java.util.Map;

public class ManualLRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> cache;
    private final Node<K, V> head;
    private final Node<K, V> tail;
    
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;
        
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public ManualLRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        
        // 哨兵节点，简化边界处理
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }
    
    public V get(K key) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            return null;
        }
        
        // 访问后移动到尾部（最近使用）
        moveToTail(node);
        return node.value;
    }
    
    public void put(K key, V value) {
        Node<K, V> node = cache.get(key);
        
        if (node != null) {
            // 更新现有节点
            node.value = value;
            moveToTail(node);
        } else {
            // 创建新节点
            Node<K, V> newNode = new Node<>(key, value);
            cache.put(key, newNode);
            addToTail(newNode);
            
            // 检查是否需要淘汰
            if (cache.size() > capacity) {
                Node<K, V> lru = removeHead();
                cache.remove(lru.key);
            }
        }
    }
    
    private void moveToTail(Node<K, V> node) {
        removeNode(node);
        addToTail(node);
    }
    
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void addToTail(Node<K, V> node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }
    
    private Node<K, V> removeHead() {
        Node<K, V> node = head.next;
        removeNode(node);
        return node;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node<K, V> node = head.next;
        while (node != tail) {
            sb.append(node.key).append("=").append(node.value);
            if (node.next != tail) {
                sb.append(", ");
            }
            node = node.next;
        }
        sb.append("]");
        return sb.toString();
    }
    
    public static void main(String[] args) {
        ManualLRUCache<Integer, String> cache = new ManualLRUCache<>(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);
        System.out.println(cache); // [2=Two, 3=Three, 1=One]
        
        cache.put(4, "Four");
        System.out.println(cache); // [3=Three, 1=One, 4=Four]
    }
}

6.3 LFU（Least Frequently Used）

LFU（Least Frequently Used）淘汰策略优先淘汰访问频率最低的数据。相比 LRU，LFU 需要维护每个键的访问频率。

完整实现：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LFUCache<K, V> {
    private final int capacity;
    private int minFrequency;
    private final Map<K, Node<K, V>> keyToNode;
    private final Map<Integer, Set<Node<K, V>>> frequencyToKeys;
    
    private static class Node<K, V> {
        K key;
        V value;
        int frequency;
        
        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.frequency = 1;
        }
    }
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFrequency = 0;
        this.keyToNode = new HashMap<>();
        this.frequencyToKeys = new HashMap<>();
    }
    
    public V get(K key) {
        Node<K, V> node = keyToNode.get(key);
        if (node == null) {
            return null;
        }
        
        // 更新频率
        updateFrequency(node);
        return node.value;
    }
    
    public void put(K key, V value) {
        if (capacity <= 0) {
            return;
        }
        
        Node<K, V> node = keyToNode.get(key);
        
        if (node != null) {
            // 更新现有节点
            node.value = value;
            updateFrequency(node);
        } else {
            // 创建新节点
            if (keyToNode.size() >= capacity) {
                // 淘汰频率最低的节点
                evict();
            }
            
            Node<K, V> newNode = new Node<>(key, value);
            keyToNode.put(key, newNode);
            minFrequency = 1;
            frequencyToKeys.computeIfAbsent(1, k -> new HashSet<>()).add(newNode);
        }
    }
    
    private void updateFrequency(Node<K, V> node) {
        int oldFreq = node.frequency;
        int newFreq = oldFreq + 1;
        
        // 从旧频率集合中移除
        Set<Node<K, V>> oldSet = frequencyToKeys.get(oldFreq);
        oldSet.remove(node);
        
        // 如果旧频率集合为空且是最小频率，更新 minFrequency
        if (oldSet.isEmpty() && oldFreq == minFrequency) {
            minFrequency++;
        }
        
        // 添加到新频率集合
        node.frequency = newFreq;
        frequencyToKeys.computeIfAbsent(newFreq, k -> new HashSet<>()).add(node);
    }
    
    private void evict() {
        Set<Node<K, V>> minFreqSet = frequencyToKeys.get(minFrequency);
        Node<K, V> nodeToRemove = minFreqSet.iterator().next();
        
        minFreqSet.remove(nodeToRemove);
        keyToNode.remove(nodeToRemove.key);
    }
    
    @Override
    public String toString() {
        return keyToNode.toString();
    }
    
    public static void main(String[] args) {
        LFUCache<Integer, String> cache = new LFUCache<>(2);
        
        cache.put(1, "One");
        cache.put(2, "Two");
        System.out.println(cache);
        
        cache.get(1); // 频率：1->2
        cache.get(1); // 频率：2->3
        cache.get(2); // 频率：1->2
        
        cache.put(3, "Three"); // 淘汰 key 2（频率2）
        System.out.println(cache); // {1=One (freq=3), 3=Three (freq=1)}
    }
}

6.4 Redis 近似 LRU

Redis 的 LRU 实现是近似的，而非精确的。原因在于维护精确的 LRU 链表需要额外的内存开销。

24 位访问时间：

Redis 在对象结构中维护一个 24 位的 LRU 时钟，记录对象的最后访问时间。

// Redis 对象结构（简化版）
typedef struct redisObject {
    unsigned type:4;        // 对象类型
    unsigned encoding:4;    // 编码方式
    unsigned lru:LRU_BITS;  // 24位 LRU 时间
    int refcount;           // 引用计数
    void *ptr;              // 指向底层数据结构的指针
} robj;

随机采样策略：

当需要淘汰数据时，Redis 随机采样 N 个 key（默认 5 个），从中选择 LRU 值最大的 key 进行淘汰。

// Redis 近似 LRU 淘汰算法（简化版）
int evictionPoolPopulate(dict *masterDict, dict *evictionDict) {
    int samples = server.maxmemory_samples; // 默认 5
    
    for (int k = 0; k < samples; k++) {
        // 随机选择一个 key
        sds key = dictGetRandomKey(masterDict);
        robj *o = dictGetVal(key);
        
        // 计算 idle 时间
        long long idle = estimateObjectIdleTime(o);
        
        // 将 key 加入候选池
        addToEvictionPool(o, idle);
    }
    
    // 从候选池中选择 idle 时间最长的 key
    return selectBestEvictionCandidate();
}

6.5 Redis 近似 LFU（4.0+）

Redis 4.0 引入了 LFU 淘汰策略，使用 8 位的 Morris Counter 来记录访问频率，并引入频率衰减机制。

8 位 Morris Counter：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;  // LFU 模式下，高16位为时间，低8位为频率
    int refcount;
    void *ptr;
} robj;

#define LFU_BITS 8

频率衰减：

为了避免历史访问频率影响新数据的淘汰，LFU 使用衰减算法定期降低所有 key 的频率。

// LFU 频率更新（简化版）
void updateLFU(robj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    
    // 计算衰减
    unsigned long num_periods = server.unixtime - ldt;
    if (num_periods > LFU_DECAY_TIME) {
        counter = counter >> num_periods;
    }
    
    // 频率递增
    counter = lfuLogIncr(counter);
    o->lru = (ldt << 8) | counter;
}

6.6 Redis 7.0 listpack 改进

Redis 7.0 引入 listpack 替代 ziplist，用于小集合和有序集合，消除了连锁更新的问题。

listpack 结构：

+------+------+----------+----------+------+------+
| HEAD | ENTRY| ...      | ENTRY   | END  | TAIL |
+------+------+----------+----------+------+------+

优势：

• 消除了连锁更新风险（ziplist 的缺陷）
• 节省内存
• 提高插入删除性能

🔑 模式提炼： 淘汰策略本质上是缩容机制。LRU 适合时序性强的访问模式，LFU 适合热点数据明显的场景。Redis 的近似实现通过随机采样和概率计数在性能和准确性之间取得平衡。

第七章：系统级扩缩容

7.1 StringBuilder 扩容

StringBuilder 内部使用字符数组存储字符串，当容量不足时会触发扩容。

扩容机制：

// StringBuilder 源码（简化版）
public final class StringBuilder extends AbstractStringBuilder {
    
    public StringBuilder() {
        super(16); // 默认初始容量 16
    }
    
    @Override
    public StringBuilder append(String str) {
        super.append(str);
        return this;
    }
}

abstract class AbstractStringBuilder {
    char[] value;
    int count;
    
    AbstractStringBuilder(int capacity) {
        value = new char[capacity];
    }
    
    public AbstractStringBuilder append(String str) {
        if (str == null) {
            str = "null";
        }
        int len = str.length();
        ensureCapacityInternal(count + len);
        str.getChars(0, len, value, count);
        count += len;
        return this;
    }
    
    private void ensureCapacityInternal(int minimumCapacity) {
        if (minimumCapacity - value.length > 0) {
            expandCapacity(minimumCapacity);
        }
    }
    
    void expandCapacity(int minimumCapacity) {
        int newCapacity = value.length * 2 + 2; // 2倍 + 2
        if (newCapacity - minimumCapacity < 0) {
            newCapacity = minimumCapacity;
        }
        if (newCapacity < 0) {
            throw new OutOfMemoryError();
        }
        value = Arrays.copyOf(value, newCapacity);
    }
}

为什么 +2？

扩容公式 newCapacity = value.length * 2 + 2 中的 +2 是为了处理边界情况：

1. 当初始容量为 0 时，扩容后容量为 2（0 * 2 + 2）
2. 避免频繁扩容，提高性能
3. 历史遗留设计，早期版本用于处理空字符串情况

Compact Strings 影响：

Java 9 引入 Compact Strings 特性，StringBuilder 内部使用 byte[] 而非 char[] 来存储只包含 ASCII 字符的字符串，节省内存。

最佳实践：

public class StringBuilderBestPractice {
    public static void main(String[] args) {
        // 预估容量，避免频繁扩容
        StringBuilder sb = new StringBuilder(100);
        
        for (int i = 0; i < 1000; i++) {
            sb.append("Item ").append(i).append("\n");
        }
        
        System.out.println(sb.length());
        System.out.println(sb.capacity());
    }
}

7.2 线程池扩缩容

ThreadPoolExecutor 提供了灵活的线程池管理机制，支持动态扩容和缩容。

核心参数：

import java.util.concurrent.*;

public class ThreadPoolExample {
    public static void main(String[] args) {
        ThreadPoolExecutor executor = new ThreadPoolExecutor(
            5,                      // corePoolSize：核心线程数
            10,                     // maximumPoolSize：最大线程数
            60L,                    // keepAliveTime：空闲线程存活时间
            TimeUnit.SECONDS,       // 时间单位
            new LinkedBlockingQueue<>(100), // 工作队列
            Executors.defaultThreadFactory(), // 线程工厂
            new ThreadPoolExecutor.AbortPolicy() // 拒绝策略
        );
        
        // 提交任务
        for (int i = 0; i < 20; i++) {
            executor.submit(() -> {
                try {
                    Thread.sleep(1000);
                    System.out.println("Task executed by: " + 
                        Thread.currentThread().getName());
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        
        executor.shutdown();
    }
}

扩容流程：

任务提交
    ↓
核心线程数 < corePoolSize?
    ├─ 是 → 创建新核心线程
    └─ 否 → 工作队列已满?
              ├─ 否 → 加入队列
              └─ 是 → 当前线程数 < maximumPoolSize?
                      ├─ 是 → 创建非核心线程
                      └─ 否 → 执行拒绝策略

缩容机制：

当非核心线程空闲时间超过 keepAliveTime 时，会被回收。

// 动态调整线程池大小
public class DynamicThreadPool {
    public static void main(String[] args) throws InterruptedException {
        ThreadPoolExecutor executor = new ThreadPoolExecutor(
            2, 10, 5, TimeUnit.SECONDS,
            new LinkedBlockingQueue<>(10)
        );
        
        // 提交任务触发扩容
        for (int i = 0; i < 15; i++) {
            executor.submit(() -> {
                try {
                    Thread.sleep(2000);
                    System.out.println("Active threads: " + 
                        executor.getActiveCount());
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        
        System.out.println("Pool size: " + executor.getPoolSize());
        
        // 等待任务完成，观察缩容
        Thread.sleep(10000);
        System.out.println("Pool size after shrink: " + executor.getPoolSize());
        
        executor.shutdown();
    }
}

四种拒绝策略：

策略	行为	适用场景
AbortPolicy	抛出 RejectedExecutionException	需要明确感知任务被拒绝
CallerRunsPolicy	由提交任务的线程执行	能够接受任务执行延迟
DiscardPolicy	静默丢弃	允许丢失部分任务
DiscardOldestPolicy	丢弃队列中最老的任务	优先处理新任务

CallerRunsPolicy 隐含风险：

public class CallerRunsRisk {
    public static void main(String[] args) {
        ThreadPoolExecutor executor = new ThreadPoolExecutor(
            1, 1, 0, TimeUnit.SECONDS,
            new LinkedBlockingQueue<>(1),
            new ThreadPoolExecutor.CallerRunsPolicy()
        );
        
        // 主线程提交任务
        for (int i = 0; i < 5; i++) {
            final int taskId = i;
            executor.submit(() -> {
                System.out.println("Task " + taskId + " executed by: " + 
                    Thread.currentThread().getName());
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        
        executor.shutdown();
    }
}

常见线程池配置：

场景	corePoolSize	maximumPoolSize	队列类型	keepAliveTime
CPU 密集型	CPU 核心数 + 1	CPU 核心数 + 1	SynchronousQueue	0
IO 密集型	CPU 核心数 * 2	CPU 核心数 * 2	LinkedBlockingQueue	60s
混合型	CPU 核心数	CPU 核心数 * 2	LinkedBlockingQueue	30s

动态调整代码：

import java.util.concurrent.*;

public class DynamicAdjustment {
    public static void main(String[] args) {
        ThreadPoolExecutor executor = new ThreadPoolExecutor(
            5, 10, 60, TimeUnit.SECONDS,
            new LinkedBlockingQueue<>(100)
        );
        
        // 根据系统负载动态调整
        adjustThreadPoolSize(executor);
        
        executor.shutdown();
    }
    
    private static void adjustThreadPoolSize(ThreadPoolExecutor executor) {
        int cpuCores = Runtime.getRuntime().availableProcessors();
        double loadAverage = getSystemLoadAverage();
        
        if (loadAverage > cpuCores * 0.8) {
            // 高负载：减少线程数
            int newSize = Math.max(1, cpuCores / 2);
            executor.setCorePoolSize(newSize);
            executor.setMaximumPoolSize(newSize * 2);
        } else if (loadAverage < cpuCores * 0.3) {
            // 低负载：增加线程数
            int newSize = cpuCores * 2;
            executor.setCorePoolSize(newSize);
            executor.setMaximumPoolSize(newSize * 2);
        }
    }
    
    private static double getSystemLoadAverage() {
        return ManagementFactory.getOperatingSystemMXBean()
            .getSystemLoadAverage();
    }
}

Java 21+ 虚拟线程的影响

Java 21 引入的虚拟线程（Project Loom）彻底改变了线程池的设计假设。传统线程池的核心假设是"线程是昂贵资源"，因此需要复用线程来提高性能。虚拟线程使得线程创建成本极低，这一假设被打破。

虚拟线程的特性

虚拟线程是轻量级线程，由 JVM 管理，不直接映射到操作系统线程。其特点包括：

• 创建成本低：可以轻松创建数百万个虚拟线程
• 内存占用小：每个虚拟线程仅占用几百字节
• 阻塞不阻塞平台线程：虚拟线程阻塞时，平台线程可以执行其他虚拟线程

传统线程池 vs 虚拟线程

import java.util.concurrent.*;
import java.util.stream.IntStream;

public class VirtualThreadComparison {
    
    // 传统线程池：固定大小线程池
    public static void traditionalThreadPool() throws InterruptedException {
        ExecutorService executor = Executors.newFixedThreadPool(10);
        
        long startTime = System.currentTimeMillis();
        CountDownLatch latch = new CountDownLatch(1000);
        
        for (int i = 0; i < 1000; i++) {
            final int taskId = i;
            executor.submit(() -> {
                try {
                    Thread.sleep(100); // 模拟 IO 操作
                    System.out.println("Task " + taskId + " completed");
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                } finally {
                    latch.countDown();
                }
            });
        }
        
        latch.await();
        executor.shutdown();
        long duration = System.currentTimeMillis() - startTime;
        System.out.println("Traditional thread pool duration: " + duration + "ms");
    }
    
    // 虚拟线程：每个任务一个虚拟线程
    public static void virtualThreadPerTask() throws InterruptedException {
        ExecutorService executor = Executors.newVirtualThreadPerTaskExecutor();
        
        long startTime = System.currentTimeMillis();
        CountDownLatch latch = new CountDownLatch(1000);
        
        for (int i = 0; i < 1000; i++) {
            final int taskId = i;
            executor.submit(() -> {
                try {
                    Thread.sleep(100); // 模拟 IO 操作
                    System.out.println("Task " + taskId + " completed");
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                } finally {
                    latch.countDown();
                }
            });
        }
        
        latch.await();
        executor.shutdown();
        long duration = System.currentTimeMillis() - startTime;
        System.out.println("Virtual thread duration: " + duration + "ms");
    }
    
    // 虚拟线程：使用 try-with-resources 自动关闭
    public static void virtualThreadWithTryWithResources() throws InterruptedException {
        try (ExecutorService executor = Executors.newVirtualThreadPerTaskExecutor()) {
            CountDownLatch latch = new CountDownLatch(1000);
            
            IntStream.range(0, 1000).forEach(i -> {
                executor.submit(() -> {
                    try {
                        Thread.sleep(100);
                        System.out.println("Task " + i + " completed");
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    } finally {
                        latch.countDown();
                    }
                });
            });
            
            latch.await();
        }
    }
    
    public static void main(String[] args) throws InterruptedException {
        System.out.println("=== Traditional Thread Pool ===");
        traditionalThreadPool();
        
        System.out.println("\n=== Virtual Thread Per Task ===");
        virtualThreadPerTask();
        
        System.out.println("\n=== Virtual Thread with Try-With-Resources ===");
        virtualThreadWithTryWithResources();
    }
}

虚拟线程的适用场景

虚拟线程适用于 IO 密集型任务，不适合 CPU 密集型任务。

任务类型	适用线程池	原因
IO 密集型（HTTP 请求、数据库查询）	虚拟线程	阻塞操作不会浪费平台线程资源
CPU 密集型（计算、数据处理）	平台线程池	需要绑定到 CPU 核心进行计算
混合型	分离使用	IO 操作用虚拟线程，计算用平台线程

虚拟线程与平台线程的混合使用

import java.util.concurrent.*;

public class HybridThreadUsage {
    
    // 混合使用：IO 操作用虚拟线程，CPU 密集型任务用平台线程
    public static void hybridThreadPool() throws InterruptedException {
        // CPU 密集型任务的平台线程池
        ExecutorService cpuExecutor = Executors.newFixedThreadPool(
            Runtime.getRuntime().availableProcessors()
        );
        
        // IO 密集型任务的虚拟线程执行器
        ExecutorService ioExecutor = Executors.newVirtualThreadPerTaskExecutor();
        
        CountDownLatch latch = new CountDownLatch(100);
        
        for (int i = 0; i < 100; i++) {
            final int taskId = i;
            
            // 虚拟线程处理 IO 操作
            ioExecutor.submit(() -> {
                try {
                    // 模拟 IO 操作
                    Thread.sleep(50);
                    
                    // 将 CPU 密集型任务提交到平台线程池
                    Future<String> result = cpuExecutor.submit(() -> {
                        return performCPUIntensiveTask(taskId);
                    });
                    
                    System.out.println("Task " + taskId + " result: " + result.get());
                } catch (Exception e) {
                    Thread.currentThread().interrupt();
                } finally {
                    latch.countDown();
                }
            });
        }
        
        latch.await();
        
        ioExecutor.close();
        cpuExecutor.shutdown();
    }
    
    private static String performCPUIntensiveTask(int taskId) {
        // 模拟 CPU 密集型计算
        double result = 0;
        for (int i = 0; i < 100000; i++) {
            result += Math.sqrt(i);
        }
        return "Result-" + taskId + "-" + result;
    }
    
    public static void main(String[] args) throws InterruptedException {
        hybridThreadPool();
    }
}

注意事项

1. 不要用虚拟线程执行 CPU 密集型任务：虚拟线程仍然需要平台线程执行 CPU 操作，不会带来性能提升
2. 不要在虚拟线程中使用 synchronized 锁：会钉住平台线程，影响性能。应该使用 java.util.concurrent 下的锁机制
3. 不要限制虚拟线程数量：虚拟线程设计初衷就是可以大量创建，不需要像传统线程池那样限制大小
4. 正确处理中断：虚拟线程的可中断性更强，需要正确处理 InterruptedException

🔑 模式提炼： 虚拟线程打破了"线程是昂贵资源"的传统假设，使得"每个任务一个线程"成为可能。在 IO 密集型场景下，虚拟线程提供了更简单、更高效的并发编程模型。

7.3 Redis 渐进式 Rehash

Redis 的哈希表扩容采用渐进式 rehash 策略，避免一次性迁移导致的性能抖动。

为什么需要渐进式？

如果一次性迁移所有键值对，会导致：

1. 长时间阻塞主线程
2. 响应延迟激增
3. 可能触发超时

双哈希表结构：

// Redis 字典结构（简化版）
typedef struct dict {
    dictht ht[2];        // 两个哈希表
    long rehashidx;      // rehash 索引，-1 表示未进行 rehash
    unsigned long iterators; // 正在迭代的迭代器数量
} dict;

typedef struct dictht {
    dictEntry **table;   // 哈希表数组
    unsigned long size;  // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used;  // 已有节点数量
} dictht;

typedef struct dictEntry {
    void *key;           // 键
    union {
        void *val;       // 值
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next; // 下一个节点（链表解决冲突）
} dictEntry;

渐进式 Rehash 流程：

1. 触发条件：负载因子 > 1（或 > 5 且无子进程）
2. 分配空间：为 ht[1] 分配新空间（大小为第一个大于等于 ht[0].used * 2 的 2^n）
3. 渐进迁移：
   • rehashidx 记录当前迁移进度
   • 每次增删改查时，迁移一个 bucket
   • 定时任务辅助迁移
4. 完成迁移：ht[0] 清空，ht[1] 变为 ht[0]，ht[1] 重置

// Redis 渐进式 rehash（简化版）
int dictRehash(dict *d, int n) {
    int empty_visits = n * 10; // 最多访问 10n 个空 bucket
    
    while (n-- && d->ht[0].used != 0) {
        // 跳过空 bucket
        if (d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            continue;
        }
        
        // 迁移当前 bucket 的所有节点
        dictEntry *de, *nextde;
        de = d->ht[0].table[d->rehashidx];
        
        while (de) {
            nextde = de->next;
            
            // 计算在新哈希表中的位置
            unsigned int h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            
            // 插入到新哈希表
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    
    // 检查是否完成
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    
    return 1;
}

定时辅助迁移：

// Redis 定时任务辅助 rehash（简化版）
int incrementallyRehash(int dbid) {
    dict *d = server.db[dbid].dict;
    
    if (dictIsRehashing(d)) {
        // 每次迁移 100 个 bucket
        dictRehash(d, 100);
        return 1;
    }
    
    return 0;
}

缩容触发条件：

1. 负载因子 < 0.1
2. 无子进程执行
3. 缩容后的容量 >= 4

🔑 模式提炼： 渐进式迁移通过将大任务拆分为小任务，避免长时间阻塞，适用于需要平滑过渡的场景。核心思想是：将一次性操作分散到多次操作中执行。

第八章：扩缩容的通用设计模式

8.1 数据结构衍生关系

graph TD
    A[数组 Array] --> B[ArrayList]
    A --> C[HashMap]
    A --> D[ArrayDeque]
    
    E[链表 LinkedList] --> F[LRU Cache]
    
    C --> G[LinkedHashMap]
    C --> H[ConcurrentHashMap]
    C --> I[HashSet]
    
    J[二叉搜索树 BST] --> K[AVL Tree]
    J --> L[红黑树 Red-Black Tree]
    L --> M[TreeMap]
    L --> N[TreeSet]
    
    O[堆 Heap] --> P[PriorityQueue]
    
    Q[跳表 SkipList] --> R[ConcurrentSkipListMap]
    Q --> S[ConcurrentSkipListSet]
    Q --> T[Redis ZSet]

8.2 模式一：倍增策略表

数据结构/系统	扩容因子	初始容量	特殊处理
ArrayList	1.5x	10	newCapacity = old + (old >> 1)
HashMap	2x	16	必须是 2 的幂次方
StringBuilder	2x + 2	16	处理空数组边界
Redis	2x	4	必须是 2 的幂次方
Go slice	2x	0	容量 < 1024 时 2x，否则 1.25x

倍增策略的优势：

1. 均摊时间复杂度为 O(1)
2. 减少扩容频率
3. 内存利用率合理

8.3 模式二：渐进式迁移表

系统	迁移策略	触发时机	完成条件
Redis Rehash	每次操作迁移 1 个 bucket	负载因子 > 1	ht[0].used == 0
ConcurrentHashMap	分段迁移	节点数 > 阈值	所有 segment 迁移完成
Elasticsearch Reindex	Scroll 批量迁移	索引重建	所有文档迁移完成

渐进式迁移的关键点：

1. 维护新旧两个数据结构
2. 每次操作迁移少量数据
3. 读写操作同时访问新旧结构
4. 迁移完成后切换引用

8.4 模式三：水位线触发表

系统	扩容水位线	缩容水位线	触发动作
HashMap	size > capacity * loadFactor	不支持	2x 扩容
Redis	used > size * loadFactor	used < size * 0.1	2x 扩容 / 缩容
线程池	queue full & size < max	idle > keepAliveTime	创建线程 / 回收线程
K8s HPA	CPU > 80%	CPU < 50%	增加副本 / 减少副本

水位线设计原则：

1. 扩容水位线 > 使用水位线，预留缓冲
2. 缩容水位线 < 扩容水位线，避免抖动
3. 设置最小值和最大值，防止无限扩缩容

8.5 模式四：淘汰策略表

策略	核心思想	时间复杂度	适用场景
LRU	最近最少使用	O(1)（双向链表 + HashMap）	时序性强的访问模式
LFU	最少频率使用	O(1)（双 HashMap）	热点数据明显
FIFO	先进先出	O(1)（队列）	简单场景
Random	随机淘汰	O(1)	对淘汰精度要求不高
TTL	生存时间	O(log n)（时间轮）	有明确过期时间

总结

总结对比表

数据结构/系统	初始容量	扩容因子	缩容	特殊机制
ArrayList	10	1.5x	不支持	trimToSize() 手动缩容
HashMap	16	2x	不支持	负载因子 0.75
StringBuilder	16	2x + 2	不支持	Compact Strings
Redis Dict	4	2x	支持（< 0.1）	渐进式 Rehash
线程池	corePoolSize	maximumPoolSize	keepAliveTime	拒绝策略
ConcurrentSkipListMap	-	-	-	跳表结构

核心设计原则

1. 预分配：合理设置初始容量，减少扩容次数
2. 均摊 O(1)：倍增策略保证均摊时间复杂度为 O(1)
3. 渐进式：将大任务拆分为小任务，避免阻塞
4. 水位线：设置合理的扩缩容阈值，避免抖动

模式速查表

需求关键词	对应模式	方案	口诀
高性能扩容	倍增策略	1.5x 或 2x 扩容	翻倍扩容，均摊 O(1)
避免阻塞	渐进式迁移	分批迁移，双结构	分批迁移，平滑过渡
动态调整	水位线触发	设置阈值，自动调整	高扩低缩，避免抖动
限制大小	淘汰策略	LRU/LFU/TTL	淘汰即缩容

参考资料

• Java ArrayList 源码
• Java HashMap 源码
• Redis 源码 dict.c
• ThreadPoolExecutor 官方文档
• Collection Hierarchy