摘要:顯然,開發人員認為通過下標遍歷的數組結構更加高效。在進行分裂時,原始保留中部至末尾的元素,新的保留原起始位置到中部的元素。同樣,也會進行重新賦值,使得在使用前與保持一致。在遍歷時,會調用方法,將動作施加于元素之上。
java.util.ArrayList
ArrayList繼承自AbstractList,AbstractList為隨機訪問數據的結構,如數組提供了基本實現,并且提供了Iterator。首先看AbstractList實現了什么方法。
AbstractList AbstractList里可以存儲null嗎null可以作為一項存儲在ArrayList中。ListIterator是遍歷訪問AbstractList中元素較好的方式,需要注意獲取元素序號的方法是previousIndex,而不是nextIndex,因為之前有next方法的調用。還有,這里判斷兩個元素是否相等采用的是equals方法,而不是==。
public int indexOf(Object o) { ListIteratorListIterator可以逆序訪問元素it = listIterator(); if (o==null) { while (it.hasNext()) if (it.next()==null) return it.previousIndex(); } else { while (it.hasNext()) if (o.equals(it.next())) return it.previousIndex(); } return -1; }
從后向前遍歷AbstractList,過程恰恰相反。
public int lastIndexOf(Object o) { ListIteratorIterator遍歷元素時,被其它線程修改了怎么辦it = listIterator(size()); if (o==null) { while (it.hasPrevious()) if (it.previous()==null) return it.nextIndex(); } else { while (it.hasPrevious()) if (o.equals(it.previous())) return it.nextIndex(); } return -1; }
如果在使用Iterator時,有其他線程嘗試去修改List的大小,會被發現且立即拋出異常。
可以看class Itr implements Iterator
有兩個游標分別記錄當前指向的位置和上一次指向的位置。
/** * Index of element to be returned by subsequent call to next. */ int cursor = 0; /** * Index of element returned by most recent call to next or * previous. Reset to -1 if this element is deleted by a call * to remove. */ int lastRet = -1;如何處理遍歷過程中,刪除list中的元素導致的序號偏移
Iterator可以正確的刪除AbstractList中的元素,并且保證訪問的順序的正確性。
public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } }
刪除的元素是上一個next調用后的元素,并且連續調用兩次remove會拋出異常,因為元素只能刪除一次,上次指向的元素已經沒有了。
ListIterator可以添加元素在class ListItr extends Itr implements ListIterator
public void add(E e) { checkForComodification(); try { int i = cursor; AbstractList.this.add(i, e); lastRet = -1; cursor = i + 1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }ArrayList ArrayList用什么來存儲元素
就是用了一個簡單的數組。。。
/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access如何節約ArrayList占用的空間
使用trimToSize函數,將原始數組copy到適合大小的數組中。
/** * 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); } }用Iterator遍歷ArrayList真的高效嗎
不可否認,Iterator為遍歷一個集合提供了統一的接口,用戶可以忽略集合內部的具體實現,但是過多的封裝會導致效率的降低。顯然,Java開發人員認為通過下標遍歷ArrayList的數組結構更加高效。所以重寫了indexOf和lastIndexOf。
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }ArrayList的clone是淺copy
ArrayList只是新建了數組,copy了元素的引用,元素本身沒有進行copy。clone方法為什么不new一個ArrayList對象,而是調用了Object類的clone?因為Object的clone函數是native的,更高效。
/** * Returns a shallow copy of this ArrayList instance. (The * elements themselves are not copied.) * * @return a clone of this ArrayList instance */ public Object clone() { try { //使用Object的clone獲得一個對象 ArrayList> v = (ArrayList>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn"t happen, since we are Cloneable throw new InternalError(e); } }ArrayList存儲空間的擴展策略
如果list初始沒有元素,使用一個靜態的空數組。元素增加時,空間擴展為默認的10。在后續的擴展過程中,容量會每次增加原始大小的1/2。
ArrayList實現了自己的iterator雖然AbstractList實現了iterator,但ArrayList似乎不太滿意,又重新實現了一遍。主要區別就是在獲取元素時,利用了數組結構的優勢,可以直接通過下標獲取元素,而不必通過調用方法。
用Spliterator分割遍歷ArrayListArrayList理所當然的實現了自己的Spliterator,也就是ArrayListSpliterator。分割的策略簡而言之為:二分+延遲初始化。
ArrayListSpliterator有如下屬性:
this.list = list; // OK if null unless traversed 保存目標list this.index = origin; //起始位置 this.fence = fence; //終止位置 this.expectedModCount = expectedModCount; //期望修改次數,用來判斷運行時是否有其它線程修改
每次從中間開始分裂。在進行分裂時,原始spliterator保留中部至末尾的元素,新的spliterator保留原起始位置到中部的元素。
public ArrayListSpliteratortrySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : // divide range in half unless too small new ArrayListSpliterator (list, lo, index = mid, expectedModCount); }
在第一次創建spliterator時,fence被初始為-1,所以在實際使用spliterator時,getFence才會被調用,從而fence才會被賦值為數組大小。同樣,expectedModCount也會進行重新賦值,使得spliterator在使用前與list保持一致。
private int getFence() { // initialize fence to size on first use int hi; // (a specialized variant appears in method forEach) ArrayListlst; if ((hi = fence) < 0) { if ((lst = list) == null) hi = fence = 0; else { expectedModCount = lst.modCount; hi = fence = lst.size; } } return hi; }
在遍歷list時,會調用方法tryAdvance,將動作施加于元素之上。該方法會檢查是否有其它線程的修改,在ArrayList中,有大量方法都會使用modCount來記錄修改,或者判斷是否在方法執行時有其它線程的修改,目前看來,用這個方法來檢測是否有并行修改使得list結構變化是有效的,可以避免并行修改帶來的一些問題。
public boolean tryAdvance(Consumer super E> action) { if (action == null) throw new NullPointerException(); int hi = getFence(), i = index; if (i < hi) { index = i + 1; @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/67747.html
摘要:不同點是線程安全的,方法有關鍵字修飾。容量增長策略默認的增長策略是每次在原容量的基礎上。的怎么做到線程安全的實現了自己的,為了保證并發線程安全的共享一個,開發者在等方法中也加入了。與類繼承自,的實現不止一種方式,比如。 java.util.Vector Vector與ArrayList的異同 相同點:隨機存取,可通過位置序號直接獲取數據。都是通過一個數組來存放元素。 不同點:Vecto...
摘要:在中引入該方法,用來替換中的每個元素。的方法,只能在或之后使用,也就是確保當前指向了一個存在的項。這里使用了,該方法可以將非對象先映射為型,然后進行比較。存儲的是有序的數組,所以劃分時會按照順序進行劃分。 java.util.List replaceAll 在Java8中引入該方法,用來替換list中的每個元素。 default void replaceAll(UnaryOpe...
摘要:說到復盤基礎,并不是所有的都會復盤,沒那個時間更沒那個必要。比如,一些基礎的語法以及條件語句,極度簡單。思前想后,我覺得整個計劃應該從集合開始,而復盤的方式就是讀源碼。通常,隊列不允許隨機訪問隊列中的元素。 ?showImg(https://segmentfault.com/img/remote/1460000020029737?w=1080&h=711); 老讀者都知道,我是自學轉行...
摘要:集合類關系是和的父接口。相等必須是對稱的,約定只能和其它相等,亦然。和接口在中引入,這個單詞是和的合成,用來分割集合以給并行處理提供方便。這些并不立即執行,而是等到最后一個函數,統一執行。 集合類關系: Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ...
前言 聲明,本文使用的是JDK1.8 從今天開始正式去學習Java基礎中最重要的東西--->集合 無論在開發中,在面試中這個知識點都是非常非常重要的,因此,我在此花費的時間也是很多,得參閱挺多的資料,下面未必就做到日更了... 當然了,如果講得有錯的地方還請大家多多包涵并不吝在評論去指正~ 一、集合(Collection)介紹 1.1為什么需要Collection Java是一門面向對象的語言,...
閱讀 3904·2021-11-22 09:34
閱讀 1490·2021-11-04 16:10
閱讀 1721·2021-10-11 10:59
閱讀 3271·2019-08-30 15:44
閱讀 2036·2019-08-30 13:17
閱讀 3445·2019-08-30 11:05
閱讀 744·2019-08-29 14:02
閱讀 2618·2019-08-26 13:34