萬萬沒想到!!! 谷歌面試原來也問ArrayList
本文轉(zhuǎn)載自微信公眾號「稀飯下雪」，作者帥氣的小飯飯 。轉(zhuǎn)載本文請聯(lián)系稀飯下雪公眾號。
前幾天H同學(xué)和我聊了下去谷歌的面試經(jīng)驗(yàn)，令我詫異的是，沒想到谷歌也問ArrayList???
仔細(xì)一想也正常，畢竟集合是Java程序員逃不掉的金光咒。
看文章前可以先看看以下幾個問題，如果覺得莫得問題，可以直接跳過該篇文章了，不用浪費(fèi)大家時間。
- ArrayList使用無參構(gòu)造函數(shù)的時候什么時候進(jìn)行擴(kuò)容?
- 說說看ArrayList是擴(kuò)容的時候是怎么復(fù)制數(shù)組的?
- ArrayList遍歷刪除的時候會觸發(fā)什么機(jī)制?為什么用迭代器遍歷刪除不會?
好了，接下來繼續(xù)聊聊高頻面試題 ArrayList。
ArrayList的擴(kuò)容機(jī)制
- // 存儲數(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)，不設(shè)置的話，默認(rèn)初始容量為10
- // 數(shù)組擴(kuò)容方法
- // minCapacity = size + 1
- private int newCapacity(int minCapacity) {
- // 當(dāng)前數(shù)組長度
- int oldCapacity = elementData.length;
- // 新的數(shù)組容量 = 舊數(shù)組長度 + 舊數(shù)組長度 / 2
- // oldCapacity = 10 oldCapacity >> 1 --- 5
- // 例如10的二進(jìn)制為 : 0000 1010 >> 1 -----> 0000 0101 = 5
- int newCapacity = oldCapacity + (oldCapacity >> 1);
- if (newCapacity - minCapacity <= 0) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
- // 如果一開始沒有定義初始容量這時newCapacity=0,返回默認(rèn)容量10
- // 可以得出當(dāng)無參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 // 這里返回的長度為原數(shù)組的1.5倍
- : hugeCapacity(minCapacity);
- }
當(dāng)增加元素的時候發(fā)現(xiàn)底層數(shù)組的需要的容量(size+1)大于數(shù)組的容量的時候，就會觸發(fā)擴(kuò)容，在首次調(diào)用add()方法之后，返回一個容量為10的數(shù)組，后面每次擴(kuò)容后新數(shù)組的長度為原數(shù)組長度的 「1.5」 倍，并調(diào)用底層原生的System.arraycopy將舊數(shù)組的數(shù)據(jù)copy到新的數(shù)組中，完成整個擴(kuò)容。
所以日常開發(fā)中，在知道初始值的時候先設(shè)置初始值，因?yàn)閿U(kuò)容是比較耗性能的。
「不用腦子的總結(jié)：首次擴(kuò)容為10 ，后面每次擴(kuò)容為原數(shù)組的1.5倍，調(diào)用底層原生的System.arraycopy將舊數(shù)組的數(shù)據(jù)copy到新的數(shù)組中，完成整個擴(kuò)容?！?/p>
ArrayList添加元素與擴(kuò)容
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++，我們重點(diǎn)來看看ensureCapacityInternal(size + 1)方法;
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity);
- }
ensureCapacityInternal()方法中判斷緩存變量elementData是否為空，也就是判斷是否是第一次添加元素，如果是第一次添加元素，則設(shè)置初始化大小為默認(rèn)容量10，否則為傳入的參數(shù)。這個方法的目的就是「獲取初始化數(shù)組容量」。獲取到初始化容量后調(diào)用ensureExplicitCapacity(minCapacity)方法;
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
ensureExplicitCapacity(minCapacity)方法用來判斷是否需要擴(kuò)容，假如第一次添加元素，minCapacity為10，elementData容量為0，那么就需要去擴(kuò)容。調(diào)用grow(minCapacity)方法。
- // 數(shù)組的最大容量
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;
- // 擴(kuò)容大小為原來數(shù)組長度的1.5倍
- int newCapacity = oldCapacity + (oldCapacity >> 1);
- // 擴(kuò)容容量比需要擴(kuò)容的長度小，則使用需要擴(kuò)容的容量
- if (newCapacity - minCapacity < 0)
- newCapacity = minCapacity;
- // 擴(kuò)容容量比最大數(shù)組長度大，則使用最大整數(shù)長度
- 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)方法對數(shù)組進(jìn)行擴(kuò)容，擴(kuò)容大小為原數(shù)組的1.5倍，如果計(jì)算出的擴(kuò)容容量比需要的容量小，則擴(kuò)容大小為需要的容量，可以看到，第一次擴(kuò)容的時候其實(shí)是10。如果擴(kuò)容容量比數(shù)組最大容量大，則調(diào)用hugeCapacity(minCapacity)方法，將數(shù)組擴(kuò)容為整數(shù)的最大長度，然后將elemetData數(shù)組指向新擴(kuò)容的內(nèi)存空間并將元素復(fù)制到新空間，這里使用的是 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的過程是比較耗性能的，因此建議初始化時預(yù)估一個容量大小。
「不用腦子的總結(jié)：用無參構(gòu)造函數(shù)創(chuàng)建ArrayList后進(jìn)行第一次擴(kuò)容容量是10，后續(xù)則是1.5倍，底層調(diào)用的是System.arraycopy，而這個copy的過程是比較耗性能的，因此建議初始化時預(yù)估一個容量大小。」
ArrayList刪除元素
ArrayList提供兩種刪除元素的方法，可以通過索引和元素進(jìn)行刪除。兩種刪除大同小異，刪除元素后，將后面的元素一次向前移動。
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，最后返回移除的元素。
「不用腦子的總結(jié)：刪除后底層調(diào)用的依舊是System.arraycopy，而這個copy的過程是比較耗性能的，因此才說頻繁增刪的盡量別用ArrayList?！?/p>
ArrayList遍歷刪除
- @Override
- public void forEach(Consumer<? super E> action) {
- Objects.requireNonNull(action);
- // 預(yù)設(shè)值了一個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;
- }
從代碼就可以看出來了，在遍歷的時候會率先 預(yù)設(shè)值了一個expectedModCount值，然后再遍歷拿出來判斷，如果不一樣了，則中斷流程并且報錯，而這個過程則涉及到了快速失敗機(jī)制了，正常來說，ArrayList不允許遍歷刪除。
「不用腦子的總結(jié)：ArrayList通過預(yù)設(shè)值expectedModCount實(shí)現(xiàn)了快速失敗機(jī)制，避免了多線程遍歷刪除或者增加，以及遍歷過程中增刪元素?！?/p>
集合的快速失敗(fail-fast)
它是 Java 集合的一種錯誤檢測機(jī)制，當(dāng)多個線程對集合進(jìn)行結(jié)構(gòu)上的改變操作時，有可能會產(chǎn)生 fail-fast 機(jī)制。
迭代器在遍歷時直接訪問集合中的內(nèi)容，并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會改變modCount的值。每當(dāng)?shù)魇褂胔ashNext()/next()遍歷下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍歷;否則拋出異常，終止遍歷。
注意：這里異常的拋出條件是檢測到 modCount!=expectedmodCount 這個條件。如果集合發(fā)生變化時修改modCount值剛好又設(shè)置為了expectedmodCount值，則異常不會拋出。因此，不能依賴于這個異常是否拋出而進(jìn)行并發(fā)操作的編程，這個異常只建議用于檢測并發(fā)修改的bug。
場景：java.util包下的集合類都是快速失敗的，不能在多線程下發(fā)生并發(fā)修改(迭代過程中被修改)。
「不用腦子的總結(jié)：我們?nèi)粘？吹降腃oncurrent Modification Exception，其實(shí)就是觸發(fā)了快速失敗機(jī)制的表現(xiàn)，做法也很簡單：在遍歷的時候給你給modCount設(shè)置個備份expectedModCount，如果有多線程在搞，那么必定會導(dǎo)致modCount被改，那么就容易了，每次遍歷的時候都檢測下modCount變量是否為expectedModCount就可以了，如果不是意味著被改了，那我就不管，我就要報錯?！?/p>
集合的安全失敗(fail-safe)
采用安全失敗機(jī)制的集合容器，在遍歷時不是直接在集合內(nèi)容上訪問的，而是先復(fù)制原有集合內(nèi)容，在拷貝的集合上進(jìn)行遍歷。
原理：由于迭代時是對原集合的拷貝進(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ā)修改。
「不用記憶的總結(jié)：那么為啥并發(fā)容器的時候不怕呢?簡單，因?yàn)椴捎昧税踩C(jī)制，在遍歷的時候直接拷貝了一份出來，這樣就不會觸發(fā)了?！?/p>
使用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)建一個內(nèi)部類SubList實(shí)例，這個SubList是AbstractList的實(shí)現(xiàn)類，并不繼承于ArrayList。
通過上面源碼可以看出，通過parent屬性指定父類并直接引用了原有的List，并返回該父類的部分視圖，只是指定了他要使用的元素的范圍fromIndex(包含)，endIndex(不包含)。
那么，如果對其原有或者子List做數(shù)據(jù)性修改，則會互相影響。如果對原有List進(jìn)行結(jié)構(gòu)性修改，則會踩坑Fast-fail，報錯會拋出異常ConcurrentModification Exception。
ArrayList迭代器
看下迭代器的遍歷和刪除相關(guān)的源碼
- 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;
- // 這里刪除后會重新復(fù)制一次
- expectedModCount = modCount;
- } catch (IndexOutOfBoundsException ex) {
- throw new ConcurrentModificationException();
- }
- }
通過代碼我們也可以看出ArrayList的迭代器是支持遍歷刪除的，因?yàn)樵趧h除后會重新賦一次值給expectedModCount。
ArrayList和LinkedList的優(yōu)劣
其實(shí)就是數(shù)組和鏈表的優(yōu)劣勢，ArrayList優(yōu)點(diǎn)，支持隨機(jī)訪問，get(i)的時間復(fù)雜度為O(1)，而缺點(diǎn)就是需要擴(kuò)容，要復(fù)制數(shù)組，而且內(nèi)部插入數(shù)據(jù)需要移動數(shù)據(jù)，插入刪除的性能差;
對于LinkedList來說，優(yōu)點(diǎn)就是容量理論上來說是無限，不存在擴(kuò)容，而且可以很方便的插入和刪除數(shù)據(jù)(性能損失在查找)，而缺點(diǎn)就是不能隨機(jī)訪問，get(i)需要遍歷。
貌似就是反過來的，所以在實(shí)際開發(fā)中也很容易區(qū)別，看是查找頻繁、還是增刪頻繁，如果是查找頻繁就用ArrayList，如果增刪頻繁就用LinkedList即可。
