JDK源码阅读——ArrayList

2019-11-11 04:55:57

字体：大中小

来源：转载

供稿：网友

序

如同C语言中字符数组向String过渡一样，作为面向对象语言，自然而然的出现了由Object[]数据形成的集合。本文从JDK源码出发简单探讨一下ArrayList的几个重要方法。

Fields

//序列化Id保证了集合是可以进行RPC通信的 PRivate static final long serialVersionUID = 8683452581122892189L; //作为一个普通Object[]数组，集合的默认长度是10 private static final int DEFAULT_CAPACITY = 10; //这里声明一个空Object数组，用来标示空集合 private static final Object[] EMPTY_ELEMENTDATA = {}; //默认长度的Object数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //真正存储数据的的Object数组，transient保证不会参与序列化 transient Object[] elementData; //当前ArrayList的长度 private int size;

构造器

//当用户指定了容量的时候，elementData就是新new出来的Object数组，如果长度指定为0则等于声明的空Object数组。不支持负数长度。 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); } } //若用户没有指定长度，构造一个默认长度为10的空Object数组。 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //如果传入的是集合类，则拷贝出一个新的Object数组存放用户输入的数组内容 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) //根据c的声明方式不同，c.toArray()得到的结果类型是不同的。虽然elementData声明的是Object数组，但是如果c.toArray()不是Object数组类型，elementData无法存放Object类型。所以这里做了判断，如果是这种情况，重新拷贝一份新的Object数组。 //关于这点特性可以参考http://blog.csdn.net/aitangyong/article/details/30274749?utm_source=tuicool&utm_medium=referral if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 如果传入的长度为0，则elementData等于声明的空数组 this.elementData = EMPTY_ELEMENTDATA; } }

内部方法

//由于elementData会进行扩容，扩容机制见下文。所以会生成一些没有用的位置，通过trimToSize方法啊重新生成一段实际长度的Object数组。长度全为有效长度。 public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //核心功能，提前扩容。当需要扩容的空间很大的时候，可以通过这个以前一次性扩容，否则会一次次慢慢扩容。这种方式效率很高。 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果用户希望的大小大于当前的容量，则进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } //扩容方法 private void grow(int minCapacity) { // 新容量为老容量的1.5倍 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) { //如果用户期待的容量很大，比最大整数还大就是负数了，则OOM if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //否则就给最大的空间 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } //新增元素 public void add(int index, E element) { //检查索引，不合法就异常 rangeCheckForAdd(index); //进行扩容，首先进行+1扩容 ensureCapacityInternal(size + 1); //将index后面的统一往后移动，所以add效率很低 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } //删除元素 public E remove(int index) { //索引合法性检查 rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) //统一往前移动 System.arraycopy(elementData, index+1, elementData, index,numMoved); //把最后一个空出来的赋值null，方便gc回收 elementData[--size] = null; // clear to let GC do its work return oldValue; }//取子列表方法public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); } //检查参数 static void subListRangeCheck(int fromIndex, int toIndex, int size) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); if (toIndex > size) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex +") > toIndex(" + toIndex + ")"); } private class SubList extends AbstractList<E> implements Random access { private final AbstractList<E> parent; private final int parentOffset; private final int offset; int size; //依然是原始数组，不过是声明了一个不同的其实与结尾坐标，总体逻辑和外部类ArrayList基本相同 SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) { this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } //jdk1.7以后List本身有了sort功能，不用再通过Collections.sort来排序了 @Override @SuppressWarnings("unchecked") 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++; }

总结

ArrayList的源码重点在于： 1. 扩容的时候按照原容量的1.5倍扩容 2. 若需要的容量很大，可以通过ensureCapacity进行提前一步到位扩容，或者直接通过构造器声明一个大的ArrayList。 3. 对Object[]进行操作的时候都是通过System.arraycopy进行的，这是一个native方法，直接操作内存，等同于C语言中的底层方法。 4. 关于默认长度为什么是10，还不是很明白。按照StackOverFlow的说法是作为一个List长度没有必要是2的次幂。10不大不小，刚好够用（通过数据分析得到）。但是我仍然不理解为什么HashMap就要是2的次幂。等看完HashMap再来回答这个问题。

上一篇：MATLAB中videoinput编程的一些细节问题

下一篇：深入理解JVM内幕