萬萬沒想到!!! 谷歌面試原來也問ArrayList
本文轉載自微信公眾號「稀飯下雪」，作者帥氣的小飯飯 。轉載本文請聯系稀飯下雪公眾號。
前幾天H同學和我聊了下去谷歌的面試經驗，令我詫異的是，沒想到谷歌也問ArrayList???
仔細一想也正常，畢竟集合是Java程序員逃不掉的金光咒。
看文章前可以先看看以下幾個問題，如果覺得莫得問題，可以直接跳過該篇文章了，不用浪費大家時間。
- ArrayList使用無參構造函數的時候什么時候進行擴容?
- 說說看ArrayList是擴容的時候是怎么復制數組的?
- 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使用數組實現，不設置的話，默認初始容量為10
- // 數組擴容方法
- // minCapacity = size + 1
- private int newCapacity(int minCapacity) {
- // 當前數組長度
- int oldCapacity = elementData.length;
- // 新的數組容量 = 舊數組長度 + 舊數組長度 / 2
- // oldCapacity = 10 oldCapacity >> 1 --- 5
- // 例如10的二進制為 : 0000 1010 >> 1 -----> 0000 0101 = 5
- int newCapacity = oldCapacity + (oldCapacity >> 1);
- if (newCapacity - minCapacity <= 0) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
- // 如果一開始沒有定義初始容量這時newCapacity=0,返回默認容量10
- // 可以得出當無參new 一個ArrayList()時候，這個ArrayList()為空集合，size為0
- return Math.max(DEFAULT_CAPACITY, minCapacity);
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- return minCapacity;
- }
- return (newCapacity - MAX_ARRAY_SIZE <= 0)
- ? newCapacity // 這里返回的長度為原數組的1.5倍
- : hugeCapacity(minCapacity);
- }
當增加元素的時候發現底層數組的需要的容量(size+1)大于數組的容量的時候，就會觸發擴容，在首次調用add()方法之后，返回一個容量為10的數組，后面每次擴容后新數組的長度為原數組長度的 「1.5」 倍，并調用底層原生的System.arraycopy將舊數組的數據copy到新的數組中，完成整個擴容。
所以日常開發中，在知道初始值的時候先設置初始值，因為擴容是比較耗性能的。
「不用腦子的總結：首次擴容為10 ，后面每次擴容為原數組的1.5倍，調用底層原生的System.arraycopy將舊數組的數據copy到新的數組中，完成整個擴容。」
ArrayList添加元素與擴容
ArrayList.add(E e)源碼：
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
add()中elementData[size++] = e很好理解，就是將元素插入第size個位置，然后將size++，我們重點來看看ensureCapacityInternal(size + 1)方法;
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity);
- }
ensureCapacityInternal()方法中判斷緩存變量elementData是否為空，也就是判斷是否是第一次添加元素，如果是第一次添加元素，則設置初始化大小為默認容量10，否則為傳入的參數。這個方法的目的就是「獲取初始化數組容量」。獲取到初始化容量后調用ensureExplicitCapacity(minCapacity)方法;
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
ensureExplicitCapacity(minCapacity)方法用來判斷是否需要擴容，假如第一次添加元素，minCapacity為10，elementData容量為0，那么就需要去擴容。調用grow(minCapacity)方法。
- // 數組的最大容量
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;
- // 擴容大小為原來數組長度的1.5倍
- 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);
- }
grow(minCapacity)方法對數組進行擴容，擴容大小為原數組的1.5倍，如果計算出的擴容容量比需要的容量小，則擴容大小為需要的容量，可以看到，第一次擴容的時候其實是10。如果擴容容量比數組最大容量大，則調用hugeCapacity(minCapacity)方法，將數組擴容為整數的最大長度，然后將elemetData數組指向新擴容的內存空間并將元素復制到新空間，這里使用的是 Arrays.copyOf(elementData, newCapacity)
- public static int[] copyOf(int[] original, int newLength) {
- int[] copy = new int[newLength];
- System.arraycopy(original, 0, copy, 0,
- Math.min(original.length, newLength));
- return copy;
- }
可以看到底層使用的是System.arraycopy，而這個copy的過程是比較耗性能的，因此建議初始化時預估一個容量大小。
「不用腦子的總結：用無參構造函數創建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，最后返回移除的元素。
「不用腦子的總結：刪除后底層調用的依舊是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();
- }
- }
- public E remove(int index) {
- rangeCheck(index);
- // 修改了modCount
- 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;
- }
從代碼就可以看出來了，在遍歷的時候會率先 預設值了一個expectedModCount值，然后再遍歷拿出來判斷，如果不一樣了，則中斷流程并且報錯，而這個過程則涉及到了快速失敗機制了，正常來說，ArrayList不允許遍歷刪除。
「不用腦子的總結：ArrayList通過預設值expectedModCount實現了快速失敗機制，避免了多線程遍歷刪除或者增加，以及遍歷過程中增刪元素。」
集合的快速失敗(fail-fast)
它是 Java 集合的一種錯誤檢測機制，當多個線程對集合進行結構上的改變操作時，有可能會產生 fail-fast 機制。
迭代器在遍歷時直接訪問集合中的內容，并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內容發生變化，就會改變modCount的值。每當迭代器使用hashNext()/next()遍歷下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍歷;否則拋出異常，終止遍歷。
注意：這里異常的拋出條件是檢測到 modCount!=expectedmodCount 這個條件。如果集合發生變化時修改modCount值剛好又設置為了expectedmodCount值，則異常不會拋出。因此，不能依賴于這個異常是否拋出而進行并發操作的編程，這個異常只建議用于檢測并發修改的bug。
場景：java.util包下的集合類都是快速失敗的，不能在多線程下發生并發修改(迭代過程中被修改)。
「不用腦子的總結：我們日常看到的Concurrent Modification Exception，其實就是觸發了快速失敗機制的表現，做法也很簡單：在遍歷的時候給你給modCount設置個備份expectedModCount，如果有多線程在搞，那么必定會導致modCount被改，那么就容易了，每次遍歷的時候都檢測下modCount變量是否為expectedModCount就可以了，如果不是意味著被改了，那我就不管，我就要報錯。」
集合的安全失敗(fail-safe)
采用安全失敗機制的集合容器，在遍歷時不是直接在集合內容上訪問的，而是先復制原有集合內容，在拷貝的集合上進行遍歷。
原理：由于迭代時是對原集合的拷貝進行遍歷，所以在遍歷過程中對原集合所作的修改并不能被迭代器檢測到，所以不會觸發Concurrent Modification Exception。
缺點：基于拷貝內容的優點是避免了Concurrent Modification Exception，但同樣地，迭代器并不能訪問到修改后的內容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發生的修改迭代器是不知道的。
場景：java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發使用，并發修改。
「不用記憶的總結：那么為啥并發容器的時候不怕呢?簡單，因為采用了安全失敗機制，在遍歷的時候直接拷貝了一份出來，這樣就不會觸發了。」
使用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。
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();
- }
- }
通過代碼我們也可以看出ArrayList的迭代器是支持遍歷刪除的，因為在刪除后會重新賦一次值給expectedModCount。
ArrayList和LinkedList的優劣
其實就是數組和鏈表的優劣勢，ArrayList優點，支持隨機訪問，get(i)的時間復雜度為O(1)，而缺點就是需要擴容，要復制數組，而且內部插入數據需要移動數據，插入刪除的性能差;
對于LinkedList來說，優點就是容量理論上來說是無限，不存在擴容，而且可以很方便的插入和刪除數據(性能損失在查找)，而缺點就是不能隨機訪問，get(i)需要遍歷。
貌似就是反過來的，所以在實際開發中也很容易區別，看是查找頻繁、還是增刪頻繁，如果是查找頻繁就用ArrayList，如果增刪頻繁就用LinkedList即可。
