ArrayList源码详解
程序员文章站
2022-04-18 19:07:27
ArrayList是一个容量能够动态增涨的数组,它是java集合框架中一个重要的类,继承抽象类AbstractList,实现了List接口。 实现了RandomAccess接口,该接口为标记接口,即提供了随机访问功能。 实现了Cloneable接口,可以调用Object的clone方法,返回对象的浅 ......
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList是一个容量能够动态增涨的数组,它是java集合框架中一个重要的类,继承抽象类AbstractList,实现了List接口。
实现了RandomAccess接口,该接口为标记接口,即提供了随机访问功能。
实现了Cloneable接口,可以调用Object的clone方法,返回对象的浅拷贝。
实现了java.io.Serializable接口,可以进行序列化功能。
-
ArrayList的属性
private static final int DEFAULT_CAPACITY = 10; //默认大小 private static final Object[] EMPTY_ELEMENTDATA = {}; //空的数组 private transient Object[] elementData; //存放ArrayList内元素的数组,定义了transient在实现Serializable序列化时,不会被串行化 private int size; //ArrayList的大小,成员变量,系统默认初始化0, 存在堆内存中,实际为ArrayList存放元素的个数
-
ArrayList的构造方法
public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; //初始化一个initialCapacity大小的数组 } public ArrayList() { super(); //ArrayList(10) jdk1.6该构造方法的实现,默认就创建10个大小的数组 this.elementData = EMPTY_ELEMENTDATA; //将elementData的引用指向定义的空数组(本文基于jdk1.7) } public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; if (elementData.getClass() != Object[].class) //返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[] elementData = Arrays.copyOf(elementData, size, Object[].class); }
ArrayList的方法
add方法
//直接添加元素,添加至数组末尾 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; //把元素追加到数组最后一个,size+1 return true; } //通过下标添加元素,假如当前数组大小为10,数组里有5个元素,下标传参只能<=5, //index=5 则元素直接添加至末尾 //index<5 index原位置元素及后续所有元素都往后移一个单位,新元素插入原index元素位置 //eg: 此时有arraylist有[1,2,3,4,5,6,7,8]size:8,我想在索引为5的时候插入1个数字1 //add(5,1) ,arrayList最后是[1,2,3,4,5,1,6,7,8] public void add(int index, E element) { rangeCheckForAdd(index); //检查数组下标越界 ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { //假如elementDate是个空的数组,即没有容量大小 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //比较大小,返回大的那个数值,作为初始化数组的大小 } ensureExplicitCapacity(minCapacity); //检查容量是否够,不够就扩容 } private void ensureExplicitCapacity(int minCapacity) { modCount++; ////AbstractList里所定义,假如使用迭代器将会用到 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //假设当前的ArrayList大小为12,即oldCapacity大小为12 //12二进制为1100,右移一个单位,即0110,十进制就是6,newCapacity即为18 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //MAX_ARRAY_SIZE=Integer.MAX_VALUE-8 Integer.MAX_VALUE = 2147483647 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); //创建一个原来大小1.5倍的数组,将原数组数据复制过去 } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //小于0则报内存溢出 //当天arrayList大小假如大于定义的MAX_ARRAY_SIZE大小,则返回Integer的最大值 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } private void rangeCheckForAdd(int index) { //检查数组下标是否越界 if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
关于方法:扩容方法grow()里Arrays.copyOf(elementData, newCapacity),就是根据class的类型来决定是new 还是反射去构造一个泛型数组,同时利用System.arraycopy函数,批量赋值元素至新数组中。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { 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; }
remove方法
public E remove(int index) { rangeCheck(index); //检查数组下标越界 modCount++; E oldValue = elementData(index); //读出要删除的值 //eg:假设当前数组值为{1,2,3,4,5,6,7,8},size为8,要删除index为5的值,在数组里是6 int numMoved = size - index - 1; //numMoved = 8 - 5 -1 = 2 if (numMoved > 0) //eg:System.arraycopy(elementData,5+1,elementData,5,2) //eg:从数组elementData中的第6个位置开始复制2个数,复制到elementData中,从elementData中的5位置开始存放 //eg:{1,2,3,4,5,7,8} System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } //删除该元素在数组中第一次出现的位置上的数据。 如果有该元素返回true,如果false。 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; // clear to let GC do its work } //for循环使数组里每一个元素为null public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } //从2个集合中删除重叠的数据 public boolean removeAll(Collection<?> c) { return batchRemove(c, false); } //从2个集合中获取重叠的数据 public boolean retainAll(Collection<?> c) { return batchRemove(c, true); } // private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; //获得当前对象的所有元素 int r = 0, w = 0; //w:标记两个集合公共元素的个数 boolean modified = false; try { for (; r < size; r++) ////遍历集合A if (c.contains(elementData[r]) == complement) //判断集合B中是否包含集合A中的当前元素 elementData[w++] = elementData[r]; //如果包含则直接保存。 } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { //出现异常会导致 r !=size , 则将出现异常处后面的数据全部复制覆盖到数组里。 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { //置空数组后面的元素 // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; //记录集合中元素的改变(add/remove) size = w; modified = true; } } return modified; }
set方法
public E set(int index, E element) { rangeCheck(index); //检查数组下标越界 E oldValue = elementData(index); //取出原来的元素 elementData[index] = element; //替换元素 return oldValue; //返回原来的元素 } @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
get方法
public E get(int index) { rangeCheck(index); //检查数组下标越界 return elementData(index); }
iterator
public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { int cursor; //默认0 int lastRet = -1; //上次返回的元素 int expectedModCount = modCount; //用于判断集合是否修改过结构的标识 public boolean hasNext() { return cursor != size; //游标是否达到数组最大值了 } @SuppressWarnings("unchecked") 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; //游标+1 return (E) elementData[lastRet = i];//返回元素,并将记录上次返回元素的下标 } public void remove() { //remove掉上次next的元素 if (lastRet < 0) //判断有没有执行过next方法 throw new IllegalStateException(); checkForComodification(); // try { ArrayList.this.remove(lastRet); //删除上次next的元素,会修改modCount cursor = lastRet; //被删除位置赋值给游标 lastRet = -1; //不能连续删除 expectedModCount = modCount; //更新expectedModCount } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { //Fail-Fast 机制 if (modCount != expectedModCount) //因此如果在使用迭代器的过程中有其他线程修改了modCount,就会抛ConcurrentModificationException() throw new ConcurrentModificationException(); }
总结
ArrayList基于数组方式实现,容量限制不大于Integer.MAX_VALUE的小大,每次扩容1.5倍。有序,可以为null,允许重复,非线程安全。
elementData属性采用了transient来修饰,不使用Java默认的序列化机制来实例化,自己实现了序列化writeObject()和反序列化readObject()的方法。
增加和删除会修改modCount,在迭代的时候需要保持单线程的唯一操作,如果期间进行了插入或者删除操作,就会被迭代器检查获知,从而出现运行时异常。
推荐阅读