Java 常用集合与 API 详解#

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

4
    private static final int DEFAULT_CAPACITY = 10;       // 初始容量
5
    private static final Object[] EMPTY_ELEMENTDATA = {};  // 空数组常量
6
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 区分无参构造
7
    transient Object[] elementData;  // 存储元素的数组，未被序列化
8
    private int size;                 // 实际元素数量
9
    protected transient int modCount = 0;  // 结构修改计数（fail-fast）
10
}

1
new ArrayList<>();                 // elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
2
new ArrayList<>(int initialCapacity);
3
new ArrayList<>(Collection<? extends E> c);

1
public boolean add(E e) {
2
    modCount++;
3
    add(e, elementData, size);
4
}
5

6
private void add(E e, Object[] elementData, int s) {
7
    if (s == elementData.length)  // 容量已满，需扩容
8
        elementData = grow();
9
    elementData[s] = e;
10
    size = s + 1;
11
}
12

13
private Object[] grow() {
14
    return grow(size + 1);
15
}
16

17
private Object[] grow(int minCapacity) {
18
    int oldCapacity = elementData.length;
19
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5 倍
20
    if (newCapacity - minCapacity < 0)
21
        newCapacity = minCapacity;
22
    if (newCapacity - MAX_ARRAY_SIZE > 0)               // 接近 Integer.MAX_VALUE
23
        newCapacity = hugeCapacity(minCapacity);
24
    return elementData = Arrays.copyOf(elementData, newCapacity);
25
}

1
public E next() {
2
    checkForComodification();
3
    ...
4
}
5

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

1
public class LinkedList<E> extends AbstractSequentialList<E>
2
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
3

4
    transient int size = 0;
5
    transient Node<E> first;   // 头节点
6
    transient Node<E> last;    // 尾节点
7

8
    private static class Node<E> {
9
        E item;
10
        Node<E> next;
11
        Node<E> prev;
12
        Node(E item, Node<E> next, Node<E> prev) {
13
            this.item = item; this.next = next; this.prev = prev;
14
        }
15
    }
16
}

1
public void addFirst(E e) {
2
    Node<E> f = first;
3
    Node<E> newNode = new Node<>(null, f, null);
4
    first = newNode;
5
    if (f == null) last = newNode;
6
    else f.prev = newNode;
7
    size++;
8
    modCount++;
9
}
10

11
public void addLast(E e) {
12
    Node<E> l = last;
13
    Node<E> newNode = new Node<>(e, null, l);
14
    last = newNode;
15
    if (l == null) first = newNode;
16
    else l.next = newNode;
17
    size++;
18
    modCount++;
19
}
20

21
public E get(int index) {
22
    checkElementIndex(index);
23
    return node(index).item;  // 这里会根据 index 决定从前往后还是从后往前遍历
24
}
25

26
Node<E> node(int index) {
27
    if (index < (size >> 1)) {       // 前半段，从前往后
28
        Node<E> x = first;
29
        for (int i = 0; i < index; i++) x = x.next;
30
        return x;
31
    } else {                          // 后半段，从后往前
32
        Node<E> x = last;
33
        for (int i = size - 1; i > index; i--) x = x.prev;
34
        return x;
35
    }
36
}

1
public synchronized boolean add(E e) {
2
    modCount++;
3
    ensureCapacityHelper(elementCount + 1);
4
    elementData[elementCount++] = e;
5
    return true;
6
}
7

8
private void grow(int minCapacity) {
9
    int oldCapacity = elementData.length;
10
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
11
    ...
12
}

1
public class Stack<E> extends Vector<E> {
2
    public E push(E item) { add(item); return item; }
3
    public synchronized E pop() { ... }
4
    public synchronized E peek() { ... }
5
    public boolean empty() { return size() == 0; }
6
    public synchronized int search(Object o) { return indexOf(o) + 1; }
7
}

1
public class HashSet<E> extends AbstractSet<E>
2
        implements Set<E>, Cloneable, java.io.Serializable {
3

4
    private transient HashMap<E, Object> map;
5
    private static final Object PRESENT = new Object();
6

7
    public HashSet() { map = new HashMap<>(); }
8
    public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); }
9
    public HashSet(int initialCapacity, float loadFactor) {
10
        map = new HashMap<>(initialCapacity, loadFactor);
11
    }
12

13
    public boolean add(E e) {
14
        return map.put(e, PRESENT) == null;
15
    }
16

17
    public boolean contains(Object o) {
18
        return map.containsKey(o);
19
    }
20

21
    public boolean remove(Object o) {
22
        return map.remove(o) == PRESENT;
23
    }
24

25
    public int size() { return map.size(); }
26
}

1
Set<String> set = new HashSet<>();
2
set.add("a");
3
set.add("b");
4
set.add("a");       // 不会被加入
5
System.out.println(set.size());  // 2
6

7
// 自定义对象去重
8
class User {
9
    String name;
10
    int age;
11
    @Override public boolean equals(Object o) {
12
        if (this == o) return true;
13
        if (!(o instanceof User)) return false;
14
        User u = (User) o;
15
        return age == u.age && Objects.equals(name, u.name);
16
    }
17
    @Override public int hashCode() { return Objects.hash(name, age); }
18
}
19
Set<User> users = new HashSet<>();
20
users.add(new User("tom", 18));
21
users.add(new User("tom", 18));  // 不会加入

1
public LinkedHashSet() { super(16, .75f, true); }
2

3
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
4
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
5
}

1
class LRUCache<K, V> extends LinkedHashMap<K, V> {
2
    private final int maxSize;
3
    public LRUCache(int maxSize) {
4
        super(16, .75f, true);  // accessOrder=true
5
        this.maxSize = maxSize;
6
    }
7
    @Override
8
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
9
        return size() > maxSize;
10
    }
11
}

1
public class TreeSet<E> extends AbstractSet<E>
2
        implements NavigableSet<E>, Cloneable, java.io.Serializable {
3
    private transient NavigableMap<E, Object> m;
4
    private static final Object PRESENT = new Object();
5

6
    public TreeSet() { this(new TreeMap<>()); }
7
    public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); }
8
}

1
// 范围操作
2
E lower(E e);       // 小于 e 的最大元素
3
E floor(E e);       // 小于或等于 e 的最大元素
4
E ceiling(E e);     // 大于或等于 e 的最小元素
5
E higher(E e);      // 大于 e 的最小元素
6

7
// 头尾
8
E first();          // 最小的
9
E last();           // 最大的
10
E pollFirst();      // 取出并移除最小
11
E pollLast();       // 取出并移除最大
12

13
// 子集视图
14
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
15
NavigableSet<E> headSet(E toElement, boolean inclusive);
16
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
17

18
// 逆序
19
NavigableSet<E> descendingSet();
20
Iterator<E> descendingIterator();

1
// 1. 自然顺序（元素实现 Comparable）
2
TreeSet<Integer> ts1 = new TreeSet<>();
3
ts1.add(3); ts1.add(1); ts1.add(2);
4
// 遍历：1 2 3
5

6
// 2. 自定义比较器
7
TreeSet<String> ts2 = new TreeSet<>(Comparator.comparingInt(String::length));
8
ts2.add("aa"); ts2.add("b"); ts2.add("ccc");
9
// 遍历：b aa ccc（按长度升序，长度相同按 String 自然顺序）
10

11
// 3. Lambda 比较器（Java 8+）
12
TreeSet<User> ts3 = new TreeSet<>((a, b) -> Integer.compare(a.getAge(), b.getAge()));

1
┌────────────────────┐
2
│   table (Node[])   │
3
│  ┌────┐ ┌────┐    │
4
│  │ [] │ │[N1]│→[N2]│→[N3]│   链表长度 < 8
5
│  └────┘ └────┘    │
6
│  ┌────┐ ┌────┐    │
7
│  │ [] │ │[T1]│─→[T2]│        红黑树 (Node 数 >= 8 且 table 长度 >= 64)
8
│  └────┘ └────┘    │
9
└────────────────────┘

1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   // 16
2
static final float DEFAULT_LOAD_FACTOR = 0.75f;
3
static final int TREEIFY_THRESHOLD = 8;                // 链表转红黑树阈值
4
static final int UNTREEIFY_THRESHOLD = 6;              // 红黑树退化为链表阈值
5
static final int MIN_TREEIFY_CAPACITY = 64;            // 树化最小表长度
6

7
transient Node<K, V>[] table;
8
transient int size;
9
int threshold;             // 扩容阈值 = capacity * loadFactor
10
final float loadFactor;

1
static class Node<K, V> implements Map.Entry<K, V> {
2
    final int hash;
3
    final K key;
4
    V value;
5
    Node<K, V> next;
6
}

1
static final int hash(Object key) {
2
    int h;
3
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4
}

1
static int indexFor(int h, int length) {
2
    return h & (length - 1);  // 等价于 h % length，length 必为 2 的幂
3
}

1
public V put(K key, V value) {
2
    return putVal(hash(key), key, value, false, true);
3
}
4

5
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
6
    Node<K, V>[] tab; Node<K, V> p; int n, i;
7
    // 1. 表为空则初始化
8
    if ((tab = table) == null || (n = tab.length) == 0)
9
        n = (tab = resize()).length;
10
    // 2. 计算下标，桶为空则直接放
11
    if ((p = tab[i = (n - 1) & hash]) == null)
12
        tab[i] = newNode(hash, key, value, null);
13
    else {
14
        Node<K, V> e; K k;
15
        // 3. 桶不为空：先比较头节点
16
        if (p.hash == hash &&
17
            ((k = p.key) == key || (key != null && key.equals(k))))
18
            e = p;
19
        // 4. 红黑树节点则走树插入
20
        else if (p instanceof TreeNode)
21
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
22
        // 5. 链表：遍历到末尾追加，必要时树化
23
        else {
24
            for (int binCount = 0; ; ++binCount) {
25
                if ((e = p.next) == null) {
26
                    p.next = newNode(hash, key, value, null);
27
                    if (binCount >= TREEIFY_THRESHOLD - 1)
28
                        treeifyBin(tab, hash);  // 链表长度 >= 8 时尝试树化
29
                    break;
30
                }
31
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
32
                    break;
33
                p = e;
34
            }
35
        }
36
        // 6. 已存在的 key：替换值
37
        if (e != null) {
38
            V oldValue = e.value;
39
            if (!onlyIfAbsent || oldValue == null)
40
                e.value = value;
41
            afterNodeAccess(e);  // LinkedHashMap 用
42
            return oldValue;
43
        }
44
    }
45
    ++modCount;
46
    if (++size > threshold)
47
        resize();
48
    afterNodeInsertion(evict);   // LinkedHashMap 用
49
    return null;
50
}

1
final Node<K, V>[] resize() {
2
    Node<K, V>[] oldTab = table;
3
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
4
    int oldThr = threshold;
5
    int newCap, newThr = 0;
6
    if (oldCap > 0) {
7
        if (oldCap >= MAXIMUM_CAPACITY) {
8
            threshold = Integer.MAX_VALUE;
9
            return oldTab;
10
        }
11
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
12
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
13
            newThr = oldThr << 1;  // 阈值翻倍
14
    }
15
    else if (oldThr > 0)
16
        newCap = oldThr;
17
    else {
18
        newCap = DEFAULT_INITIAL_CAPACITY;
19
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
20
    }
21
    if (newThr == 0) {
22
        float ft = (float) newCap * loadFactor;
23
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY
24
                  ? (int) ft : Integer.MAX_VALUE);
25
    }
26
    threshold = newThr;
27
    @SuppressWarnings({"rawtypes","unchecked"})
28
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
29
    table = newTab;
30
    if (oldTab != null) {
31
        for (int j = 0; j < oldCap; ++j) {
32
            Node<K, V> e;
33
            if ((e = oldTab[j]) != null) {
34
                oldTab[j] = null;
35
                if (e.next == null)
36
                    newTab[e.hash & (newCap - 1)] = e;
37
                else if (e instanceof TreeNode)
38
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
39
                else {
40
                    // 链表拆分：JDK 8 优化，避免重新计算 hash
41
                    Node<K, V> loHead = null, loTail = null;
42
                    Node<K, V> hiHead = null, hiTail = null;
43
                    Node<K, V> next;
44
                    do {
45
                        next = e.next;
46
                        // 关键：根据 hash & oldCap == 0 决定节点位置
47
                        if ((e.hash & oldCap) == 0) {
48
                            if (loTail == null) loHead = e;
49
                            else loTail.next = e;
50
                            loTail = e;
51
                        } else {
52
                            if (hiTail == null) hiHead = e;
53
                            else hiTail.next = e;
54
                            hiTail = e;
55
                        }
56
                    } while ((e = next) != null);
57
                    if (loTail != null) {
58
                        loTail.next = null;
59
                        newTab[j] = loHead;
60
                    }
61
                    if (hiTail != null) {
62
                        hiTail.next = null;
63
                        newTab[j + oldCap] = hiHead;
64
                    }
65
                }
66
            }
67
        }
68
    }
69
    return newTab;
70
}

1
public V get(Object key) {
2
    Node<K, V> e;
3
    return (e = getNode(hash(key), key)) == null ? null : e.value;
4
}
5

6
final Node<K, V> getNode(int hash, Object key) {
7
    Node<K, V>[] tab; Node<K, V> first, e; int n; K k;
8
    if ((tab = table) != null && (n = tab.length) > 0 &&
9
        (first = tab[(n - 1) & hash]) != null) {
10
        // 1. 先查头节点
11
        if (first.hash == hash &&
12
            ((k = first.key) == key || (key != null && key.equals(k))))
13
            return first;
14
        // 2. 链表 / 树继续查找
15
        if ((e = first.next) != null) {
16
            if (first instanceof TreeNode)
17
                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
18
            do {
19
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
20
                    return e;
21
            } while ((e = e.next) != null);
22
        }
23
    }
24
    return null;
25
}

1
if (binCount >= TREEIFY_THRESHOLD - 1)  // 链表长度 >= 8
2
    treeifyBin(tab, hash);
3

4
if (tab.length < MIN_TREEIFY_CAPACITY)  // 表长度 < 64
5
    resize();   // 优先扩容而不是树化

1
static class Entry<K, V> extends HashMap.Node<K, V> {
2
    Entry<K, V> before, after;
3
    Entry(int hash, K key, V value, Node<K, V> next) {
4
        super(hash, key, value, next);
5
    }
6
}
7

8
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
9
    super(initialCapacity, loadFactor);
10
    this.accessOrder = accessOrder;
11
}

1
public class LRU<K, V> extends LinkedHashMap<K, V> {
2
    private final int capacity;
3
    public LRU(int capacity) {
4
        super(16, 0.75f, true);
5
        this.capacity = capacity;
6
    }
7
    @Override
8
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
9
        return size() > capacity;
10
    }
11
}

1
Map.Entry<K, V> lowerEntry(K key);
2
Map.Entry<K, V> floorEntry(K key);
3
Map.Entry<K, V> ceilingEntry(K key);
4
Map.Entry<K, V> higherEntry(K key);
5

6
Map.Entry<K, V> firstEntry();
7
Map.Entry<K, V> lastEntry();
8
Map.Entry<K, V> pollFirstEntry();
9
Map.Entry<K, V> pollLastEntry();
10

11
NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);

1
transient volatile Node<K, V>[] table;        // 桶数组，volatile 保持可见性
2
private transient volatile Node<K, V>[] nextTable; // 扩容时的新表
3
private transient volatile int sizeCtl;       // 控制扩容标识
4
private transient volatile long baseCount;
5
private transient volatile CounterCell[] counterCells;

1
public class ArrayDeque<E> extends AbstractCollection<E>
2
        implements Deque<E>, Cloneable, Serializable {
3

4
    transient Object[] elements;
5
    transient int head;
6
    transient int tail;
7
    private static final int MIN_INITIAL_CAPACITY = 8;
8
}

1
// 当作栈
2
Deque<Integer> stack = new ArrayDeque<>();
3
stack.push(1);
4
stack.push(2);
5
stack.push(3);
6
while (!stack.isEmpty()) {
7
    System.out.println(stack.pop());  // 3 2 1
8
}
9

10
// 当作队列
11
Deque<Integer> queue = new ArrayDeque<>();
12
queue.offer(1);
13
queue.offer(2);
14
queue.offer(3);
15
while (!queue.isEmpty()) {
16
    System.out.println(queue.poll());  // 1 2 3
17
}

1
public class PriorityQueue<E> extends AbstractQueue<E>
2
        implements java.io.Serializable {
3

4
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
5
    transient Object[] queue;
6
    int size;
7
    private final Comparator<? super E> comparator;
8
}

1
// 上浮：插入时保证堆序
2
private void siftUpComparable(int k, E x) {
3
    Comparable<? super E> key = (Comparable<? super E>) x;
4
    while (k > 0) {
5
        int parent = (k - 1) >>> 1;
6
        Object e = queue[parent];
7
        if (key.compareTo((E) e) >= 0) break;
8
        queue[k] = e;
9
        k = parent;
10
    }
11
    queue[k] = key;
12
}
13

14
// 下沉：删除堆顶时维持堆序
15
private void siftDownComparable(int k, E x) {
16
    int half = size >>> 1;
17
    while (k < half) {
18
        int child = (k << 1) + 1;
19
        Object c = queue[child];
20
        int right = child + 1;
21
        if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
22
            c = queue[child = right];
23
        if (key.compareTo((E) c) <= 0) break;
24
        queue[k] = c;
25
        k = child;
26
    }
27
    queue[k] = key;
28
}