終生求職之 ArrayList 篇
本文轉(zhuǎn)載自微信公眾號「稀飯下雪」，作者帥氣的小飯飯 。轉(zhuǎn)載本文請聯(lián)系稀飯下雪公眾號。
最近又到了適合交配的季節(jié)了，不對，跳槽的季節(jié)了，發(fā)現(xiàn)好多之前看的知識點(diǎn)都忘記了，為此我做了面壁思過，最終總結(jié)如下。
問題的根本：
- 不是不懂，而是記不住。
- 一次性了解的東西可能不夠深入。
針對這兩種情況，解決方案也不難：
- 每隔一段時(shí)間都要重新看回以前的東西，加深記憶力
- 一次性了解的不夠深入，那就多來幾次，然后加上備忘錄
為此，我定了一個(gè)終生求職計(jì)劃
終生求職是一種狀態(tài)，讓自己一直保持隨時(shí)可以面試的狀態(tài)，目前行業(yè)越來越卷，這種狀態(tài)很有必要
我這邊預(yù)計(jì)是每兩個(gè)月都會回顧一次筆記，然后不定期發(fā)文章。
好了，接下來繼續(xù)聊聊 ArrayList。
ArrayList參數(shù)和構(gòu)造函數(shù)
- // 存儲數(shù)組元素的緩沖區(qū)
- transient Object[] elementData;
- // 默認(rèn)空數(shù)組元素
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- // 默認(rèn)初始化容量
- private static final int DEFAULT_CAPACITY = 10;
- // 數(shù)組的大小
- private int size;
- // 記錄被修改的次數(shù)
- protected transient int modCount = 0;
- // 數(shù)組的最大值
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
底層ArrayList使用數(shù)組實(shí)現(xiàn)
構(gòu)造函數(shù)的幾種情況：
- 空構(gòu)造函數(shù)
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 空數(shù)組
- }
- 有參構(gòu)造函數(shù)
- public ArrayList(int initialCapacity) {
- if (initialCapacity > 0) {
- this.elementData = new Object[initialCapacity]; // 數(shù)組的大小為參數(shù)的大小
- } else if (initialCapacity == 0) {
- this.elementData = EMPTY_ELEMENTDATA; // 空數(shù)組
- } else {
- throw new IllegalArgumentException("Illegal Capacity: "+
- initialCapacity);
- }
- }
Collection轉(zhuǎn)Arraylist
- 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;
- }
- }
參數(shù)collection個(gè)數(shù)不為0的直接轉(zhuǎn)成Arraylist，但是用的是system.copy
202112留言： ArrayList構(gòu)造函數(shù)，除非賦值，否則初始化后內(nèi)部數(shù)組都是空數(shù)組，而第一次擴(kuò)容則發(fā)生在添加元素的時(shí)候。
ArrayList添加元素與擴(kuò)容
ArrayList.add(E e)源碼：
可以看到底層使用的是System.arraycopy，而這個(gè)copy的過程是比較耗性能的，因此建議初始化時(shí)預(yù)估一個(gè)容量大小。
202112留言： 用無參構(gòu)造函數(shù)創(chuàng)建ArrayList后進(jìn)行第一次擴(kuò)容容量是10，后續(xù)則是1.5倍，底層調(diào)用的是System.arraycopy，而這個(gè)copy的過程是比較耗性能的，因此建議初始化時(shí)預(yù)估一個(gè)容量大小。
ArrayList刪除元素
ArrayList提供兩種刪除元素的方法，可以通過索引和元素進(jìn)行刪除。兩種刪除大同小異，刪除元素后，將后面的元素一次向前移動(dòng)。
ArrayList.remove(int index)源碼：
- 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);
- elementData[--size] = null; // clear to let GC do its work
- return oldValue;
- }
刪除元素時(shí)，首先會判斷索引是否大于ArrayList的大小，如果索引范圍正確，則將索引位置的下一個(gè)元素賦值到索引位置，將ArrayList的大小-1，最后返回移除的元素。
這里也可以看到modCount++，正如前面所說，就是為了做并發(fā)處理，不允許其他線程在這個(gè)的同時(shí)做修改，同時(shí)也不允許自身線程在同時(shí)遍歷修改。
elementData[--size] = null;可以看到，就是將最后一個(gè)值置空，方便GC掉。
202112備注： 刪除后底層調(diào)用的依舊是System.arraycopy，而這個(gè)copy的過程是比較耗性能的，因此才說頻繁增刪的盡量別用ArrayList。
ArrayList遍歷
- @Override
- public void forEach(Consumer<? super E> action) {
- Objects.requireNonNull(action);
- // 預(yù)設(shè)值了一個(gè)expectedModCount值
- final int expectedModCount = modCount;
- @SuppressWarnings("unchecked")
- final E[] elementData = (E[]) this.elementData;
- final int size = this.size;
- // 遍歷過程中拿出來判斷
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- action.accept(elementData[i]);
- }
- // 如果對不上則報(bào)錯(cuò)
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- }
從代碼就可以看出來了，在遍歷的時(shí)候會率先 預(yù)設(shè)值了一個(gè)expectedModCount值，然后再遍歷拿出來判斷，如果不一樣了，則中斷流程并且報(bào)錯(cuò)，而這個(gè)過程則涉及到了快速失敗機(jī)制了，正常來說，ArrayList不允許遍歷刪除。
202112備注： ArrayList通過預(yù)設(shè)值expectedModCount實(shí)現(xiàn)了快速失敗機(jī)制，避免了多線程遍歷刪除或者增加，以及遍歷過程中增刪元素。
集合的快速失敗(fail-fast)
它是 Java 集合的一種錯(cuò)誤檢測機(jī)制，當(dāng)多個(gè)線程對集合進(jìn)行結(jié)構(gòu)上的改變操作時(shí)，有可能會產(chǎn)生 fail-fast 機(jī)制。
迭代器在遍歷時(shí)直接訪問集合中的內(nèi)容，并且在遍歷過程中使用一個(gè) modCount 變量。
集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會改變modCount的值。
每當(dāng)?shù)魇褂胔ashNext()/next()遍歷下一個(gè)元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍歷;否則拋出異常，終止遍歷。
注意：這里異常的拋出條件是檢測到 modCount!=expectedmodCount 這個(gè)條件。
如果集合發(fā)生變化時(shí)修改modCount值剛好又設(shè)置為了expectedmodCount值，則異常不會拋出。
因此，不能依賴于這個(gè)異常是否拋出而進(jìn)行并發(fā)操作的編程，這個(gè)異常只建議用于檢測并發(fā)修改的bug。
場景：java.util包下的集合類都是快速失敗的，不能在多線程下發(fā)生并發(fā)修改(迭代過程中被修改)。
202112備注： 我們?nèi)粘？吹降腃oncurrent Modification Exception，其實(shí)就是觸發(fā)了快速失敗機(jī)制的表現(xiàn)，做法也很簡單：
在遍歷的時(shí)候給你給modCount設(shè)置個(gè)備份expectedModCount，如果有多線程在搞，那么必定會導(dǎo)致modCount被改，那么就容易了，每次遍歷的時(shí)候都檢測下modCount變量是否為expectedModCount就可以了，如果不是意味著被改了，那我就不管，我就要報(bào)錯(cuò)。
集合的安全失敗(fail-safe)
采用安全失敗機(jī)制的集合容器，在遍歷時(shí)不是直接在集合內(nèi)容上訪問的，而是先復(fù)制原有集合內(nèi)容，在拷貝的集合上進(jìn)行遍歷。
原理：由于迭代時(shí)是對原集合的拷貝進(jìn)行遍歷，所以在遍歷過程中對原集合所作的修改并不能被迭代器檢測到，所以不會觸發(fā)Concurrent Modification Exception。
缺點(diǎn)：基于拷貝內(nèi)容的優(yōu)點(diǎn)是避免了Concurrent Modification Exception，但同樣地，迭代器并不能訪問到修改后的內(nèi)容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生的修改迭代器是不知道的。
場景：java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發(fā)使用，并發(fā)修改。
202112備注： 那么為啥并發(fā)容器的時(shí)候不怕呢?簡單，因?yàn)椴捎昧税踩C(jī)制，在遍歷的時(shí)候直接拷貝了一份出來，這樣就不會觸發(fā)了。
使用ArrayList的subList()需要注意的地方
- public List<E> subList(int fromIndex, int toIndex) {
- subListRangeCheck(fromIndex, toIndex, size);
- return new SubList(this, 0, fromIndex, toIndex);
- }
- 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;
- }
subList()返回結(jié)果不可強(qiáng)制轉(zhuǎn)為ArrayList類型，因?yàn)樵摲椒▽?shí)質(zhì)是創(chuàng)建一個(gè)內(nèi)部類SubList實(shí)例，這個(gè)SubList是AbstractList的實(shí)現(xiàn)類，并不繼承于ArrayList。
通過上面源碼可以看出，通過parent屬性指定父類并直接引用了原有的List，并返回該父類的部分視圖，只是指定了他要使用的元素的范圍fromIndex(包含)，endIndex(不包含)。
那么，如果對其原有或者子List做數(shù)據(jù)性修改，則會互相影響。如果對原有List進(jìn)行結(jié)構(gòu)性修改，則會踩坑Fast-fail，報(bào)錯(cuò)會拋出異常ConcurrentModification Exception。
202112備注： XList.subList()不能當(dāng)作ArrayList來使用，但是內(nèi)部其實(shí)是引用了實(shí)際上XList的部分元素，所以如果引用內(nèi)的對象被改，也會直接影響XList。
ArrayList迭代器
看下迭代器的遍歷和刪除相關(guān)的源碼
- public boolean hasNext() {
- return cursor != size;
- }
- @SuppressWarnings("unchecked")
- public E next() {
- // 同樣判斷modCount != expectedModCount，不同則報(bào)錯(cuò)
- 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];
- }
- public void remove() {
- if (lastRet < 0)
- throw new IllegalStateException();
- checkForComodification();
- try {
- ArrayList.this.remove(lastRet);
- cursor = lastRet;
- lastRet = -1;
- // 這里刪除后會重新復(fù)制一次
- expectedModCount = modCount;
- } catch (IndexOutOfBoundsException ex) {
- throw new ConcurrentModificationException();
- }
- }
202112備注： 為什么ArrayList的迭代器是支持遍歷刪除的，原因很簡單，因?yàn)樵趧h除后會重新賦一次值給expectedModCount。
ArrayList和LinkedList的優(yōu)劣
其實(shí)就是數(shù)組和鏈表的優(yōu)劣勢，ArrayList優(yōu)點(diǎn)，支持隨機(jī)訪問，get(i)的時(shí)間復(fù)雜度為O(1)，而缺點(diǎn)就是需要擴(kuò)容，要復(fù)制數(shù)組，而且內(nèi)部插入數(shù)據(jù)需要移動(dòng)數(shù)據(jù)，插入刪除的性能差;
對于LinkedList來說，優(yōu)點(diǎn)就是容量理論上來說是無限，不存在擴(kuò)容，而且可以很方便的插入和刪除數(shù)據(jù)(性能損失在查找)，而缺點(diǎn)就是不能隨機(jī)訪問，get(i)需要遍歷。
貌似就是反過來的，所以在實(shí)際開發(fā)中也很容易區(qū)別，看是查找頻繁、還是增刪頻繁，如果是查找頻繁就用ArrayList，如果增刪頻繁就用LinkedList即可。
202112備注： ：ArrayList和LinkedList的優(yōu)劣可以從數(shù)組和鏈表的結(jié)構(gòu)上來回答，額外補(bǔ)充擴(kuò)容問題，再回答索引查找頻繁還是增刪頻繁。
原文鏈接：https://mp.weixin.qq.com/s/QEzHmLNj-uUytOsikpBf7g
