首页 > 代码库 > ArrayList源码解析

ArrayList源码解析

ArrayList源码解析

ArrayList简介:

ArrayList 是list接口的一个常用实现类。它的对象可以认为是一维数组的“类版本”。我们很快就可以看到,ArrayList 对象可以看做是一维数组的改良版本。类似于数组,ArrayList 对象支持元素的随机访问;也就是说,只要给出元素的索引,任何元素的访问时间都是常数。但是同数组不同的是,ArrayList 对象的大小在程序执行的过程中可以自动进行调整,并且ArrayList对象具有在任何索引位置插入和删除对象的方法,而数组如果想要插入和删除对象,则必须要编写代码增加和减少储存空间。

ArrayList方法简介:

首先我们先来看一下ArrayList的所有公共方法。

注:下面方法除构造函数方法外,其他方法皆按照字母顺序排序。

技术分享
 1 1、public Arraylist()
 2 2、public ArrayList(int initalCapacity)
 3 3、public ArrayList(Collection<? extends E> c)
 4 4、public boolean add(E e)
 5 5、public void add(int index, E element)
 6 6、 public boolean addAll(int index, Collection<? extends E> c)
 7 7、public boolean addAll(Collection<? extends E> c)
 8 8、 public void clear()
 9 9、 public Object clone()
10 10、 public boolean contains(Object o)
11 11、public boolean containsAll(Collection<?> c)
12 12、public void ensureCapacity(int minCapacity)
13 13、public boolean equals(Object o)
14 14、 public void forEach(Consumer<? super E> action)
15 15、public E get(int index)
16 16、public int hashCode()
17 17、 public int indexOf(Object o)
18 18、public boolean isEmpty()
19 19、public Iterator<E> iterator()
20 20、public int lastIndexOf(Object o)
21 21、public ListIterator<E> listIterator()
22 22、public ListIterator<E> listIterator(int index)
23 23、public E remove(int index)
24 24、public boolean remove(Object o)
25 25、public boolean removeAll(Collection<?> c)
26 26、public boolean removeIf(Predicate<? super E> filter)
27 27、 public void replaceAll(UnaryOperator<E> operator)
28 28、public boolean retainAll(Collection<?> c)
29 29、public E set(int index, E element)
30 30、public int size()
31 31、public void sort(Comparator<? super E> c)
32 32、public Spliterator<E> spliterator()
33 33、public List<E> subList(int fromIndex, int toIndex)
34 34、public Object[] toArray()
35 35、public <T> T[] toArray(T[] a)
36 36、public String toString()
37 37、public void trimToSize()
View Code

ArrayList方法解析:

ArrayList类结构关系:

在具体分析Arrayl类的方法之前,我们先看一下ArrayList类的继承关系。
 
技术分享
从图中可以看出,ArrayList继承AbstractList类,并且实现了List、RandomAccess、Serializable接口。
其中RandomAccess接口为一个空接口,起到一个标识的作用,如果集合类是RandomAccess的实现,则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历,在效率上要差一些。反过来,如果List是Sequence List,则最好用迭代器来进行迭代。 其具体细节在我们在这里就不进行讨论了,感兴趣的同学可以自己去查一查。
Serializable是启用序列化功能的接口,这里也不进行讨论了。
AbstractList继承了AbstractCollection.两者都是抽象类,AbstractCollection提供了Collection接口的一些方法的默认实现,AbstractCollection提供了List接口
的默认实现(个别方法为抽象方法)。

ArrayList类的属性:

技术分享
 1 //默认容量的大小
 2 private static final int DEFAULT_CAPACITY = 10;
 3 
 4 //空数组常量
 5 private static final Object[] EMPTY_ELEMENTDATA =http://www.mamicode.com/ {};
 6 
 7 //默认的空数组常量
 8 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA =http://www.mamicode.com/ {};
 9 
10 //存放元素的数组,从这可以发现ArrayList的底层实现就是一个Object数组
11 transient Object[] elementData;
12 
13 //数组中包含的元素个数
14 private int size;
15 
16 //数组的最大上限
17 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
View Code

ArrayList的属性非常少,一共就只有这五个。其中:DEFAULT_CAPACITY 代表默认容量的大小,在后面我们可以看到,在像ArrayList对象第一次添
加元素的时候,会将ArrayList的容量设置为默认的容量。EMPTY_ELEMENTDATE和DEFAULTCAPACITY_EMPTY_ELEMENTDATA区别不大。这个在后面
讲构造器的时候会详细讲到。其中最重要的莫过于elementData了,ArrayList所有的方法都是建立在elementData之上。

ArrayList构造函数:

ArrayList一共有三个构造函数,分别为:

技术分享
 1 public ArrayList(int initialCapacity) {
 2         if (initialCapacity > 0) {
 3             this.elementData = http://www.mamicode.com/new Object[initialCapacity];
 4         } else if (initialCapacity == 0) {
 5             this.elementData =http://www.mamicode.com/ EMPTY_ELEMENTDATA;
 6         } else {
 7             throw new IllegalArgumentException("Illegal Capacity: "+
 8                                                initialCapacity);
 9         }
10     }
11     public ArrayList() {
12         this.elementData =http://www.mamicode.com/ DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
13     }
14     public ArrayList(Collection<? extends E> c) {
15         elementData =http://www.mamicode.com/ c.toArray();
16         if ((size = elementData.length) != 0) {
17             // c.toArray might (incorrectly) not return Object[] (see 6260652)
18             if (elementData.getClass() != Object[].class)
19                 elementData = http://www.mamicode.com/Arrays.copyOf(elementData, size, Object[].class);
20         } else {
21             // replace with empty array.
22             this.elementData =http://www.mamicode.com/ EMPTY_ELEMENTDATA;
23         }
24     }
View Code
从构造函数我们可以看出,elementDate默认是一个大小为0的的数组,即DEFAULTCAPACITY_EMPTY_ELEMENTDATA,而
当指定数组长度时,elementData的初始大小就变成了我们所指定的初始大小了。如果我们指定数组的默认长度为0时,
elementDate即为EMPTY_ELEMENTDATA,在这里我们还看不出两者的区别,在后面讲到add方法时,就可以看到两者的不同了。
ArrayList同样可以传入一个Collection,当Collection不为空时,复制该Collection。否则elementDate仍然为EMPTY_ELEMENTDATA。

ArrayList的公共方法:

ArrayList的添加方法:

ArrayList添加单个元素有两个方法,分别为:
技术分享
 1     public boolean add(E e) {
 2         ensureCapacityInternal(size + 1);  // Increments modCount!!
 3         elementData[size++] = e;
 4         return true;
 5     }
 6     public void add(int index, E element) {
 7         rangeCheckForAdd(index);
 8 
 9         ensureCapacityInternal(size + 1);  // Increments modCount!!
10         System.arraycopy(elementData, index, elementData, index + 1,
11                          size - index);
12         elementData[index] = element;
13         size++;
14     }
View Code

add(E e)方法是用来添加一个单个的元素,其调用了私有方法enesureCapacityInternal(size+1).

 1   private void ensureCapacityInternal(int minCapacity) {
 2         if (elementData =http://www.mamicode.com/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 3             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 4         }
 5 
 6         ensureExplicitCapacity(minCapacity);
 7     }
 8     private void ensureExplicitCapacity(int minCapacity) {
 9         modCount++;//
10         // overflow-conscious code
11         if (minCapacity - elementData.length > 0)
12             grow(minCapacity);
13     }
14  private void grow(int minCapacity) {
15         // overflow-conscious code
16         int oldCapacity = elementData.length;
17         int newCapacity = oldCapacity + (oldCapacity >> 1);
18         if (newCapacity - minCapacity < 0)
19             newCapacity = minCapacity;
20         if (newCapacity - MAX_ARRAY_SIZE > 0)
21             newCapacity = hugeCapacity(minCapacity);
22         // minCapacity is usually close to size, so this is a win:
23         elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity);
24     }
我们可以看到,在这个方法中,增加了一个判断,elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA,那么minCapacity=DEFAULT_CAPACITY,也就是等于10.这就区分出了前面所说的DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的区别。当elemetnDate=DEFAULT_CAPACITY时,第一次添加元素时,容量变为1,而当elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,第一次添加元素时,容量变为10.
同时,我们也可以看出ArrayList在面对容量不足时,每次扩容都是在原容量的基础上,增加0.5倍。
而add(int index,E e)就比较好理解了,先检查index,然后判断是否需要扩容,需要就扩容,然后将原来的elemetnDate从index起始到最后复制到index+1的位置上,然后在原index位置添加元素。

 ArrayList添加多个元素的方法一样有两个,分别为:

 1     public boolean addAll(Collection<? extends E> c) {
 2         Object[] a = c.toArray();
 3         int numNew = a.length;
 4         ensureCapacityInternal(size + numNew);  // Increments modCount
 5         System.arraycopy(a, 0, elementData, size, numNew);
 6         size += numNew;
 7         return numNew != 0;
 8     }
 9 
10  public boolean addAll(int index, Collection<? extends E> c) {
11         rangeCheckForAdd(index);
12 
13         Object[] a = c.toArray();
14         int numNew = a.length;
15         ensureCapacityInternal(size + numNew);  // Increments modCount
16 
17         int numMoved = size - index;
18         if (numMoved > 0)
19             System.arraycopy(elementData, index, elementData, index + numNew,
20                              numMoved);
21 
22         System.arraycopy(a, 0, elementData, index, numNew);
23         size += numNew;
24         return numNew != 0;
25     }

插入多个元素,与插入单个元素的逻辑是一样的,在这里就不再重复了。

ArrayList删除元素方法:

ArrayList删除元素的方法一共有五个,分别是

 1   public E remove(int index) {
 2         rangeCheck(index);
 3 
 4         modCount++;
 5         E oldValue =http://www.mamicode.com/ elementData(index);
 6 
 7         int numMoved = size - index - 1;
 8         if (numMoved > 0)
 9             System.arraycopy(elementData, index+1, elementData, index,
10                              numMoved);
11         elementData[--size] = null; // clear to let GC do its work
12 
13         return oldValue;
14     }

remove(int index)的处理逻辑:先检查index是否大于elementDate的size,如果大于的话,则抛出异常;然后获取elementDate[index],留在方法结束后返回;然后复制素组,从index+1开始,复制size-index-1个元素,复制到elementDate,从index开始;最后设置elementDate[--size]=null;

 

 1     public boolean remove(Object o) {
 2         if (o == null) {
 3             for (int index = 0; index < size; index++)
 4                 if (elementData[index] == null) {
 5                     fastRemove(index);
 6                     return true;
 7                 }
 8         } else {
 9             for (int index = 0; index < size; index++)
10                 if (o.equals(elementData[index])) {
11                     fastRemove(index);
12                     return true;
13                 }
14         }
15         return false;
16     }

remove(Object o)的逻辑:先判断Object 是否为null,如果为null,则遍历ArrayList,删除所有的null值,如果有值被删除,则返回true;如果Object不为null,同样遍历ArrayList,删除ArrayList中相同的元素,如果有元素被删除,则返回true.

而fastRemove(int index)的逻辑与remove(int index),完全一致,只是少了对index的验证。

1  public boolean removeAll(Collection<?> c) {
2         Objects.requireNonNull(c);
3         return batchRemove(c, false);
4     }
 1  private boolean batchRemove(Collection<?> c, boolean complement) {
 2         final Object[] elementData = http://www.mamicode.com/this.elementData;
 3         int r = 0, w = 0;
 4         boolean modified = false;
 5         try {
 6             for (; r < size; r++)
 7                 if (c.contains(elementData[r]) == complement)
 8                     elementData[w++] = elementData[r];
 9         } finally {
10             // Preserve behavioral compatibility with AbstractCollection,
11             // even if c.contains() throws.
12             if (r != size) {
13                 System.arraycopy(elementData, r,
14                                  elementData, w,
15                                  size - r);
16                 w += size - r;
17             }
18             if (w != size) {
19                 // clear to let GC do its work
20                 for (int i = w; i < size; i++)
21                     elementData[i] = null;
22                 modCount += size - w;
23                 size = w;
24                 modified = true;
25             }
26         }
27         return modified;
28     }

从上面的代码我们可以看出,remove(Collection<?> c)的逻辑:先判断c是否为null,如果为null,则抛出异常。然后遍历elementDate,如果c包含数组elementDate中的元素

,则将该元素添加一次替换原elementDate数组中,最后,将数组的其余位置设为null,如果新数组比原来数组中的元素少,则已经删除了元素,返回true.

 

除此之外,还有一个清空ArrayList的方法
1     public void clear() {
2         modCount++;
3 
4         // clear to let GC do its work
5         for (int i = 0; i < size; i++)
6             elementData[i] = null;
7 
8         size = 0;
9     }

clear()方法的逻辑:遍历,删除所有元素。

 

除此之外,还有一个retainAll(collenction<T> c)方法,该方法愿意是取得两个集合得交集,在这里也可以理解为删除集合中不与collection c 重复得元素。

 1 return batchRemove(c, true); 

可以看到,它得处理逻辑和removeAll是同样得逻辑,这里就不再重复了。

ArrayList修改元素的方法

在JDK1.8之前,修改元素只有一个方法,就是set(int index,Object c).

1  public E set(int index, E element) {
2         rangeCheck(index);
3 
4         E oldValue =http://www.mamicode.com/ elementData(index);
5         elementData[index] = element;
6         return oldValue;
7     }

逻辑很简单,就是先检查index,然后新元素替换旧元素,并返回旧元素。

在JDK1.8中,添加了一个新方法,批量修改replaceAll(UnaryOperator<E> operator):

 1 public void replaceAll(UnaryOperator<E> operator) {
 2         Objects.requireNonNull(operator);
 3         final int expectedModCount = modCount;
 4         final int size = this.size;
 5         for (int i=0; modCount == expectedModCount && i < size; i++) {
 6             elementData[i] = operator.apply((E) elementData[i]);
 7         }
 8         if (modCount != expectedModCount) {
 9             throw new ConcurrentModificationException();
10         }
11         modCount++;
12     }

 UnaryOperator<T> extends Function<T, T>,而Function<T,R>方法中有一个抽象方法,R apply<T,t>,方法的原意应该是将一个T转换成R.而这里使用,UnaryOperator,则只能将T转换成T。我们在使用ReplaceAll方法是,必须重写apply方法,作为转换规则。例如:

 1 public class ArrayListTest {
 2     public static void main(String[] args) {
 3         List<String> list = new ArrayList<String>();
 4         list.add("科比");
 5         list.add("詹姆斯");
 6         list.add("库里");
 7         list.replaceAll(new UnaryOperator<String>() {
 8             @Override
 9             public String apply(String t) {
10                 // TODO Auto-generated method stub
11                 return t+"牛逼";
12             }
13         });
14         System.out.println(list);
15     }
16 }
输出的结果为:
[科比牛逼, 詹姆斯牛逼, 库里牛逼]

ArrayList查找元素得方法:

   

1    public E get(int index) {
2         rangeCheck(index);
3 
4         return elementData(index);
5     }

get(int index)方法,通过元素的下标来获取元素。其原理就是获取数组的当前下表的元素。

 1     public int indexOf(Object o) {
 2         if (o == null) {
 3             for (int i = 0; i < size; i++)
 4                 if (elementData[i]==null)
 5                     return i;
 6         } else {
 7             for (int i = 0; i < size; i++)
 8                 if (o.equals(elementData[i]))
 9                     return i;
10         }
11         return -1;
12     }

 indextOf(Object o),查找ArrayList是否含有某元素,且返回该元素在集合中的第一个位置的下标。通过遍历元素,获取该集合所含有的第一个该元素的下标。如果不含有该元素,则返回-1.

 1     public int lastIndexOf(Object o) {
 2         if (o == null) {
 3             for (int i = size-1; i >= 0; i--)
 4                 if (elementData[i]==null)
 5                     return i;
 6         } else {
 7             for (int i = size-1; i >= 0; i--)
 8                 if (o.equals(elementData[i]))
 9                     return i;
10         }
11         return -1;
12     }

lastIndexOf(Object o),与indexOf方法想法,该方法查找该元素在集合中最后一个位置,并返回下标。其逻辑与indexOf基本一致,只不过是在遍历的时候选择从后往前遍历。

 1 public boolean isEmpty() { 2 return size == 0; 3 } 

isEmpth()方法用来查看集合是否为空集合。如果size=0,则为空集合,返回true。否则返回false。

  public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

 contains(Object o)查看集合中是否含有某元素。其调用indexOf(Object o),如果含有返回ture,否则返回false.

   public int size() {
        return size;
    }

 size()方法用来查看集合中含有多少个元素,返回元素个数。

ArrayList的一些其他常用方法:

 1    public Object clone() {
 2         try {
 3             ArrayList<?> v = (ArrayList<?>) super.clone();
 4             v.elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, size);
 5             v.modCount = 0;
 6             return v;
 7         } catch (CloneNotSupportedException e) {
 8             // this shouldn‘t happen, since we are Cloneable
 9             throw new InternalError(e);
10         }
11     }

clone()方法,用来复制集合并返回一个新的集合。而查看copyOf源码,发现最底层是使用native方法进行的复制。我无法确定其到底是深复制还是浅复制。

  private static native Object newArray(Class<?> componentType, int length) throws NegativeArraySizeException; 

所以我写了一个简单的测试代码,代码如下:

 1 public class ArrayListTest{
 2     public static void main(String[] args) {
 3         ArrayList<User> list = new ArrayList<User>();
 4         list.add(new User("科比"));
 5         list.add(new User("詹姆斯"));
 6         list.add(new User("库里"));
 7         ArrayList list1= (ArrayList) list.clone();
 8         User user = list.get(1);
 9         user.name = "麦迪";
10         System.out.println(list1);
11     }
12 }
13 
14 class User{
15      String name;
16     public User(String name){
17         this.name = name;
18     }
19     @Override
20     public String toString() {
21         return name;
22     }
23 }

打印结果为:

[科比, 麦迪, 库里]

  说明ArrayList的复制为潜复制,因为其数组中的元素,并没有进行值复制,而是直接复制了元素的引用。

 

在Java8中,ArrayList添加了一种新的遍历方法。foreach+lambda表达式遍历。代码如下:

1 public class ArrayListTest{
2     public static void main(String[] args) {
3         ArrayList<String> list = new ArrayList<String>();
4         list.add("科比");
5         list.add("詹姆斯");
6         list.add("库里");
7         list.forEach((s)->System.out.println(s));
8     }
9 }

因为不懂lambda表达式的实现原理,foreach的源码实在看不懂。等以后研究了lambda表达式的实现原理,在回来研究下foreach方法。

 在Java8中,ArrayList同样新添加了一种排序方法。sort(Comparator<? super E> c).源码如下:

 1  @Override
 2     @SuppressWarnings("unchecked")
 3     public void sort(Comparator<? super E> c) {
 4         final int expectedModCount = modCount;
 5         Arrays.sort((E[]) elementData, 0, size, c);
 6         if (modCount != expectedModCount) {
 7             throw new ConcurrentModificationException();
 8         }
 9         modCount++;
10     }

发现,ArrayList的排序,其实就是调用了数组的排序。我们继续往下看,数组是如何排序的:

 1     public static <T> void sort(T[] a, int fromIndex, int toIndex,
 2                                 Comparator<? super T> c) {
 3         if (c == null) {
 4             sort(a, fromIndex, toIndex);
 5         } else {
 6             rangeCheck(a.length, fromIndex, toIndex);
 7             if (LegacyMergeSort.userRequested)
 8                 legacyMergeSort(a, fromIndex, toIndex, c);
 9             else
10                 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
11         }
12     }
1     public static void sort(Object[] a, int fromIndex, int toIndex) {
2         rangeCheck(a.length, fromIndex, toIndex);
3         if (LegacyMergeSort.userRequested)
4             legacyMergeSort(a, fromIndex, toIndex);
5         else
6             ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
7     }
1  private static void legacyMergeSort(Object[] a,
2                                         int fromIndex, int toIndex) {
3         Object[] aux = copyOfRange(a, fromIndex, toIndex);
4         mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
5     }
 1 @SuppressWarnings({"unchecked", "rawtypes"})
 2     private static void mergeSort(Object[] src,
 3                                   Object[] dest,
 4                                   int low,
 5                                   int high,
 6                                   int off) {
 7         int length = high - low;
 8 
 9         // Insertion sort on smallest arrays
10         if (length < INSERTIONSORT_THRESHOLD) {
11             for (int i=low; i<high; i++)
12                 for (int j=i; j>low &&
13                          ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
14                     swap(dest, j, j-1);
15             return;
16         }
17 
18         // Recursively sort halves of dest into src
19         int destLow  = low;
20         int destHigh = high;
21         low  += off;
22         high += off;
23         int mid = (low + high) >>> 1;
24         mergeSort(dest, src, low, mid, -off);
25         mergeSort(dest, src, mid, high, -off);
26 
27         // If list is already sorted, just copy from src to dest.  This is an
28         // optimization that results in faster sorts for nearly ordered lists.
29         if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
30             System.arraycopy(src, low, dest, destLow, length);
31             return;
32         }
33 
34         // Merge sorted halves (now in src) into dest
35         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
36             if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
37                 dest[i] = src[p++];
38             else
39                 dest[i] = src[q++];
40         }
41     }
1    /** To be removed in a future release. */
2     private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
3                                             Comparator<? super T> c) {
4         T[] aux = copyOfRange(a, fromIndex, toIndex);
5         if (c==null)
6             mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
7         else
8             mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
9     }
 1    @SuppressWarnings({"rawtypes", "unchecked"})
 2     private static void mergeSort(Object[] src,
 3                                   Object[] dest,
 4                                   int low, int high, int off,
 5                                   Comparator c) {
 6         int length = high - low;
 7 
 8         // Insertion sort on smallest arrays
 9         if (length < INSERTIONSORT_THRESHOLD) {
10             for (int i=low; i<high; i++)
11                 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
12                     swap(dest, j, j-1);
13             return;
14         }
15 
16         // Recursively sort halves of dest into src
17         int destLow  = low;
18         int destHigh = high;
19         low  += off;
20         high += off;
21         int mid = (low + high) >>> 1;
22         mergeSort(dest, src, low, mid, -off, c);
23         mergeSort(dest, src, mid, high, -off, c);
24 
25         // If list is already sorted, just copy from src to dest.  This is an
26         // optimization that results in faster sorts for nearly ordered lists.
27         if (c.compare(src[mid-1], src[mid]) <= 0) {
28            System.arraycopy(src, low, dest, destLow, length);
29            return;
30         }
31 
32         // Merge sorted halves (now in src) into dest
33         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
34             if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
35                 dest[i] = src[p++];
36             else
37                 dest[i] = src[q++];
38         }
39     }

可以看出,当比较器为空时,调用了mergeSort(Object[] src,Object[] dest,int low, int high, int off方法,不为空时,调用了mergeSort(Object[] src,Object[] dest,int low, int high, int off,Comparator c方法,两个方法基本一模一样,唯一的区别就是在有默认比较器的时候,两个元素的比较实用默认比较器的比较方法来比较。

仔细看两个方法,可以看出,ArrayList.sort方法 时间上是使用了一种优化过后的递归排序,在数组长度小于7的时候使用直接插入排序。数组长度大于7的时候,使用归并排序,直至子数组的长度小于7.

归并排序详见我的另一篇随笔经典排序算法--归并排序。

 

写在最后:
  此篇随笔仅用来记录我的学习内容,如有错误,欢迎指正。谢谢!!!

 

ArrayList源码解析