JDK源碼閱讀——ArrayList

2019-11-11 04:14:59

字體：大中小

供稿：網(wǎng)友

序

如同C語言中字符數(shù)組向String過渡一樣，作為面向?qū)ο笳Z言，自然而然的出現(xiàn)了由Object[]數(shù)據(jù)形成的集合。本文從JDK源碼出發(fā)簡(jiǎn)單探討一下ArrayList的幾個(gè)重要方法。

Fields

//序列化Id保證了集合是可以進(jìn)行RPC通信的 PRivate static final long serialVersionUID = 8683452581122892189L; //作為一個(gè)普通Object[]數(shù)組，集合的默認(rèn)長(zhǎng)度是10 private static final int DEFAULT_CAPACITY = 10; //這里聲明一個(gè)空Object數(shù)組，用來標(biāo)示空集合 private static final Object[] EMPTY_ELEMENTDATA = {}; //默認(rèn)長(zhǎng)度的Object數(shù)組 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //真正存儲(chǔ)數(shù)據(jù)的的Object數(shù)組，transient保證不會(huì)參與序列化 transient Object[] elementData; //當(dāng)前ArrayList的長(zhǎng)度 private int size;

構(gòu)造器

//當(dāng)用戶指定了容量的時(shí)候，elementData就是新new出來的Object數(shù)組，如果長(zhǎng)度指定為0則等于聲明的空Object數(shù)組。不支持負(fù)數(shù)長(zhǎng)度。 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); } } //若用戶沒有指定長(zhǎng)度，構(gòu)造一個(gè)默認(rèn)長(zhǎng)度為10的空Object數(shù)組。 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //如果傳入的是集合類，則拷貝出一個(gè)新的Object數(shù)組存放用戶輸入的數(shù)組內(nèi)容 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) //根據(jù)c的聲明方式不同，c.toArray()得到的結(jié)果類型是不同的。雖然elementData聲明的是Object數(shù)組，但是如果c.toArray()不是Object數(shù)組類型，elementData無法存放Object類型。所以這里做了判斷，如果是這種情況，重新拷貝一份新的Object數(shù)組。 //關(guān)于這點(diǎn)特性可以參考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 { // 如果傳入的長(zhǎng)度為0，則elementData等于聲明的空數(shù)組 this.elementData = EMPTY_ELEMENTDATA; } }

內(nèi)部方法

//由于elementData會(huì)進(jìn)行擴(kuò)容，擴(kuò)容機(jī)制見下文。所以會(huì)生成一些沒有用的位置，通過trimToSize方法啊重新生成一段實(shí)際長(zhǎng)度的Object數(shù)組。長(zhǎng)度全為有效長(zhǎng)度。 public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //核心功能，提前擴(kuò)容。當(dāng)需要擴(kuò)容的空間很大的時(shí)候，可以通過這個(gè)以前一次性擴(kuò)容，否則會(huì)一次次慢慢擴(kuò)容。這種方式效率很高。 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果用戶希望的大小大于當(dāng)前的容量，則進(jìn)行擴(kuò)容 if (minCapacity - elementData.length > 0) grow(minCapacity); } //擴(kuò)容方法 private void grow(int minCapacity) { // 新容量為老容量的1.5倍 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //如果新容量依然沒有達(dá)到用戶期望的長(zhǎng)度，則以用戶輸入的容量為準(zhǔn)擴(kuò)容。 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果新容量已經(jīng)特別大接近極限了，進(jìn)行最大程度的擴(kuò)容 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); } //最大程度擴(kuò)容方法 private static int hugeCapacity(int minCapacity) { //如果用戶期待的容量很大，比最大整數(shù)還大就是負(fù)數(shù)了，則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); //進(jìn)行擴(kuò)容，首先進(jìn)行+1擴(kuò)容 ensureCapacityInternal(size + 1); //將index后面的統(tǒng)一往后移動(dòng)，所以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) //統(tǒng)一往前移動(dòng) System.arraycopy(elementData, index+1, elementData, index,numMoved); //把最后一個(gè)空出來的賦值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); } //檢查參數(shù) 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; //依然是原始數(shù)組，不過是聲明了一個(gè)不同的其實(shí)與結(jié)尾坐標(biāo)，總體邏輯和外部類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++; }

總結(jié)

ArrayList的源碼重點(diǎn)在于： 1. 擴(kuò)容的時(shí)候按照原容量的1.5倍擴(kuò)容 2. 若需要的容量很大，可以通過ensureCapacity進(jìn)行提前一步到位擴(kuò)容，或者直接通過構(gòu)造器聲明一個(gè)大的ArrayList。 3. 對(duì)Object[]進(jìn)行操作的時(shí)候都是通過System.arraycopy進(jìn)行的，這是一個(gè)native方法，直接操作內(nèi)存，等同于C語言中的底層方法。 4. 關(guān)于默認(rèn)長(zhǎng)度為什么是10，還不是很明白。按照StackOverFlow的說法是作為一個(gè)List長(zhǎng)度沒有必要是2的次冪。10不大不小，剛好夠用（通過數(shù)據(jù)分析得到）。但是我仍然不理解為什么HashMap就要是2的次冪。等看完HashMap再來回答這個(gè)問題。

上一篇：scala基礎(chǔ)知識(shí)學(xué)習(xí)(基于Gatling源碼)1_mutale.map,case class

下一篇：LEETCODE--Number of Boomerangs