Github：https://github.com/yihonglei/jdk-source-code-reading（java-collection）
主要分析 JDK8 版本源码。
ArrayList日常应用中随处可见，底层基于数组实现（数组数据结构），ArrayList 的特性：
ArrayList 变长集合，底层基于 Object 数组（Object[]）实现；ArrayList 查找快，根据下标随机访问数组元素的时间复杂度是 O(1)；ArrayList 插入和删除慢，因为数组要保证内存的连续性，每次插入和删除需要搬迁元素；ArrayList 允许空值和重复值，因为是 Object 数组，元素是 Object 对象，一切都是对象，null 也是；ArrayList 有序集合，数组是连续内存空间，按照插入顺序连续存储；ArrayList 非线程安全，因为 add()，remove() 等方法，没有加锁机制，并发操作保证不了集合的原子性，非线程安全；从一个最简单的 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
重点分析下 add()、get()、remove() 和 sort() 方法。
ArrayList 底层基于数组存储元素，是一个 Object 数组。默认容量 DEFAULT_CAPACITY 为 10，
这个 10 是在数组 add() 的时候判断体现的，并不是直接创建一个大小为10 的数组。
通过默认构造器，构建了一个默认大小为10 的 Object 数组存储结构的 ArrayList。
add() 添加元素，先通过 ensureCapacityInternal() 容量保证和扩容操作，最后通过 elementData[size++] = e 往数组添加元素。
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; }常用的 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）基于这两个条件，可以通过寻找算法，计算出访问位置的内存地址，所以，可以直接定位元素，支持按下表随机访问；
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; }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); } }老板本采用的是归并排序算法和插入排序的混合算法进行排序。
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; }没有实现 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 合并结果；
实现 Comparator 接口，使用自定义比较器的 TimSort，与 ComparableTimSort.sort() 实现算法逻辑一样，
只是实现了 Comparator 是策略模式，可以自己定义具体的比较策略。
1、ArrayList 底层基于数组实现，查找快，插入和删除慢，集合是有序的，允许元素为空和重复；
2、ArrayList#sort() 老版本基于归并排序实现，使用插入排序优化，1.7和1.8也是基于归并排序新版本，二分排序优化；
3、ArrayList 是非线程安全的，并发操作时需要注意线程安全问题；
