JDK源碼閱讀——ArrayList

2019-11-11 04:14:59

字體：大中小

來源：轉載

供稿：網友

序

如同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再來回答這個問題。

上一篇：scala基礎知識學習(基于Gatling源碼)1_mutale.map,case class

下一篇：LEETCODE--Number of Boomerangs