本文将以以下几个问题来探讨ArrayList的源码实现
ArrayList成员属性、构造方法。
ArrayList的大小是如何自动增加的?
add/set方法。
remove方法。
Iterator和ListIterator接口。
子集操作。
如何复制某个ArrayList到另一个ArrayList中去?写出你的代码?
1、ArrayList成员属性、构造方法
private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size;
从这段定义中可以看出,ArrayList维护了两个数组DEFAULT_CAPACITY和elementData。DEFAULT_CAPACITY是一个空数组,当创建一个空的ArrayList的时候就会使用DEFAULT_CAPACITY,这个时候elementData==DEFAULT_CAPACITY,当在容器中添加一个元素以后,则会使用elementData来存储数据。
这里值得讨论的是DEFAULT_CAPACITY常量,他代表的含义是一个默认数组大小,当我们创建的容器没用指定容量大小时,就会默认使用这个常量作为数组大小。因此当我们创建一个ArrayList实例的时候,最好考虑一下业务场景,如果我们将频繁的存储大量的元素,那么最好在创建的时候指定一个合理的size。所谓动态扩容,就是当数组中存储的元素达到容量上限以后,ArrayList会创建一个新的数组,新数组的大小为当前数组大小的1.5倍。随后将数组元素拷贝到新数组,如果这个动作频繁执行的话,会增大性能开销。
public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; } public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
这三个方法都是ArrayList的构造方法,从前两个方法中可以看出初始化ArrayList的时候是如何指定容器初始大小的,这里也无需多言了。那么我们再看看,当容量达到上限的时候,是如何动态扩充数组大小的呢。
2、ArrayList的大小是如何自动增加的?
public boolean add(E e) { // 每次添加元素之前先动态调整数组大小,避免溢出 ensureCapacityInternal(size + 1); // 为什么ArrayList的元素都是顺序存放的?这就是原因,每次都会把最新添加的元素放到数组末尾。 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { // 如果当前容器为空,那么就先初始化数组,数组大小不能小于DEFAULT_CAPACITY if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 容器会在什么时候扩容? 就是他了! 如果当前元素数量达到了容器的上限,那么就扩充数组 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // oldCapacity为当前容器大小 int oldCapacity = elementData.length; // oldCapacity >> 1和oldCapacity / 2是等效的,因此newCapacity为原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 因为第一次容器有可能为空,elementData.length==0,newCapacity会小于minCapacity if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 当然newCapacity也不能大于MAX_ARRAY_SIZE,因为数组能分配的最大空间就是Integer.MAX_VALUE if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 当确定好数组大小后,就可以进行数组拷贝,Arrays.copyOf的底层是一个native方法,后续有机会会讲到他的实现。 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; }
add/set方法
1.add方法:
public boolean add(E e) { // 检查扩容 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); //将index后面的元素后移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }
这里给出了四种add方法,add(E e)添加到数组末尾,add(int index, E element)添加到指定位置。添加元素的时候,首先都要检查扩容,而add(int index, E element)方法中多一步操作,就是将指定位置以后的所有元素向后移动一位,留出当前位置用来存放添加的元素。后面两种addAll方法原理和前两种一样,无非他是添加一个集合元素的区别。
2.set方法:
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
set和add的区别就是,add是添加一个元素,而set是替换元素,size不变。
remove方法:
1.remove单个元素:
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) // 直接进行数组拷贝操作,把index后的所有元素向前移动一位。 System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // 把元素设空,等待垃圾回收 return oldValue; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } // 之所以叫做快速删除,是因为他被设置为一个私有方法,只能在内部调用,删除元素的时候,省去了数组越界的判断。也不返回被删除的元素,直接进行数组拷贝操作。 private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; }
2.删除集合元素
removeAll和remove方法思想也是类似的,但是这里有个细节我认为作者处理的非常妙,有必要拿出来品味一下。那么妙在哪里呢?原来这里有两个方法removeAll和retainAll他们正好是互斥的两个操作,但是底层都调用了同一个方法来实现,请看!
// 删除包含集合C的元素 public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } // 除了包含集合C的元素外,一律被删除。也就是说,最后只剩下c中的元素。 public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) // 我认为这里有两点值得我们学习 // 第一,作者巧妙的提取了逻辑上的最大公约数,仅通过一行逻辑判断就实现了两个互斥的效果。 // 第二,作者的所用操作都集中于elementData一个数组上,避免了资源的浪费。 if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // 理论上r==size 只有当出现异常情况的时候,才会出现r!=size,一旦出现了异常, // 那么务必要将之前被修改过的数组再还原回来。 if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // 被删除部分数组后,剩余的所有元素被移到了0-w之间的位置,w位置以后的元素都被置空回收。 for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }
Iterator和ListIterator接口
1.Itr
Itr实现的是Iterator接口,拥有对元素向后遍历的能力.
int cursor; // 指向下一个返回的元素 int lastRet = -1; // 指向在遍历过程中,最后返回的那个元素。 如果没有为-1。 public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); // 指向下一个元素 cursor = i + 1; // 返回当前元素,并把lastRet指向当前这个元素 return (E) elementData[lastRet = i]; } // 此处有坑,调用此方法前,必须调用next方法,从lastRet可以看出,如果当前没有调用next,那么lastRet==-1 public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }
2.ListItr
ListItr不但继承了Itr类,也实现了ListIterator接口,因此他拥有双向遍历的能力。这里着重介绍一下向前遍历的原理。
public boolean hasPrevious() { return cursor != 0; } public int previousIndex() { // 通过cursor-1,将指针向前移位。 return cursor - 1; } public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; }
子集操作
public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); }
这里指的子集,就是指定list的起始位置和结束位置,获取这段范围内的集合元素。那么这有什么作用呢?当单独获取了这段子集以后,就可以独立的对待他,他的起始元素将从0开始。那么这是怎么实现的呢?原来他是通过维护一个SubList内部类,每次读取元素的时候,配合一个offset偏移量,精确的找到elementData数组中对应位置的元素了。由于代码量过多,我这里就象征性的展示其中的一个get方法。
public E get(int index) { rangeCheck(index); checkForComodification(); // 子集中的位置+偏移量==实际数组中的位置 return ArrayList.this.elementData(offset + index); }
如何复制某个ArrayList到另一个ArrayList中去?写出你的代码?
1.clone
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }
2.之前介绍过的构造方法。
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
两者本质都是调用Arrays.copyOf,而Arrays.copyOf是调用System.arrayscopy
public static <T> T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
总结:
以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组,因此最好能给出数组大小的与估值。默认第一次插入元素是创建大小为10的数组。
按数组下标访问元素-get(i)/set(i,e)的性能很高,这是数组的基本优势。直接在数组末尾加入元素-add(e)的性能也很高,但如果按下标插入,删除元素–add(i,e),remove(i),remove(e)则要用System.arraycopy()来移动受影响的元素,性能就变差了,这是基本劣势。
与Vector的区别
1、ArrayList是非线程安全,而Vector是线程安全的,在源码的表示上Vector加上了关键字synchronized。
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } // ArrayList的add方法 public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }
2、 ArrayList和Vector都具有动态扩容的特性,唯一的区别是,ArrayList扩容后是原来的1.5倍。Vector中有一个capacityIncrement变量,每次扩容都在原来大小基础上增加capacityIncrement。如果capacityIncrement==0,那么就在原大小基础上再扩充一倍。
3、 Vector中有一个方法setSize(int newSize),而ArrayList并没有,我觉得这个方法有点鸡肋。setSize允许用户主动设置容器大小,如果newSize小于当前size,那么elementData数组中只会保留newSize个元素,多出来的会设为null。如果newSize大于当前size,那么就扩容到newSize大小,数组中多出来的部分设为null,以后添加元素的时候,之前多出来的部分就会以null的形式存在,直接试验一下吧。
Vector<Integer> v2 = new Vector<Integer>(); v2.add(1); v2.setSize(3); v2.add(3); System.out.println(v2.size()); setSize之前: [1] setSize之后: [1, null, null] 当我再次添加一个元素后: [1, null, null, 3] 所以我觉得这个方法并没有太大实用意义。而且会是用户困惑,出现一些不必要的错误。 原文链接:https://blog.csdn.net/qq_33850908/article/details/79481787