[小笔记] Java 集合类

匿名上传

发布时间:2025-12-01 14:30:03

线程不安全集合类

HashMap

HashMap 的默认容量大小为 16，重载因子为 0.75。

计算 key 的 hash 值然后做 mod 运算，将其存放在 bucket 中（默认容量为 16），如果出现冲突，bucket 上的数据就变成链表。如果单个链表上的数据量达到 8，构建红黑树来储存数据（一种自平衡二叉查询树）。当数据容量达到容量 * 重载因子后（默认是 16 * 0.75 = 12）或者多次出现数据碰撞，扩容容量，将原来的容量 * 2，然后重新构建 bucket 中的数据。

当 bucket 中未出现数据碰撞时，数据查询复杂度 O(1)。
当 bucket 中出现数据碰撞时，但是链表节点数量小于 8，数据查询复杂度 O(n)。
当 bucket 中的数据出现碰撞，且节点数量大于等于 8，数据查询复杂度为 O(logn)。

容量总是为 2 的幂次方的好处。

求 mod 时性能更好。

// 计算索引位置的标准方法 
int index = hash % length; 
// 当 length 是 2 的幂次方时的优化方法 
int index = hash & (length - 1);

Hash 分布更加均匀，减少碰撞。
扩容时的高效迁移

// 扩容时重新计算位置
if ((e.hash & oldCap) == 0) {
    // 保持原索引
} else {
    // 新索引 = 原索引 + oldCap
}

HashSet

其内部也是通过 HashMap 实现，只是将其 Value 用一个固定的值 PRESENT。

LinkedHashMap

继承于 HashMap，默认的 HashMap 中的元素是无序的，LinkedHashMap 内部自定义了 LinkedHashMap#Entry，它继承于 HashMap#Entry，不同的是它也是一个双向链表的节点。这样就 LinkedHashMap 中的元素就变得有序，可以通过 putFirst() 和 putLast() 方法来分别控制在链表的头部或者尾部来添加数据。

LinkedHashSet

它就相当于 HashSet 之于 HashMap，它继承于 HashSet，内部也通过 LinkedHashMap 来使其元素有序。

ArrayList

内部通过数组来保存元素，当数组的容量不足以来容纳元素时，会将其数组扩容，扩容会将原来旧的容量 * 2，如果之前的数组容量为 0，那么新的数组容量是 10。参考以下代码：

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 扩容
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        // 复制旧数组的数据        
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 之前的容量为 0，默认初始化大小为 10 的数组
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

private Object[] grow() {
    return grow(size + 1);
}

LinkedList

内部使用双向链表来储存元素，移除/添加首部/尾部的元素性能比 ArrayList 高，但是随机读写的性能比 ArrayList 低。它实现了栈/队列的方法。栈：pop() / push()；队列：poll / offer()。

ArrayDeque

内部使用数组来储存元素，默认的数组大小为 17。其中通过 head / tail 来记录首部和尾部的 index。它同样实现了栈/队列中的方法，相对于 LinkedList，它的特点是内部实现是数组。

PriorityQueue

使用数组来储存元素，默认数组大小为 11，使用堆排序来确认优先级。

线程安全集合类

ConcurrentHashMap

Java 7: 写操作分段加锁（分为 16 个段），读取操作无需加锁。 Java 8: 写操作锁单个 bucket / entry，初始化 table 时线程安全通过 CAS 保证线程安全，读操作无需加锁。

Hashtable

读写都会锁 Hashtable 对象，相对于 ConcurrentHashMap 性能较差。

CopyOnWriteArrayList

写的时候加锁，构建新的数组，将原来的数组复制到新的数组，然后将新的数据添加到新的数据末尾，源码：

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}

读取不需要加锁。