摘要:一路至此,風(fēng)景過半。與雖然名字各異,源碼實(shí)現(xiàn)基本相同,除了增加了線程安全。同時(shí)注意溢出情況處理。同時(shí)增加了考慮并發(fā)問題。此外,源碼中出現(xiàn)了大量泛型如。允許為非線程安全有序。
一路至此,風(fēng)景過半。ArrayList與Vector雖然名字各異,源碼實(shí)現(xiàn)基本相同,除了Vector增加了線程安全。所以作者建議我們?cè)诓恍枰€程安全的情況下盡量使用ArrayList。下面看看在ArrayList源碼中遇到什么有趣的事情。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA與EMPTY_ELEMENTDATA/** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */ 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); } } /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection"s * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) ① if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
區(qū)別:DEFAULTCAPACITY_EMPTY_ELEMENTDATA用于無參初始化;EMPTY_ELEMENTDATA用于指定容量為0時(shí)的初始化。
trimToSize()/** * Trims the capacity of this ArrayList instance to be the * list"s current size. An application can use this operation to minimize * the storage of an ArrayList instance. */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }
去除擴(kuò)容后未存放元素的預(yù)留空間,以size為基準(zhǔn)。
ensureCapacity() --> ensureExplicitCapacity() --> grow() --> hugeCapacity()/** * Increases the capacity of this ArrayList instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It"s already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code 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) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
預(yù)設(shè)容量(提前擴(kuò)容),可提高初始化效率。擴(kuò)容后比擴(kuò)容前多了“oldCapacity >> 1”(即多了原來的50%)。同時(shí)注意溢出情況處理。(overflow-conscious code)。即“a-b<0”而不是"a
If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
* null. (This is useful in determining the length of the
* list only if the caller knows that the list does not contain
* any null elements.)
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose.
* @return an array containing the elements of the list
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this list
* @throws NullPointerException if the specified array is null
*/
@SuppressWarnings("unchecked")
public int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE + 1;
System.out.println(a < b); // false
System.out.println(a - b < 0); // true
toArray()
/**
* Returns an array containing all of the elements in this list in proper
* sequence (from first to last element); the runtime type of the returned
* array is that of the specified array. If the list fits in the
* specified array, it is returned therein. Otherwise, a new array is
* allocated with the runtime type of the specified array and the size of
* this list.
*
*
當(dāng)傳入數(shù)組長(zhǎng)度大于ArrayList的size時(shí),將a[size]置空作為調(diào)用者判斷標(biāo)志。根據(jù)這段代碼寫了個(gè)demo幫助理解:(擴(kuò)展知識(shí)見②)
ArrayList al = new ArrayList(); al.add("s"); String[] s = {"c","h","e"}; String[] sal = (String[]) al.toArray(s); System.out.println(sal[0] + "," + sal[1] + "," + sal[2]); // s,null,eadd()
/** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ 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++; }
新增、刪除都用到了System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);下面舉例加深理解。
String[] arr ={"r", "e", "b", "e", "y", "."}; System.arraycopy(arr, 0, arr, 2, 2); for(String i : arr) { System.out.println(i); }
即將arr下標(biāo)從0開始的2個(gè)元素拷貝到arr下標(biāo)從2開始的位置。
retainAll()/** * Retains only the elements in this list that are contained in the * specified collection. In other words, removes from this list all * of its elements that are not contained in the specified collection. * * @param c collection containing elements to be retained in this list * @return {@code true} if this list changed as a result of the call * @throws ClassCastException if the class of an element of this list * is incompatible with the specified collection * (optional) * @throws NullPointerException if this list contains a null element and the * specified collection does not permit null elements * (optional), * or if the specified collection is null * @see Collection#contains(Object) */ public boolean retainAll(Collection> c) { Objects.requireNonNull(c); return batchRemove(c, true); } private boolean batchRemove(Collection> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. // 保證異常時(shí),未比較元素不丟失 if (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; size = w; modified = true; } } return modified; }
a.retainAll(c)可以看成取a與c交集,a非c子集時(shí),返回true。a中只留在c中存在的元素,其余刪除。否則,返回false。
“elementData[w++] = elementData[r];”w永遠(yuǎn)小于等于r,因此可以將找到的相等元素大膽的放在elementData[w++]中(elementData[w++]是先放后加)。
iterator()/** * Returns an iterator over the elements in this list in proper sequence. * *The returned iterator is fail-fast. * * @return an iterator over the elements in this list in proper sequence */ public Iterator
iterator() { return new Itr(); } /** * An optimized version of AbstractList.Itr */ private class Itr implements Iterator { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; // 是否有下一個(gè)元素 public boolean hasNext() { return cursor != size; } // 游標(biāo)移動(dòng) @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; return (E) elementData[lastRet = i]; //第一次cursor=1,lastRet=0 } // lastRet不等于-1時(shí)才能進(jìn)行刪除,即next()后才能使用remove() public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic !!! cursor = i; lastRet = i - 1; checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
Iterator()所指類似數(shù)據(jù)庫的游標(biāo),不了解的同學(xué)可參看以下解釋:
當(dāng)使用語句Iterator it=List.Iterator()時(shí),迭代器it指向的位置是Iterator1指向的位置,當(dāng)執(zhí)行語句it.next()之后,迭代器指向的位置后移到Iterator2指向的位置。[1]
由源碼可見ArrayList的迭代器基于Itr子類實(shí)現(xiàn)。該類實(shí)現(xiàn)了Iterator接口,并重寫了它的全部方法(4種)。同時(shí)增加了checkForComodification()考慮并發(fā)問題。
listIterator()/** * Returns a list iterator over the elements in this list (in proper * sequence), starting at the specified position in the list. * The specified index indicates the first element that would be * returned by an initial call to {@link ListIterator#next next}. * An initial call to {@link ListIterator#previous previous} would * return the element with the specified index minus one. * *The returned list iterator is fail-fast. * * @throws IndexOutOfBoundsException {@inheritDoc} */ public ListIterator
listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } /** * Returns a list iterator over the elements in this list (in proper * sequence). * * The returned list iterator is fail-fast. * * @see #listIterator(int) */ public ListIterator
listIterator() { return new ListItr(0); } /** * An optimized version of AbstractList.ListItr */ private class ListItr extends Itr implements ListIterator { ListItr(int index) { super(); cursor = index; } // 向前 public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } // 替換 public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }
listIterator有2中構(gòu)造方法,即它多了指定游標(biāo)的功能。它實(shí)現(xiàn)了ListIterator
private class SubList extends AbstractList
此外,源碼中出現(xiàn)了大量泛型(如T、E...)。希望順便鞏固泛型知識(shí)。
ArrayList允許為null;非線程安全;有序。
更多有意思的內(nèi)容,歡迎訪問筆者小站: rebey.cn
知識(shí)點(diǎn)1.[ArrayList c.toArray might (incorrectly) not return Object[] (see 6260652);](http://www.cnblogs.com/cmdra/...
2.[為什么 Java ArrayList.toArray(T[]) 方法的參數(shù)類型是 T 而不是 E ?](http://www.cnblogs.com/xiaomi...;2016.04.07;
[1]JAVA中ListIterator和Iterator詳解與辨析;2014.11.27;
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/70131.html
摘要:如今行至于此,當(dāng)觀賞一方。由于所返回的無執(zhí)行意義。源碼閱讀總體門檻相對(duì)而言比,畢竟大多數(shù)底層都由實(shí)現(xiàn)了。比心可通過這篇文章理解創(chuàng)建一個(gè)實(shí)例過程圖工作原理往期線路回顧源碼一帶一路系列之源碼一帶一路系列之源碼一帶一路系列之 本文以jdk1.8中LinkedHashMap.afterNodeAccess()方法為切入點(diǎn),分析其中難理解、有價(jià)值的源碼片段(類似源碼查看是ctrl+鼠標(biāo)左鍵的過程...
摘要:同樣在源碼的與分別見看到老朋友和。這樣做可以降低性能消耗的同時(shí),還可以減少序列化字節(jié)流的大小,從而減少網(wǎng)絡(luò)開銷框架中。使用了反射來尋找是否聲明了這兩個(gè)方法。十進(jìn)制和,通過返回值能反應(yīng)當(dāng)前狀態(tài)。 Map篇暫告段落,卻并非離我們而去。這不在本篇中你就能經(jīng)常見到她。HashSet、LinkedHashSet、TreeSet各自基于對(duì)應(yīng)Map實(shí)現(xiàn),各自源碼內(nèi)容較少,因此歸納為一篇。 HashS...
摘要:本篇涉及少許以下簡(jiǎn)稱新特性,請(qǐng)?bào)H友們系好安全帶,準(zhǔn)備開車。觀光線路圖是在中新增的一個(gè)方法,相對(duì)而言較為陌生。其作用是把的計(jì)算結(jié)果關(guān)聯(lián)到上即返回值作為新。實(shí)際上,乃縮寫,即二元函數(shù)之意類似。 本文以jdk1.8中HashMap.compute()方法為切入點(diǎn),分析其中難理解、有價(jià)值的源碼片段(類似源碼查看是ctrl+鼠標(biāo)左鍵的過程)。本篇涉及少許Java8(以下簡(jiǎn)稱J8)新特性,請(qǐng)?bào)H友們...
摘要:觀光線路圖將涉及到的源碼全局變量哈希表初始化長(zhǎng)度默認(rèn)值是負(fù)載因子默認(rèn)表示的填滿程度。根據(jù)是否為零將原鏈表拆分成個(gè)鏈表,一部分仍保留在原鏈表中不需要移動(dòng),一部分移動(dòng)到原索引的新鏈表中。 前言 本文以jdk1.8中HashMap.putAll()方法為切入點(diǎn),分析其中難理解、有價(jià)值的源碼片段(類似ctrl+鼠標(biāo)左鍵查看的源碼過程)。?觀光線路圖:putAll() --> putMapEnt...
摘要:表示該類本身不可比表示與對(duì)應(yīng)的之間不可比。當(dāng)數(shù)目滿足時(shí),鏈表將轉(zhuǎn)為紅黑樹結(jié)構(gòu),否則繼續(xù)擴(kuò)容。至此,插入告一段落。當(dāng)超出時(shí),哈希表將會(huì)即內(nèi)部數(shù)據(jù)結(jié)構(gòu)重建至大約兩倍。要注意的是使用許多有這相同的鍵值肯定會(huì)降低哈希表性能。 回顧上期?觀光線路圖:putAll() --> putMapEntries() --> tableSizeFor() --> resize() --> hash() --...
閱讀 3259·2021-11-15 11:37
閱讀 1065·2021-11-02 14:45
閱讀 3893·2021-09-04 16:48
閱讀 3569·2019-08-30 15:55
閱讀 748·2019-08-23 17:53
閱讀 994·2019-08-23 17:03
閱讀 2020·2019-08-23 16:43
閱讀 2183·2019-08-23 16:22