基于ArrayList常用方法的源码全面解析
我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问题早已烂熟于心,前者基于数组实现,后者基于链表实现;前者随机方法速度快删除和插入指定位置速度慢,后者随机访问速度慢删除和插入指定位置速度快;两者都是线程不安全的;列表与数组之间的区别等等。
列表与数组之间很大的一个区别就是:数组在其初始化就需要给它确定大小不能动态扩容,而列表则可以动态扩容。ArrayList是基于数组实现的,那么它是如何实现的动态扩容呢?
对于ArrayList的初始化有三种方式:
对于第一种默认的构造方法,ArrayList并没有初始化容量大小,而是将列表的元素数据引用指向了一个空数组。
private transient Object[] elementData; private static final Object[] EMPTY_ELEMENTDATA = {};
//1.ArrayList默认构造方法 public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; }
与JDK1.6不同的是,JDK1.6即时是在调用默认的构造方法时,也会初始化容量大小,JDK1.7当然会带来一定的好处,如果初始化而不使用就白白浪费了存储空间,等到添加的时候再初始化容量大小即可。
与JDK1.6不同的是,JDK1.6即时是在调用默认的构造方法时,也会初始化容量大小,JDK1.7当然会带来一定的好处,如果初始化而不使用就白白浪费了存储空间,等到添加的时候再初始化容量大小即可。
//JDK1.6 ArrayList public ArrayList() { this(10); }
对于第二种构造方法,则直接创建一个指定大小的数组,将列表的元素数组引用指向它。
//2.ArrayList带有初始化大小的构造方法 public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; }
第三种构造方法,能将一个集合作为参数传递,但集合中的元素必须继承自ArrayList中的元素。
//3.可将一个集合作为ArrayList的参数构造成ArrayList public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); //将集合转换为数组 size = elementData.length; //集合中的元素大小 // c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug,参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
上面提到了一个bug,也就是说将一个集合转换为数组的时候可能错误地不会返回Object[],举例说明。
package com.algorithm.sort; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * bug编号:6260652。toArray有可能不会返回Object[] * Created by yulinfeng on 2017/6/26. */ public class Test { public static void main(String[] args) { correctly(); incorrectly(); } /** * 返回Object[] */ private static void correctly() { List<String> list = new ArrayList<String>(); list.add("test"); System.out.println(list.getClass()); Object[] objArray = list.toArray(); System.out.println(objArray.getClass()); } /** * 不返回Object[] */ private static void incorrectly() { List<String> list = Arrays.asList("test"); System.out.println(list.getClass()); Object[] objArray = list.toArray(); System.out.println(objArray.getClass()); } }
运行结果:
上面的这个例子就说明了toArray并不一定总是返回Object[],返回的Object[]时,Object元素就不能插入,故JDK在“6260652”中修复了这个bug。
接下来看元素插入以及删除等其它方法。
//ArrayList#add public boolean add(E e) { ensureCapacityInternal(size + 1); //确保容量是否充足 elementData[size++] = e; //将元素添加至数组 return true; }
//ArrayList#ensureCapacityInternal private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //如果此时还没有初始化列表容量大小,则对其初始化,默认容量为10 } ensureExplicitCapacity(minCapacity); //检查容量是否充足 }
//ArrayList#ensureEcplicitCapacity private void ensureExplicitCapacity(int minCapacity) { modCount++; //注意此变量 if (minCapacity - elementData.length > 0) grow(minCapacity); //容量不够则进行扩容 }
在ensureEcplicitCapacity方法中有一个modCount(modify count)变量进行了自增。
protected transient int modCount = 0;
这个变量不仅在add方法中会自增,只要是在增加或者删除等对ArrayList结构产生了变化都会记录加1,这样做的原因和多线程下Iterator迭代器遍历有关。在AbstractList$Itr中也有一个变量与之对应。
//AbstractList$Itr int expectedModCount = modCount;
在AbstractList$Itr#next中调用了checkForComodification方法。
//AbstractList$Itr#checkForComodification final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
如果当前运行环境是单线程,不论对列表进行何种操作何时增加、修改、删除等,excpectedModCount总是会等于modCount,但是如果当前运行环境是多线程,很有可能一个线程在迭代遍历,而另一个线程在对其进行新增或者修改等,JDK则不允许这么做,此时则会抛出ConcurrentModificationException异常,这就是modCount变量在此起的作用。
回到ArrayList#add方法,当列表容量不足时,此时会调用grow方法进行扩容。
//ArrayList#grow private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容策略为,每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10,则第一次扩容大小为10 / 2 = 5,第二次扩容大小为15 / 2 = 7。 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //扩容策略扩得太小 if (newCapacity - MAX_ARRAY_SIZE > 0) //扩容策略扩得太大,大于最大数组大小时,最多等于Integer.MAX_VALUE newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
ArrayList获取指定索引位置的元素get方法。
public E get(int index) { rangeCheck(index); //检查索引是否越界 return elementData(index); }
由于ArrayList是由基于数组实现,故此方法较为简单,判断是否越界,没有则根据数组下标来索引返回元素即可。remove方法删除指定位置的元素。
//ArrayList#remove public E remove(int index) { rangeCheck(index); //检查索引是否越界 modCount++; //记录modCount,上面已提及 E oldValue = elementData(index); //取出指定索引元素 int numMoved = size - index - 1; //移动的元素个数 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; //将最后一个数组元素置为null,方便GC return oldValue; }
代码比较简单,同样也体现了基于数组实习的ArrayList在删除指定元素时的效率问题。
以上这篇基于ArrayList常用方法的源码全面解析就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。