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