Collections / Arrays 工具类源码

概述

Collections 和 Arrays 是 Java 集合框架中最核心的两个工具类，分别提供了对集合和数组的各种操作。

Collections 包含了排序、查找、同步包装、不可变包装、类型安全包装等静态工厂方法。Arrays 提供了数组排序、二分查找、复制、填充、asList、deepToString 等操作。

这两个类的大部分排序实现都委托给 TimSort（JDK 7+ 引入，结合归并排序和插入排序的稳定排序算法）和 DualPivotQuicksort（原始类型数组排序的高性能实现）。

本文基于 OpenJDK 21 源码，逐层深入到排序、查找、包装视图等核心实现。

本文基于 OpenJDK 21 源码分析，关键实现会对比 JDK 8 到 JDK 21 的版本差异。

---

核心源码解析

① Collections.sort(List) 的 TimSort

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

List.sort() 的具体实现：

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Arrays.sort(T[], Comparator) → 委托给 TimSort：

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        // 使用自然排序的 TimSort
        ComparableTimSort.sort(a);
    } else {
        // 使用自定义 Comparator 的 TimSort
        TimSort.sort(a, c);
    }
}

TimSort 的核心特性：

• 稳定排序：相等元素的相对顺序不变
• 归并+插入混合：小数组（< 32）使用二分插入排序
• 最优 O(n)：已排序或部分排序数组接近线性
• 最坏 O(n log n)

ComparableTimSort 的 countRunAndMakeAscending()：

private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
    assert lo < hi;
    int runHi = lo + 1;
    if (runHi == hi) return 1;

    // 找到最大升序或降序子序列
    if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // 降序
        while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
            runHi++;
        reverseRange(a, lo, runHi); // 反转成升序
    } else {                                              // 升序
        while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
            runHi++;
    }
    return runHi - lo;
}

• 提取自然 run（升序或降序子序列）
• 降序 run 直接反转
• 然后合并所有的 run

② Collections.binarySearch(List, key) 的二分查找

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
    if (c == null)
        return binarySearch((List<? extends Comparable<? super T>>) list, key);
    if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
        return indexedBinarySearch(list, key, c);     // 索引二分
    else
        return iteratorBinarySearch(list, key, c);     // 迭代器二分
}

索引二分：

private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
    int low = 0;
    int high = l.size() - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1; // 无符号右移防止溢出
        T midVal = l.get(mid);
        int cmp = c.compare(midVal, key);
        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1); // 没找到，返回插入点
}

• RandomAccess 接口标记 → 允许 O(1) 索引访问
• 非 RandomAccess 的链表 → 退化为迭代器二分（O(n)）

③ Collections.unmodifiableList(list) 的不可变视图

public static <T> List<T> unmodifiableList(List<? extends T> list) {
    return (list instanceof RandomAccess ?
            new UnmodifiableRandomAccessList<>(list) :
            new UnmodifiableList<>(list));
}

static class UnmodifiableList<E> extends UnmodifiableCollection<E> implements List<E> {
    final List<? extends E> list;

    public E get(int index) { return list.get(index); }

    public void add(int index, E element) { throw new UnsupportedOperationException(); }
    public E remove(int index) { throw new UnsupportedOperationException(); }
    public E set(int index, E element) { throw new UnsupportedOperationException(); }
    // 所有修改方法都抛 UnsupportedOperationException
}

• 视图模式：原列表变化后，不可变视图也会反映变化
• UnmodifiableList 不允许任何结构性修改
• UnmodifiableRandomAccessList 额外实现 RandomAccess 接口

④ Collections.synchronizedList(list) 的同步包装

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

static class SynchronizedCollection<E> implements Collection<E> {
    final Collection<E> c;      // 被包装集合
    final Object mutex;         // 同步锁

    SynchronizedCollection(Collection<E> c) {
        this.c = Objects.requireNonNull(c);
        mutex = this;           // 默认用自身作为锁
    }

    public int size() { synchronized (mutex) { return c.size(); } }
    public boolean add(E e) { synchronized (mutex) { return c.add(e); } }
}

注意事项：

• 迭代器仍需外部同步：甚至 SynchronizedList 的 iterator() 本身没有同步
• 推荐用法：synchronized (list) { Iterator i = list.iterator(); while(i.hasNext()) ... }
• mutex 默认是 this，也可以指定外部锁

⑤ Collections.singleton(T) 的单元素集合

public static <T> Set<T> singleton(T o) {
    return new SingletonSet<>(o);
}

private static class SingletonSet<E> extends AbstractSet<E> {
    private final E element;

    public int size() { return 1; }
    public boolean contains(Object o) { return eq(o, element); }
    public Iterator<E> iterator() { return SingletonIterator(element); }
}

• 固定大小 1，不可扩容
• 常用于返回只有一个元素的集合
• 内存占用极小

⑥ Collections.checkedList(list, Class) 的类型检查

public static <E> List<E> checkedList(List<E> list, Class<E> type) {
    return (list instanceof RandomAccess ?
            new CheckedRandomAccessList<>(list, type) :
            new CheckedList<>(list, type));
}

static class CheckedCollection<E> implements Collection<E> {
    final Collection<E> c;
    final Class<E> type;

    void typeCheck(Object o) {
        if (o != null && !type.isInstance(o))
            throw new ClassCastException(badElementMsg(o));
    }

    public boolean add(E e) {
        typeCheck(e);           // 运行时类型检查
        return c.add(e);
    }
}

• 通过 Class.isInstance() 在运行时检查元素类型
• 防止因泛型擦除导致的类型安全问题
• 性能有轻微开销

⑦ Arrays.sort(int[]) 的 DualPivotQuicksort

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, 0, a.length);
}

DualPivotQuicksort 根据数组长度选择不同策略：

static void sort(int[] a, int left, int right, int[] work, int workBase, int len) {
    if (right - left < QUICKSORT_THRESHOLD) {         // < 286
        sort(a, left, right, true);                     // 双轴快排
    } else {
        // 检查是否近乎有序
        int[] run = new int[MAX_RUN_COUNT + 1];
        int count = 0; run[0] = left;
        for (int k = left; k < right; run[count] = k) {
            while (k < right && a[k] <= a[k + 1]) k++;  // 升序 run
            while (k < right && a[k] >= a[k + 1]) k++;  // 降序 run
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);              // 乱序 → 快排
                return;
            }
        }
        // 近乎有序 → TimSort
        // ...
    }
}

DualPivotQuicksort 的三个阈值：

长度	算法
< 47	插入排序（近乎有序时 O(n)）
< 286	双轴快速排序（O(n log n)）
≥ 286	近乎有序 → TimSort / 乱序 → 双轴快排

⑧ Arrays.binarySearch(int[], key)

public static int binarySearch(int[] a, int key) {
    return binarySearch0(a, 0, a.length, key);
}

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1; // 无符号右移防溢出
        int midVal = a[mid];
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1); // 没找到插入点
}

⑨ Arrays.asList(T...) 的 ArrayList

@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable {

    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }

    public E get(int index) { return a[index]; }
    public E set(int index, E element) {
        E oldValue = a[index];
        a[index] = element;
        return oldValue;
    }
    // 没有 add() / remove() — 继承 AbstractList 抛 UnsupportedOperationException
}

注意：

• 返回的 ArrayList 是 Arrays 的内部类，不是 java.util.ArrayList
• 底层直接包装传入的数组，修改列表会反映到数组
• 没有 add() / remove() 方法，调用会抛 UnsupportedOperationException
• 不支持扩容

⑩ Arrays.deepToString(Object[]) 的递归

public static String deepToString(Object[] a) {
    if (a == null) return "null";
    int bufLen = 20 * a.length;
    if (a.length != 0 && bufLen <= 0)
        bufLen = Integer.MAX_VALUE;
    StringBuilder buf = new StringBuilder(bufLen);
    deepToString(a, buf, new HashSet<>()); // 传入 HashSet 检测循环
    return buf.toString();
}

private static void deepToString(Object[] a, StringBuilder buf, Set<Object[]> dejaVu) {
    if (a == null) {
        buf.append("null");
        return;
    }
    if (!dejaVu.add(a)) { // 循环引用检测
        buf.append("[...]");
        return;
    }
    buf.append('[');
    for (int i = 0; i < a.length; i++) {
        if (i != 0) buf.append(", ");
        Object element = a[i];
        if (element == null)
            buf.append("null");
        else {
            Class<?> eClass = element.getClass();
            if (eClass.isArray()) {
                if (eClass == int[].class)      buf.append(Arrays.toString((int[])element));
                else if (eClass == byte[].class) buf.append(Arrays.toString((byte[])element));
                // ... 所有原始类型数组
                else                              deepToString((Object[])element, buf, dejaVu);
            } else {
                buf.append(element.toString());
            }
        }
    }
    buf.append(']');
    dejaVu.remove(a);
}

• 通过 HashSet<Object[]> 检测循环引用（dejaVu）
• 不同类型的数组有不同的 toString() 处理
• 递归深度受限于 JVM 栈

---

总结

Collections 和 Arrays 提供了日常开发中最常用的工具操作：

• Collections：排序（TimSort）、二分查找、不可变视图、同步包装、类型安全包装、单元素集合
• Arrays：排序（DualPivotQuicksort + TimSort 混合策略）、二分查找、asList 固定视图、deepToString 递归

它们的核心设计理念是委托——将具体实现委托给专门的算法类（TimSort、DualPivotQuicksort），自身提供统一的静态接口。