【集合】ArrayList 源码分析

偏执的太偏执、 2022-12-11 15:13 310阅读 0赞

# 前言 #

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

主要分析 JDK8 版本源码。

# 一 ArrayList 概述 #

ArrayList 日常应用中随处可见，底层基于数组实现（[数组数据结构][Link 1]），**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 是非线程安全的，并发操作时需要注意线程安全问题；

[https_github.com_yihonglei_jdk-source-code-reading]: https://github.com/yihonglei/jdk-source-code-reading
[Link 1]: https://blog.csdn.net/yhl_jxy/article/details/51760123