ArrayList源码一览

ArrayList(线程不安全)

ArrayList是一个其容量能够动态增长的动态数组

继承关系

构造方法

是符合collection父接口的规范的

（福利推荐：阿里云、腾讯云、华为云服务器最新限时优惠活动，云服务器1核2G仅88元/年、2核4G仅698元/3年，点击这里立即抢购>>>）

//传0则设置为默认容量 public ArrayList(int initialCapacity) {         if (initialCapacity > 0) {             this.elementData = new Object[initialCapacity];         } else if (initialCapacity == 0) {             this.elementData = EMPTY_ELEMENTDATA;         } else {             throw new IllegalArgumentException("Illegal Capacity: "+                                                initialCapacity);         }     }  //把collection中的元素取出来,再放在一个数组中 public ArrayList(Collection<? extends E> c) {         elementData = c.toArray();//这个地方说明引用不能为空,否则会出nullpointer异常         if ((size = elementData.length) != 0) {             // c.toArray might (incorrectly) not return Object[] (see 6260652)             if (elementData.getClass() != Object[].class)                 elementData = Arrays.copyOf(elementData, size, Object[].class);         } else {             // replace with empty array.             this.elementData = EMPTY_ELEMENTDATA;         }     } //ArrayList的toarray,因为底层是用数组存的,所以就是把数组复制一下  public Object[] toArray() {         return Arrays.copyOf(elementData, size);     } public static <T> T[] copyOf(T[] original, int newLength) {         return (T[]) copyOf(original, newLength, original.getClass());     }//这里T其实就是object,所以上面需要做一个if判断,其他集合最后可能不是object

Fail-Fast

重要方法

add

在某个索引处添加元素,或者添加集合,删除元素,都是直接通过数组的复制(System.arrayCopy)来完成而不是元素的移动,可以根据情况决定调用次数

public static native void arraycopy(Object src,  int  srcPos,                                  Object dest, int destPos,                                  int length);

//在传入index参数的时候,都会对其进行检查  private void rangeCheck(int index)  //在调用add在某个index处插入的方法时采用这个进行检查 private void rangeCheckForAdd(int index) {         if (index > size || index < 0)             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  private void add(E e, Object[] elementData, int s) {         if (s == elementData.length)             elementData = grow();         elementData[s] = e;         size = s + 1;     }     }

search

//从前往后找 public int indexOf(Object o) {         if (o == null) {             for (int i = 0; i < size; i++)                 if (elementData[i]==null)                     return i;         } else {             for (int i = 0; i < size; i++)                 if (o.equals(elementData[i]))                     return i;         }         return -1;     } //从后往前找     public int lastIndexOf(Object o) {         if (o == null) {             for (int i = size-1; i >= 0; i--)                 if (elementData[i]==null)                     return i;         } else {             for (int i = size-1; i >= 0; i--)                 if (o.equals(elementData[i]))                     return i;         }         return -1;     }

set

//修改该位置的值,返回原来该位置的值 public E set(int index, E element) {         rangeCheck(index);         E oldValue = elementData(index);         elementData[index] = element;         return oldValue;     }

Sort方法

根据由指定Comparator引起的顺序对该列表进行排序。
使用指定的比较器，此列表中的所有元素必须可以相互比较
如果指定的比较器为null则此列表中的所有元素都必须实现Comparable接口，并且应使用元素的自然顺序。
该列表必须是可修改的，但无需调整大小。

public void sort(Comparator<? super E> c) {         final int expectedModCount = modCount;         Arrays.sort((E[]) elementData, 0, size, c);         if (modCount != expectedModCount) {             throw new ConcurrentModificationException();         }         modCount++;     } }

这里的核心方法其实是Arrays.sort()

public static <T> void sort(T[] a, int fromIndex, int toIndex,                                 Comparator<? super T> c) {         if (c == null) {         //根据其对象的自然顺序，将指定对象数组的指定范围按升序排序。 要排序的范围从索引fromIndex （包括在内）到索引toIndex （不包括在内）。         // （如果fromIndex==toIndex ， fromIndex==toIndex排序的范围为空。）此范围中的所有元素必须实现Comparable接口             sort(a, fromIndex, toIndex);         } else {             rangeCheck(a.length, fromIndex, toIndex);             if (LegacyMergeSort.userRequested)                 legacyMergeSort(a, fromIndex, toIndex, c);//将被遗弃             else                 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);         }     }

这里主要是sort()与TimSort.sort()这两个核心方法,让我们再看一看他们的实现

• sort()

//ComparableTimSort 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         if (nRemaining < MIN_MERGE) {             int initRunLen = countRunAndMakeAscending(a, lo, hi);             binarySort(a, lo, hi, lo + initRunLen);             return;         }

-TimSort.sort()

//TimSort static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,                          T[] work, int workBase, int workLen) {         assert c != null && 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         if (nRemaining < MIN_MERGE) {             int initRunLen = countRunAndMakeAscending(a, lo, hi, c);             binarySort(a, lo, hi, lo + initRunLen, c);             return;         }

发现没有,这两个方法的实现几乎一模一样,再看一下,不仅如此
ComparableTimSort与TimSort这两个类也几乎一模一样.
这是源码给的注释

This is a near duplicate of TimSort, modified for use with arrays of objects  that implement Comparable, instead of using explicit comparators.

最后其实都是调用了binarySort(a, lo, hi, lo + initRunLen, c)进行排序
这里贴出源码

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;                 default: System.arraycopy(a, left, a, left + 1, n);             }             a[left] = pivot;         }     }

将里面的元素转换成数组

//实际上经过一些预处理之后都会调用 System.arraycopy方法; public Object[] toArray() {         return Arrays.copyOf(elementData, size);     } public <T> T[] toArray(T[] a) {         if (a.length < size)             // Make a new array of a's runtime type, but my contents:             return (T[]) Arrays.copyOf(elementData, size, a.getClass());         System.arraycopy(elementData, 0, a, 0, size);         if (a.length > size)             a[size] = null;         return a;     }

扩容

在add元素的时候

1. 确保最小容量为size+1(所含元素的个数),ensureCapacityInternal(size+1)
2. 计算出最小容量calculateCapacity(elementData, minCapacity),如果比默认的小就返回默认的,比默认的大,就返回自己
3. ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)),判断当前数组长度与所需的最小容量
4. 如果所需最小容量>当前数组长度,调用grow进行扩容
5. 一般而言根据newCapacity = oldCapacity + (oldCapacity >> 1);进行扩容
6. 如果这样之后数组长度依然不够,则直接newCapacity = minCapacity;
7. 如果超过了定义的最大数组长度调用 newCapacity = hugeCapacity(minCapacity);
8. 最后进行扩容(实际上就是数组的复制)

 private void grow(int minCapacity) {         // overflow-conscious code         int oldCapacity = elementData.length;         int newCapacity = oldCapacity + (oldCapacity >> 1);         if (newCapacity - minCapacity < 0)             newCapacity = minCapacity;         if (newCapacity - MAX_ARRAY_SIZE > 0)             newCapacity = hugeCapacity(minCapacity);         // minCapacity is usually close to size, so this is a win:         elementData = Arrays.copyOf(elementData, newCapacity);     } private static int hugeCapacity(int minCapacity) {         if (minCapacity < 0) // overflow             throw new OutOfMemoryError();         return (minCapacity > MAX_ARRAY_SIZE) ?             Integer.MAX_VALUE :             MAX_ARRAY_SIZE;     }

内部类

1. private class Itr implements Iterator<E> 2. private class ListItr extends Itr implements ListIterator<E> 3. private class SubList extends AbstractList<E> implements RandomAccess      对外提供subList(int fromIndex, int toIndex)方法

Itr

An optimized version of AbstractList.Itr

主要作用就是返回一个他的实例作为迭代器

public Iterator<E> iterator() {         return new Itr();     }

ListItr

//这个方法事实上还是调用的下面这个方法  public ListIterator<E> listIterator() {         return new ListItr(0);     } public ListIterator<E> listIterator(int index) {         if (index < 0 || index > size)             throw new IndexOutOfBoundsException("Index: "+index);         return new ListItr(index);     }

SubList

被用于求子列表的方法

//这个方法ArrayList与SubList均实现了,一模一样 public List<E> subList(int fromIndex, int toIndex) {         subListRangeCheck(fromIndex, toIndex, size);         return new SubList(this, 0, fromIndex, toIndex);     }

重要属性

 /**   *默认初始容量为十.   */ private static final int DEFAULT_CAPACITY = 10; /**  * Shared empty array instance used for empty instances.  */ //这两个属性,只是为了初始化不报空指针异常 private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList中含有元素的数量 private int size; //针对数组而言,指数组的长度 int length; //最大数组位数要比最大整数小8 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //用这个数组来存储集合中的元素 transient Object[] elementData;

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)