【集合】ArrayList 源码分析_arraylist排序sort源码

前言

Github：https://github.com/yihonglei/jdk-source-code-reading（java-collection）

主要分析 JDK8 版本源码。

一 ArrayList 概述

ArrayList 日常应用中随处可见，底层基于数组实现（数组数据结构），ArrayList 的特性：

• ArrayList 变长集合，底层基于 Object 数组（Object[]）实现；
• ArrayList 查找快，根据下标随机访问数组元素的时间复杂度是 O(1)；
• ArrayList 插入和删除慢，因为数组要保证内存的连续性，每次插入和删除需要搬迁元素；
• ArrayList 允许空值和重复值，因为是 Object 数组，元素是 Object 对象，一切都是对象，null 也是；
• ArrayList 有序集合，数组是连续内存空间，按照插入顺序连续存储；
• ArrayList 非线程安全，因为 add()，remove() 等方法，没有加锁机制，并发操作保证不了集合的原子性；

二 ArrayList 实例

从一个最简单的 Demo 开始。

package com.jpeony.collection.list;
 
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
 
/**
 * @author yihonglei
 */
public class ArrayListTest {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
 
        list.add(1);
        list.add(3);
        list.add(2);
 
        for (int i = 0; i < list.size(); i++) {
            System.out.println("element[" + i + "] = " + list.get(i));
        }
 
        System.out.println("=== sort ===");
        // ComparableTimSort.sort 逻辑
        list.sort(null);
        // TimSort.sort 逻辑
        // list.sort(new ListComparator());
 
        for (int i = 0; i < list.size(); i++) {
            System.out.println("element[" + i + "] = " + list.get(i));
        }
    }
 
    private static class ListComparator implements Comparator {
        @Override
        public int compare(Object o1, Object o2) {
            return Integer.parseInt(o1.toString()) - Integer.parseInt(o2.toString());
        }
    }
}

element[0] = 1
element[1] = 3
element[2] = 2
=== sort ===
element[0] = 1
element[1] = 2
element[2] = 3 

三 ArrayList 源码分析

重点分析下 add()、get()、remove() 和 sort() 方法。

ArrayList 成员变量

// 默认初始化数组容量 10
private static final int DEFAULT_CAPACITY = 10;
 
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
 
// 默认容量数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
// 存储元素的数组定义，是一个Object类型的数组，在Java里，一切都是对象，包括null
transient Object[] elementData;
 
// 数组元素的实际个数
private int size;
 
// 数组最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

默认构造器

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList 底层基于数组存储元素，是一个 Object 数组。默认容量 DEFAULT_CAPACITY 为 10，

这个 10 是在数组 add() 的时候判断体现的，并不是直接创建一个大小为10 的数组。

通过默认构造器，构建了一个默认大小为 10 的 Object 数组存储结构的 ArrayList。

ArrayList#add() 实现

add() 添加元素，先通过 ensureCapacityInternal() 容量保证和扩容操作，最后通过 elementData[size++] = e 往数组添加元素，

注意 size++ 是后加加。

public boolean add(E e) {
    // 容量判断和扩容，确保数组容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // size 默认为0，数组添加元素从下标从 0 位置开始，注意 size 是后++，添加完元素后 size 加 1
    // size 既代表下次即将添加元素的位置，又能表示数组的实际元素个数，一值两含义
    elementData[size++] = e;
    return true;
}

calculateCapacity() 容量计算、ensureExplicitCapacity() 数组扩容。 

private void ensureCapacityInternal(int minCapacity) {
    // calculateCapacity 容量计算，ensureExplicitCapacity 数组扩容
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果使用默认数组，即使用默认容量 DEFAULT_CAPACITY 为 10，
    // 如果超过了 10 个，即第 11 个，返回 minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否则，直接返回将要到达的容量 minCapacity
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
 
    // overflow-conscious code
    // 添加元素，超过了数组容量，将对数组进行扩容
    if (minCapacity - elementData.length > 0)
        // 扩容
        grow(minCapacity);
}

 grow() 扩容的实现，每次扩大为原长度的 1.5 倍，并不是百分百的 1.5 倍，1.5 只是个大约值。

private void grow(int minCapacity) {
    // overflow-conscious code
    // oldCapacity 旧数组容量
    int oldCapacity = elementData.length;
    // newCapacity 新数组容量
    // oldCapacity >> 1 右移动一位，即为oldCapacity的1/2，则newCapacity为原oldCapacity的1.5倍，即每次扩容为上一次的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判断新数组的容量是否小于最小容量，如果小于，就不需要进行扩大
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新数组容量大于数组设置的最大容量，进行最大容量限制，hugeCapacity返回最大容量限制
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 最大容量限制
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 将原旧数组复制到新数组，并重新赋值elementData，完成扩容操作
    elementData = Arrays.copyOf(elementData, newCapacity);
}

如果超过设置的最大值，将最大值设置为 Integer.MAX_VALUE，即 ArrayList 的最大长度就是 Integer 的上限值。 

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

ArrayList#get() 实现

常用的 get() 一般都是根据下标访问取值，get() 的过程比较简单，是数组根据下标随机访问元素的基本操作。

rangeCheck() 是检查下标是否越界，如果比 ArrayList 的容量还要大，抛了一个典型的异常错误 IndexOutOfBoundsException，

如果不越界，直接根据下标从数组查找元素返回即可。

public E get(int index) {
    rangeCheck(index);
 
    return elementData(index);
}

index >= size，为什么不是 index > size，因为 Java 里面数组的下标是从 0 开始的，size 是实际元素个数，是从 1 开始的，

比如数组 size 是 10 个元素，数组下标最大值也只是 9，如果用 10 来取值，已经超过了数组存储元素的下标位置，

所以，也要提前抛出错误。这也是 Java 给咱们实现了高级形态容器的好处，基于数组实现的底层细节我们都不需要关心了，

只需要使用即可，因为 Java 已经帮我们规避了常规异常。

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

数组为什么支持下标随机访问？

1）数组是线性表，只有前后两个方向；

2） 数组通过连续的内存空间存储相同类型的元素；

3）基于这两个条件，可以通过寻找算法，计算出访问位置的内存地址，可以直接定位元素，支持根据下标随机访问元素；

ArrayList#remove() 实现

remove(int index)  or remove(Object o) 可以根据下标移出元素，也可以根据元素内容移出元素，逻辑差不太多。

remove(int index) 

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);
    // 数组的最后一个元素置为null，主要是为了GC回收，Hotspot通过可达性分析算法确定对象
    // 是否可以回收，主要看GC Root有没有引用路径
    elementData[--size] = null; // clear to let GC do its work
 
    return oldValue;
}

 ArrayList#sort() 实现

sort() 为 List 的一个接口方法，default 默认实现，ArrayList 重写了 List 的 sort() 实现。

@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    // 数组排序
    Arrays.sort((E[]) elementData, 0, size, c);
    // ArrayList是非线程安全的，modCount每更新一次就会自增一次，
    // 通过预期值判断，避免并发操作集合后，排序不准，需要抛出并发更新的异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

public static <T> void sort(T[] a, int fromIndex, int toIndex,
                            Comparator<? super T> c) {
    // 如果没有实现比较方法
    if (c == null) {
        sort(a, fromIndex, toIndex);
    } else {
        // 下标合法性检测
        rangeCheck(a.length, fromIndex, toIndex);
        // 是否走老版本归并排序，1.6走老的，1.7和1.8默认不走，可以设置属性走老版本归并排序
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, fromIndex, toIndex, c);
        else
            // 自定义Comparator的排序算法
            TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
    }
}

1）legacyMergeSort() 老版本排序

老板本采用的是归并排序算法和插入排序的混合算法进行排序。

public static void sort(Object[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    // 默认是false，jdk1.7之后如果想走旧版本的归并排序，需要设置系统参数 java.util.Arrays.useLegacyMergeSort为true
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a, fromIndex, toIndex);
    else
        ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}

rangeCheck() 检查参数合法和是否越界。

private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
        throw new IllegalArgumentException(
                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    }
    if (fromIndex < 0) {
        throw new ArrayIndexOutOfBoundsException(fromIndex);
    }
    if (toIndex > arrayLength) {
        throw new ArrayIndexOutOfBoundsException(toIndex);
    }
}

legacyMergeSort() 旧版本归并排序。

private static void legacyMergeSort(Object[] a,
                                    int fromIndex, int toIndex) {
    // 复制一份数组
    Object[] aux = copyOfRange(a, fromIndex, toIndex);
    mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
}

mergeSort() 归并排序。

归并排序：归并排序是“分治”思想的典型场景，先将大数组有限次拆分为最小单元，通过递归进行比较合并，最后返回统一结果，

适用于数据规模较大，内存空间足够的情况，速度比较快，但是比较耗内存，以“空间换时间”的经典思想。

平均时间复杂度O(nlogn)，空间复杂度O(n)。

插入排序：排序元素在数组挨个比较，插入到合适位置，最后形成正序或倒序顺序，虽然不能减少元素移动次数，

但是能够减少比较次数，适用于小规模数据排序，如果数据规模比较大，性能上不去，但是小数据量，性能很好。

平均时间复杂度O(n^2)，空间复杂度O(1)。

// src  原数组
// dest 目标数组
// low  开始下标
// high 尾端下标
// off  偏移量 对数组指定位置进行排序需要用到这个
@SuppressWarnings({"unchecked", "rawtypes"})
private static void mergeSort(Object[] src,
                              Object[] dest,
                              int low,
                              int high,
                              int off) {
    // 数组区间长度
    int length = high - low;
 
    // Insertion sort on smallest arrays
    // 如果数组元素少于7个，采用插入排序进行排序，效率更高些
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i=low; i<high; i++)
            for (int j=i; j>low &&
                     ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                swap(dest, j, j-1);
        return;
    }
 
    // Recursively sort halves of dest into src
    // 递归排序，将desc的一半排序为src
    int destLow  = low;
    int destHigh = high;
    low  += off;
    high += off;
    int mid = (low + high) >>> 1;
    // 第一个优化：进行递归排序，将desc数组的一半，排序成src数组
    mergeSort(dest, src, low, mid, -off);
    mergeSort(dest, src, mid, high, -off);
 
    // If list is already sorted, just copy from src to dest.  This is an
    // optimization that results in faster sorts for nearly ordered lists.
    // 第二个优化：如果前半部分的最大值 小于 后半部分的最小值，直接将排序后的src复制到dest
    if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
        System.arraycopy(src, low, dest, destLow, length);
        return;
    }
 
    // Merge sorted halves (now in src) into dest
    // 合并排序后的数组到desc，这个desc就是排完序后的数组
    for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
        if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
            dest[i] = src[p++];
        else
            dest[i] = src[q++];
    }
}

/**
 * Swaps x[a] with x[b].
 */
private static void swap(Object[] x, int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
}

2）ComparableTimSort.sort()

没有实现 Comparator 接口，在 jdk1.7 和 1.8 已经摒弃了旧版本的归并排序和插入排序的混合算法，

而是只用了经过大量优化的归并排序算法版本，对归并排序排在已经反向排好序的输入时做了特别优化。

对已经正向排好序的输入减少回溯。对两种情况混合（一会升序，一会降序）的输入处理比较好，

传统的归并排序用的是递归实现的，而优化后则是按分小区排序，连续升或降的作为一个区，

这是基于现实中排序大部分情况下小区间是有序的，无需对其进行全部操作处理的，

每个小区间叫做 run，将多个 run 进行合并得到最后的 run，就是排序结果，速度会比传统递归快很多，

但是实现就稍微复杂些。

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
    assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
 
    int nRemaining  = hi - lo;
    if (nRemaining < 2)
        return;  // Arrays of size 0 and 1 are always sorted
 
    // If array is small, do a "mini-TimSort" with no merges
    // 数组个数小于32的时候，直接
    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi);
        binarySort(a, lo, hi, lo + initRunLen);
        return;
    }
 
    /**
     * March over the array once, left to right, finding natural runs,
     * extending short natural runs to minRun elements, and merging runs
     * to maintain stack invariant.
     */
    ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);
    do {
        // Identify next run
        int runLen = countRunAndMakeAscending(a, lo, hi);
 
        // If run is short, extend to min(minRun, nRemaining)
        // 如果run长度小于规定的minRun长度，先进行二分插入排序
        if (runLen < minRun) {
            int force = nRemaining <= minRun ? nRemaining : minRun;
            binarySort(a, lo, lo + force, lo + runLen);
            runLen = force;
        }
 
        // Push run onto pending-run stack, and maybe merge
        ts.pushRun(lo, runLen);
        // 进行归并
        ts.mergeCollapse();
 
        // Advance to find next run
        lo += runLen;
        nRemaining -= runLen;
    } while (nRemaining != 0);
 
    // Merge all remaining runs to complete sort
    assert lo == hi;
    // 归并所有的run
    ts.mergeForceCollapse();
    assert ts.stackSize == 1;
}

private static void binarySort(Object[] a, int lo, int hi, int start) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        Comparable pivot = (Comparable) a[start];
 
        // Set left (and right) to the index where a[start] (pivot) belongs
        int left = lo;
        int right = start;
        assert left <= right;
        /*
         * Invariants:
         *   pivot >= all in [lo, left).
         *   pivot <  all in [right, start).
         */
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (pivot.compareTo(a[mid]) < 0)
                right = mid;
            else
                left = mid + 1;
        }
        assert left == right;
 
        /*
         * The invariants still hold: pivot >= all in [lo, left) and
         * pivot < all in [left, start), so pivot belongs at left.  Note
         * that if there are elements equal to pivot, left points to the
         * first slot after them -- that's why this sort is stable.
         * Slide elements over to make room for pivot.
         */
        // 要移动的个数
        int n = start - left;  // The number of elements to move
        // Switch is just an optimization for arraycopy in default case
        // 移动的方法
        switch (n) {
            case 2:  a[left + 2] = a[left + 1];
            case 1:  a[left + 1] = a[left];
                     break;
            // native复制数组方法
            default: System.arraycopy(a, left, a, left + 1, n);
        }
        a[left] = pivot;
    }
}

ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0)

invoke 实现

sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen)

算法逻辑如下：

1）参数含义值 a 排序集合，lo = 0，hi = size 元素个数，work 比较策略，默认是 null，workBase 和 workLen 默认是0；

2）nRemaining 未比较长度剩余值，默认是数组长度，如果小于 2，表示只有一个元素，直接 return，不需要排序；

3）如果数组小于 32 个元素，找到连续升降的区间，进行二分插入排序；

4）如果大于等于 32 个元素，构建 TimSort 排序算法，拆分不同 run 区间进行拆分排序，然后将 多个 run 合并结果；

3）TimSort.sort

实现 Comparator 接口，使用自定义比较器的 TimSort，与 ComparableTimSort.sort() 实现算法逻辑一样，

只是实现了 Comparator 是策略模式，可以自己定义具体的比较策略。

四 总结

1、ArrayList 底层基于数组实现，查找快，插入和删除慢，集合是有序的，允许元素为空和重复；

2、ArrayList#sort() 老版本基于归并排序实现，使用插入排序优化，1.7 和 1.8 也是基于归并排序新版本，二分排序优化；

3、ArrayList 是非线程安全的，并发操作时需要注意线程安全问题；