CS-Notes Java 容器指南：ArrayList、HashMap、ConcurrentHashMap 的选型标准与 JDK 源码级实现剖析

本文基于 CS-Notes 仓库的 Java 容器 笔记整理扩展，系统梳理 Java 容器框架中 Collection 与 Map 两大体系的实现选型依据（时间复杂度、有序性、线程安全三维度），并深入到 JDK 源码层面剖析 ArrayList 扩容与 Fail-Fast、HashMap 拉链法与桶下标的位运算优化、ConcurrentHashMap 分段锁与 size 无锁统计、LinkedHashMap 的 LRU 缓存实现、WeakHashMap 的弱引用缓存等核心机制。读完本文，你将能够准确回答「什么场景该用哪个容器」，并能看懂 JDK 集合源码中每一处关键设计背后的原因。

一、容器框架概览

Java 容器主要包括 Collection 和 Map 两种：Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

1.1 Collection 体系与选型

Set 集合（元素唯一）：

• TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet——HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
• HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作；并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
• LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

List 列表（有序、可重复、按下标访问）：

• ArrayList：基于动态数组实现，支持随机访问（O(1) 按下标取元素）。
• Vector：和 ArrayList 类似，但它是线程安全的（方法级 synchronized）。
• LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

Queue 队列：

• LinkedList：可以用它来实现双向队列（Deque）。
• PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

选型时可以按两个问题收敛：是否需要保持某种顺序（无序 → HashSet；插入顺序 → LinkedHashSet；自然/比较器排序 → TreeSet）？是否需要按下标随机访问（是 → ArrayList，否且频繁中间插删 → LinkedList）？

1.2 Map 体系与选型

• TreeMap：基于红黑树实现，键有序。
• HashMap：基于哈希表实现，键无序、支持 null 键。
• HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
• LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

Map 选型的关键维度是：是否需要按键有序（TreeMap）、是否需要保持顺序（LinkedHashMap）、是否需要并发读写（ConcurrentHashMap）。

二、容器中的设计模式

2.1 迭代器模式

Collection 继承了 Iterable 接口，其中的 iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。

从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象：

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

foreach 语法糖在字节码层面正是对 Iterator 的 hasNext() / next() 循环调用，因此「遍历中删除元素」的失败（fail-fast）行为与直接操作迭代器完全等价——这一点在后文 ArrayList 的 modCount 机制中会再次出现。

2.2 适配器模式

java.util.Arrays#asList() 可以把数组类型转换为 List 类型：

@SafeVarargs
public static <T> List<T> asList(T... a)

应该注意的是 asList() 的参数为泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组：

Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);

也可以使用以下方式调用 asList()：

List list = Arrays.asList(1, 2, 3);

从 JDK 源码结构看，asList 返回的是 Arrays 内部类封装的 List，它只是把原数组包了一层适配器，并没有复制数据，长度也固定为原数组长度——因此对它调用 add/remove 会抛出 UnsupportedOperationException，且对原数组元素的修改会直接反映到返回的 List 中。需要真正可变的 List 时应使用 new ArrayList<>(Arrays.asList(...)) 之类的写法先拷贝一份。

三、源码分析

如果没有特别说明，以下源码分析基于 JDK 1.8；HashMap 一节特别注明以 JDK 1.7 为主（因为其存储结构差异更大）。

在 IDEA 中 double shift 调出 Search EveryWhere，查找源码文件，找到之后就可以阅读源码（需先在 Project Structure 中查看 SDK sources）。

3.1 ArrayList

3.1.1 概览

因为 ArrayList 是基于数组实现的，所以支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问（它是一个空标记接口，算法可以从该标记判断应使用「按索引访问」还是「按迭代器访问」的策略）：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

数组的默认大小为 10：

private static final int DEFAULT_CAPACITY = 10;

3.1.2 扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，即 oldCapacity + oldCapacity/2。其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，为奇数就是 1.5 倍 − 0.5）。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    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++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

代码中有两处值得注意：一是 newCapacity - minCapacity < 0 的兜底——当一次批量添加（如 addAll）导致 1.5 倍仍不够时，直接扩到 minCapacity，避免连续扩容；二是 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8，JVM 对对象头与数组头部的保留空间）判断，超过则走 hugeCapacity() 抛 OutOfMemoryError 或按需求分配。

3.1.3 删除元素

需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看到 ArrayList 删除元素的代价是非常高的：

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

末尾 elementData[--size] = null 的注释写得很明白——把空位置 null 是「clear to let GC do its work」：如果列表后续被 trim 或不再增长，被删除的元素引用仍会被数组持有，置 null 才能让它被垃圾回收（对泛型集合而言，装箱对象、大对象尤其如此）。

3.1.4 序列化

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。

保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化：

transient Object[] elementData; // non-private to simplify nested class access

ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容：

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似：

ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

注意 writeObject 开头记录了 expectedModCount = modCount，结尾再比对一次——这就是用 modCount 做「序列化期间并发修改检测」的典型用法。

3.1.5 Fail-Fast（快速失败）

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。代码参考上节序列化中的 writeObject() 方法。

ArrayList 迭代器内部保存了创建迭代器时的 modCount 快照（expectedModCount），每次 next() 都会先比对，一旦发现「迭代过程中结构被改了」立即抛异常终止遍历，而不是在数据不一致的情况下继续读取——这是典型的 fail-fast 语义，目的是尽早暴露多线程误用或「边遍历边修改」的编程错误。

3.2 Vector

3.2.1 同步

它的实现与 ArrayList 类似，但是使用了 synchronized 进行同步：

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

3.2.2 扩容

Vector 的构造函数可以传入 capacityIncrement 参数，它的作用是在扩容时使容量 capacity 增长 capacityIncrement。如果这个参数的值小于等于 0，扩容时每次都令 capacity 为原来的两倍：

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

调用没有 capacityIncrement 的构造函数时，capacityIncrement 值被设置为 0，也就是说默认情况下 Vector 每次扩容时容量都会翻倍：

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

对比可见：ArrayList 固定 1.5 倍扩容，Vector 默认 2 倍扩容。2 倍扩容虽然减少了扩容次数，但瞬时多分配了内存，这也是 Vector 在现代代码中基本被弃用的原因之一。

3.2.3 与 ArrayList 的比较

• Vector 是同步的，因此开销就比 ArrayList 要大，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作完全可以由程序员自己来控制；
• Vector 每次扩容请求其大小的 2 倍（也可以通过构造函数设置增长的容量），而 ArrayList 是 1.5 倍。

3.2.4 替代方案

可以使用 Collections.synchronizedList() 得到一个线程安全的 ArrayList：

List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);

也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类：

List<String> list = new CopyOnWriteArrayList<>();

前者适合写少但要求读读互斥开销低的场景，后者适合读远多于写、可接受弱一致性的场景，二者的取舍见 3.3 节。

3.3 CopyOnWriteArrayList

3.3.1 读写分离

写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。

写操作需要加锁，防止并发写入时导致写入数据丢失。

写操作结束之后需要把原始数组指向新的复制数组：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

final void setArray(Object[] a) {
    array = a;
}

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

从源码结构看，array 字段是 volatile 的，setArray() 只是简单地整体替换引用：读线程永远看到的是某个完整的旧快照或新快照，不会出现「半更新」的中间状态——这正是「读无锁、写复制」能成立的根基。

3.3.2 适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

但是 CopyOnWriteArrayList 有其缺陷：

• 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
• 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。它保证的是一致性快照语义（一次迭代过程内看到的数据来自同一版本），而不是线性化的实时值。

3.4 LinkedList

3.4.1 概览

基于双向链表实现，使用 Node 存储链表节点信息：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每个链表存储了 first 和 last 指针：

transient Node<E> first;
transient Node<E> last;

first/last 双端指针让 LinkedList 得以同时高效支持栈（addFirst/peekFirst）、队列（addLast/peekFirst）和双向队列（addFirst/addLast 两端操作）三种角色——这也是它出现在 Queue 选型里的原因。

3.4.2 与 ArrayList 的比较

ArrayList 基于动态数组实现，LinkedList 基于双向链表实现。ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别：

• 数组支持随机访问，但插入删除的代价很高，需要移动大量元素；
• 链表不支持随机访问，但插入删除只需要改变指针。

需要补充一个常被误解的点：「中间插入/删除」在两者中都是 O(N)——LinkedList 的 O(1) 是指已经定位到具体节点之后修改指针的开销；而定位节点本身在链表中仍是 O(N) 的遍历。因此「频繁在中间插删就用 LinkedList」只在遍历式维护或已持有节点引用的场景下成立，按下标频繁随机操作时 ArrayList 反而更合适。

3.5 HashMap

为了便于理解，以下源码分析以 JDK 1.7 为主（JDK 1.8 在链表转红黑树、hash 扰动函数、扩容定位方式上有所不同，文末单独说明）。

3.5.1 存储结构

内部包含了一个 Entry 类型的数组 table。Entry 存储着键值对。它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶，一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry。

transient Entry[] table;

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }
}

hash 字段在 Entry 中被缓存，意味着后续在链表上比较两个 Entry 是否同一个 key 时，可以先比较 hash 再调用 key.equals()，避免重复计算扰动后的散列值。

3.5.2 拉链法的工作原理

HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");

• 新建一个 HashMap，默认大小为 16；
• 插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115 % 16 = 3。
• 插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118 % 16 = 6。
• 插入 <K3,V3> 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118 % 16 = 6，插在 <K2,V2> 前面。

应该注意到链表的插入是以头插法方式进行的，例如上面的 <K3,V3> 不是插在 <K2,V2> 后面，而是插入在链表头部。

查找需要分成两步进行：

• 计算键值对所在的桶；
• 在链表上顺序查找，时间复杂度显然和链表的长度成正比。

3.5.3 put 操作

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 键为 null 单独处理
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    // 确定桶下标
    int i = indexFor(hash, table.length);
    // 先找出是否已经存在键为 key 的键值对，如果存在的话就更新这个键值对的值为 value
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    // 插入新键值对
    addEntry(hash, key, value, i);
    return null;
}

HashMap 允许插入键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法，也就无法确定该键值对的桶下标，只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对：

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

使用链表的头插法，也就是新的键值对插在链表的头部，而不是链表的尾部：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 头插法，链表头部指向新的键值对
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

注意 inflateTable() 的延迟初始化策略：HashMap 构造时并不真正分配 table 数组，而是等到第一次 put 时才按 threshold 初始化（threshold 此时被临时复用为传入的 initialCapacity），这避免了空 HashMap 的无用内存分配。

3.5.4 确定桶下标

很多操作都需要先确定一个键值对所在的桶下标：

int hash = hash(key);
int i = indexFor(hash, table.length);

计算 hash 值（扰动函数）：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

扰动函数 h ^ (h >>> 16) 的意图（JDK 1.8 的写法）是把 hashCode 的高位信息混入低位，因为取模运算只关心低几位——如果直接用原始 hashCode，当桶容量较小时高位差异完全不起作用，大量仅高位不同的 key 会挤在同一桶上。

取模与位运算：令 x = 1<<4，即 x 为 2 的 4 次方，它具有以下性质：

x   : 00010000
x-1 : 00001111

令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数：

y       : 10110010
x-1     : 00001111
y&(x-1) : 00000010

这个性质和 y 对 x 取模效果是一样的：

y   : 10110010
x   : 00010000
y%x : 00000010

我们知道，位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能。

确定桶下标的最后一步是将 key 的 hash 值对桶个数取模：hash % capacity，如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算：

static int indexFor(int h, int length) {
    return h & (length-1);
}

这就是「容量必须是 2 的幂」的根本原因：只有此时 length-1 才是低位全 1 的掩码，& (length-1) 才等价于对 length 取模。

3.5.5 扩容——基本原理

设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此查找的复杂度为 O(N/M)。

为了让查找的成本降低，应该使 N/M 尽可能小，因此需要保证 M 尽可能大，也就是说 table 要尽可能大。HashMap 采用动态扩容来根据当前的 N 值来调整 M 值，使得空间效率和时间效率都能得到保证。

和扩容相关的参数主要有：capacity、size、threshold 和 load_factor：

参数	含义
capacity	table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。
size	键值对数量。
threshold	size 的临界值，当 size 大于等于 threshold 就必须进行扩容操作。
loadFactor	装载因子，table 能够使用的比例，threshold = (int)(capacity * loadFactor)。

static final int DEFAULT_INITIAL_CAPACITY = 16;

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

transient Entry[] table;

transient int size;

int threshold;

final float loadFactor;

transient int modCount;

从下面的添加元素代码中可以看出，当需要扩容时，令 capacity 为原来的两倍：

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

扩容使用 resize() 实现，需要注意的是，扩容操作同样需要把 oldTable 的所有键值对重新插入 newTable 中，因此这一步是很费时的：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

当 oldCapacity 已到 MAXIMUM_CAPACITY（1<<30）时不再扩容，而是把 threshold 置为 Integer.MAX_VALUE，此后 size 增长只会让桶越来越拥挤而不再 rehash。

3.5.6 扩容——重新计算桶下标

在进行扩容时，需要把键值对重新计算桶下标，从而放到对应的桶上。在前面提到，HashMap 使用 hash % capacity 来确定桶下标。HashMap capacity 为 2 的 n 次方这一特点能够极大降低重新计算桶下标操作的复杂度。

假设原数组长度 capacity 为 16，扩容之后 new capacity 为 32：

capacity     : 00010000
new capacity : 00100000

对于一个 Key，它的哈希值 hash 在第 5 位：

• 为 0，那么 hash % 00010000 = hash % 00100000，桶位置和原来一致；
• 为 1，hash % 00010000 = hash % 00100000 + 16，桶位置是原位置 + 16。

也就是说，扩容后每个元素只有两种可能：留在原桶，或者平移到「原桶 + 旧容量」的桶。JDK 1.8 的 transfer 正是利用这一点，只检查 hash & oldCap 一位即可决定移动方向，且链表被拆成 low/high 两条，进一步避免了头插法导致的链表逆序。

3.5.7 计算数组容量

HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。

先考虑如何求一个数的掩码，对于 10010000，它的掩码为 11111111，可以使用以下方法得到：

mask |= mask >> 1    11011000
mask |= mask >> 2    11111110
mask |= mask >> 4    11111111

mask+1 是大于原始数字的最小的 2 的 n 次方：

num     10010000
mask+1 100000000

以下是 HashMap 中计算数组容量的代码：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

先 cap - 1 是为了处理传入值本身就是 2 的幂的情况（此时不应再进一位）；末尾的三段返回值分别处理非法输入（返回 1）与超过上限（钳制到 MAXIMUM_CAPACITY）。

3.5.8 链表转红黑树

从 JDK 1.8 开始，一个桶存储的链表长度大于等于 8 时会将链表转换为红黑树（且桶容量不足 64 时优先扩容而非转树；树在退化到 6 个节点以下时会转回链表），把最坏 O(N) 的桶内查找降到 O(logN)，防御「hashCode 质量差导致单桶过长」的极端情况。

3.5.9 与 Hashtable 的比较

• Hashtable 使用 synchronized 来进行同步。
• HashMap 可以插入键为 null 的 Entry。
• HashMap 的迭代器是 fail-fast 迭代器。
• HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。

Hashtable 的方法级锁会让所有读写操作互相阻塞，且不允许 null 键值——现代代码应使用 ConcurrentHashMap 替代（见 3.6 节）。

3.6 ConcurrentHashMap

3.6.1 存储结构

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

ConcurrentHashMap 和 HashMap 实现上类似，最主要的差别是 ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）。

Segment 继承自 ReentrantLock：

static final class Segment<K,V> extends ReentrantLock implements Serializable {

    private static final long serialVersionUID = 2249069246763182397L;

    static final int MAX_SCAN_RETRIES =
        Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

    transient volatile HashEntry<K,V>[] table;

    transient int count;

    transient int modCount;

    transient int threshold;

    final float loadFactor;
}

final Segment<K,V>[] segments;

默认的并发级别为 16，也就是说默认创建 16 个 Segment：

static final int DEFAULT_CONCURRENCY_LEVEL = 16;

HashEntry 中 value 与 next 都是 volatile：value 的可见性保证 put 后其他线程能立即读到新值，next 的可见性则支持 putIfAbsent 这类无锁插入链表的正确性。

3.6.2 size 操作

每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数：

/**
 * The number of elements. Accessed only either within locks
 * or among other volatile reads that maintain visibility.
 */
transient int count;

在执行 size 操作时，需要遍历所有 Segment 然后把 count 累计起来。

ConcurrentHashMap 在执行 size 操作时先尝试不加锁，如果连续两次不加锁操作得到的结果一致，那么可以认为这个结果是正确的。

尝试次数使用 RETRIES_BEFORE_LOCK 定义，该值为 2，retries 初始值为 -1，因此尝试次数为 3。

如果尝试的次数超过 3 次，就需要对每个 Segment 加锁：

/**
 * Number of unsynchronized retries in size and containsValue
 * methods before resorting to locking. This is used to avoid
 * unbounded retries if tables undergo continuous modification
 * which would make it impossible to obtain an accurate result.
 */
static final int RETRIES_BEFORE_LOCK = 2;

public int size() {
    // Try a few times to get accurate count. On failure due to
    // continuous async changes in table, resort to locking.
    final Segment<K,V>[] segments = this.segments;
    int size;
    boolean overflow; // true if size overflows 32 bits
    long sum;         // sum of modCounts
    long last = 0L;   // previous sum
    int retries = -1; // first iteration isn't retry
    try {
        for (;;) {
            // 超过尝试次数，则对每个 Segment 加锁
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    ensureSegment(j).lock(); // force creation
            }
            sum = 0L;
            size = 0;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if (seg != null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    if (c < 0 || (size += c) < 0)
                        overflow = true;
                }
            }
            // 连续两次得到的结果一致，则认为这个结果是正确的
            if (sum == last)
                break;
            last = sum;
        }
    } finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();
        }
    }
    return overflow ? Integer.MAX_VALUE : size;
}

这里用 sum（各 Segment modCount 之和）作为「世界是否发生了变化」的探针：两轮统计的 modCount 总和相等，说明期间没有任何结构性变化，size 结果可信；不等则重试，最多 3 次后兜底加锁。注释里也写明了为什么要有上限——「avoid unbounded retries if tables undergo continuous modification」。

3.6.3 JDK 1.8 的改动

JDK 1.7 使用分段锁机制来实现并发更新操作，核心类为 Segment，它继承自重入锁 ReentrantLock，并发度与 Segment 数量相等。

JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。

并且 JDK 1.8 的实现也在链表过长时会转换为红黑树。

从源码结构看，1.8 彻底移除了 Segment 类，改为 Node 数组 + 桶级别并发控制：空桶插入用 CAS，非空桶用 synchronized 锁住桶头节点，count 统计则改为 baseCount + CounterCell 数组的分段计数（LongAdder 思想）。这意味着 1.8 的并发粒度从「16 个段」细化到了「每个桶」，相同 table 容量下并发度显著提升。

3.7 LinkedHashMap

3.7.1 存储结构

继承自 HashMap，因此具有和 HashMap 一样的快速查找特性：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

内部维护了一个双向链表，用来维护插入顺序或者 LRU 顺序：

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

accessOrder 决定了顺序，默认为 false，此时维护的是插入顺序：

final boolean accessOrder;

LinkedHashMap 最重要的是以下用于维护顺序的函数，它们会在 put、get 等方法中调用：

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

这两个方法是「模板方法」钩子：HashMap 中它们是空实现，LinkedHashMap 覆盖后让父类的 put/get 流程「顺路」完成顺序维护，无需重写整个算法。

3.7.2 afterNodeAccess()

当一个节点被访问时，如果 accessOrder 为 true，则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后，在每次访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点：

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

从源码结构看，这是标准的「从链表摘除再挂到尾部」三步双向指针操作（断 before/after、挂到 last 之后、更新 head/tail），整段代码没有一次哈希计算，因此开启 accessOrder 后每次 get 的额外开销只是 O(1) 的指针调整。

3.7.3 afterNodeInsertion()

在 put 等操作之后执行，当 removeEldestEntry() 方法返回 true 时会移除最晚的节点，也就是链表首部节点 first：

evict 只有在构建 Map 的时候才为 false，在这里为 true。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry() 默认为 false，如果需要让它为 true，需要继承 LinkedHashMap 并且覆盖这个方法的实现，这在实现 LRU 的缓存中特别有用，通过移除最近最久未使用的节点，从而保证缓存空间足够，并且缓存的数据都是热点数据：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

3.7.4 LRU 缓存

以下是使用 LinkedHashMap 实现的一个 LRU 缓存：

• 设定最大缓存空间 MAX_ENTRIES 为 3；
• 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true，开启 LRU 顺序；
• 覆盖 removeEldestEntry() 方法实现，在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除。

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_ENTRIES = 3;

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);
    }
}

public static void main(String[] args) {
    LRUCache<Integer, String> cache = new LRUCache<>();
    cache.put(1, "a");
    cache.put(2, "b");
    cache.put(3, "c");
    cache.get(1);
    cache.put(4, "d");
    System.out.println(cache.keySet());
}

运行输出：

[3, 1, 4]

推演一遍：put 1/2/3 后链表顺序为 1→2→3；cache.get(1) 把 1 移到尾部变成 2→3→1；put(4) 后 size=4 超过 MAX_ENTRIES，首部节点 2（最久未访问）被驱逐，最终 keySet 按 LRU 顺序为 [3, 1, 4]。注意该实现不是线程安全的，并发场景应配合外部锁（如 Collections.synchronizedMap 包装）使用。

3.8 WeakHashMap

3.8.1 存储结构

WeakHashMap 的 Entry 继承自 WeakReference，被 WeakReference 关联的对象在下一次垃圾回收时会被回收：

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V>

WeakHashMap 主要用来实现缓存，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收。它典型的使用方式是给「外部已有生命周期管理」的对象附加元数据（如属性、监听器）：一旦外部再无强引用指向 key，条目就会自动消失，不会造成内存泄漏——这是它与普通 Map 缓存的本质区别：普通 Map 会阻止 key 被回收，WeakHashMap 则主动让位给 GC。

3.8.2 ConcurrentCache：分代缓存实践

Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 来实现缓存功能。

ConcurrentCache 采取的是分代缓存：

• 经常使用的对象放入 eden 中，eden 使用 ConcurrentHashMap 实现，不用担心会被回收（伊甸园）；
• 不常用的对象放入 longterm，longterm 使用 WeakHashMap 实现，这些老对象会被垃圾收集器回收。
• 当调用 get() 方法时，会先从 eden 区获取，如果没有找到的话再到 longterm 获取，当从 longterm 获取到就把对象放入 eden 中，从而保证经常被访问的节点不容易被回收。
• 当调用 put() 方法时，如果 eden 的大小超过了 size，那么就将 eden 中的所有对象都放入 longterm 中，利用虚拟机回收掉一部分不经常使用的对象。

public final class ConcurrentCache<K, V> {
    private final int size;
    private final Map<K, V> eden;
    private final Map<K, V> longterm;

    public ConcurrentCache(int size) {
        this.size = size;
        this.eden = new ConcurrentHashMap<>(size);
        this.longterm = new WeakHashMap<>(size);
    }

    public V get(K k) {
        V v = this.eden.get(k);
        if (v == null) {
            v = this.longterm.get(k);
            if (v != null)
                this.eden.put(k, v);
        }
        return v;
    }

    public void put(K k, V v) {
        if (this.eden.size() >= size) {
            this.longterm.putAll(this.eden);
            this.eden.clear();
        }
        this.eden.put(k, v);
    }
}

这个设计的巧妙之处在于「用 GC 代替淘汰算法」：eden 保证热点数据 O(1) 且不被回收，longterm 作为溢出区把淘汰决策交给 JVM（不再被 eden 引用的对象在下一次 GC 时自动消失），既不需要 LRU 的访问计数，也不会像固定容量缓存那样误伤长尾数据。它借鉴的正是 JVM 自身的分代思想：年轻代（eden）存热点，老年代（longterm）存长存数据并由收集器负责回收。

四、小结：一张选型速查表

容器	数据结构	顺序	线程安全	典型场景
ArrayList	动态数组	插入顺序	否	随机访问为主，预知容量可避免 1.5 倍扩容
LinkedList	双向链表	插入顺序	否	频繁两端操作、用作栈/双端队列
Vector	同步动态数组	插入顺序	是（synchronized）	遗留代码，新代码避免
CopyOnWriteArrayList	写时复制数组	插入顺序	是	读远多于写、可接受快照一致性
HashSet / LinkedHashSet / TreeSet	哈希表 / 哈希表+链表 / 红黑树	无序 / 插入顺序 / 键有序	否	去重；需有序查找范围用 TreeSet
HashMap	桶数组+拉链（1.8 起超 8 转红黑树）	无序	否	通用键值存储
LinkedHashMap	HashMap+双向链表	插入顺序 / LRU	否	保持顺序、LRU 缓存
HashTable	同步桶数组	无序	是（synchronized）	遗留类，用 ConcurrentHashMap 替代
ConcurrentHashMap	分段锁（1.7）/ 桶级 CAS+synchronized（1.8）	无序	是	高并发键值存储
WeakHashMap	桶数组+弱引用 Entry	无序	否	附加元数据、由 GC 自动清理的缓存

参考资料

• Eckel B. Java 编程思想 [M]. 机械工业出版社, 2002.
• Java 集合框架（Collection Framework）官方设计文档中关于 Iterator 模式、适配器模式（asList）的经典论述。
• 原文档 Java 容器 的参考资料中还列有 HashMap 1.8 重构解析、ConcurrentHashMap 高并发实现机制、asList 缺陷分析等延伸阅读主题，可结合本仓库 Java 并发（分段锁、CAS 相关原理）与 Java 虚拟机（GC 与弱引用回收机制）两篇笔记交叉阅读。