原文鏈接，排版更舒適
本期是【你好，面試官】系列文章的第2期，持續更新中.....，
回復"我要進大廠"獲取思維導圖，目前還在更新中，從小白到大廠~
小龍有話說
本期會模擬面試 List 相關內容，
本期題目選自 ——2022屆春招 京東 二面
面試現場
叮叮叮......
面試官：“你好，我是XX面試官，請問是小龍嗎？”
小龍：“您好，面試官，我是小龍”
面試官：“好的，現在有空嗎，我們開始面試吧”
小龍：“嗯嗯，準備好啦”
.......
other questions
.......
面試官：“我看你簡歷上有提到熟悉Java集合相關，還看過原始碼對吧？”
小龍：“是的”
面試官：“好的，那你平時開發中經常用的集合有哪些呢？”
小龍：“嗯~，平時主要使用 Collection、Map 兩個類別的集合，Collection 下 用的比較多的是 List、Set 介面的相關實作類，Map 下用得比較多的是 HashMap、TreeMap、LinkedHashMap這些，”
面試官：“好的，我們一個一個來，你有提到 List ,那你能簡單說說什么時候用 List 嗎？”
小龍：“List 介面元素是有序的并且可重復，Set 介面元素是無序的只接收一次，具有去重性，因此我們可以結合二者的特點做出選擇，然后 List 某些實作類比如 ArryList 由于底層實作是陣列，可以支持索引下標隨機訪問，因此可以結合它的這些特性去考慮”
面試官：“好的，那你能講講你經常使用的 List 下的實作類嗎？”
小龍：“List 下比較常用的是 ArryList，LinkedList，
小龍：“ ArrayList 底層是陣列實作，由于可以支持下標訪問，查詢資料快，但是它非執行緒安全，并且在寫入資料時，由于陣列復制需要時間，并且擴容需要實體化新陣列也要時間，因此寫入資料慢，而且假如當插入元素后剛觸發擴容機制，會導致浪費很多空間，”
小龍：”我們可以看看具體內部原始碼實作，“
// 查詢元素
public E get(int index) {
rangeCheck(index); // 檢查是否越界
return elementData(index);
}
// 順序添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 擴容機制
elementData[size++] = e;
return true;
}
// 從陣列中間添加元素
public void add(int index, E element) {
rangeCheckForAdd(index); // 陣列下標越界檢查
ensureCapacityInternal(size + 1); // 擴容機制
System.arraycopy(elementData, index, elementData, index + 1, size - index); // 復制陣列
elementData[index] = element; // 替換元素
size++;
}
// 從陣列中洗掉元素
private void fastRemove(int index) {
modCount++;
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
}
?
小龍：”從原始碼中可以得知，ArrayList在執行查詢操作時：1、先判斷下標是否越界，2、然后在直接通過下標從陣列中回傳元素，“
小龍：”ArrayList在執行順序添加操作時：1、通過擴容機制判斷原陣列是否還有空間，若沒有則重新實體化一個空間更大的新陣列，把舊陣列的資料拷貝到新陣列中，2、在新陣列的最后一位元素添加值，“
小龍：”ArrayList在執行中間插入操作時：1、先判斷下標是否越界，2、擴容，3、若插入的下標為i，則通過復制陣列的方式將i后面的所有元素，往后移一位，4、新資料替換下標為 i 的舊元素，洗掉也是一樣：只是陣列往前移了一位，最后一個元素設定為 null，等待 JVM垃圾回收，“
小龍：”從上面的原始碼分析，我們可以看出 ArrayList 快在下標定位，慢在陣列復制，“
小龍：”不過，您可能會問，能否將每次擴容的長度設定大點，減少擴容的次數，從而提高效率？其實每次擴容的長度大小是很有講究的，若擴容的長度太大，會造成大量的閑置空間；若擴容的長度太小，會造成頻發的擴容(陣列復制)，效率更低“
小龍：“而 LinkedList 底層是基于鏈表，由于訪問元素需要變數鏈表導致查詢慢，寫資料、洗掉資料便只需要修改指標的指向，因此速度快，同樣它也是非執行緒安全的，”
面試官：”好的，剛才我聽你提過 ArrayList 的擴容，你能講講它的擴容機制嗎？“
獨白：”wc，這是往死里薅啊....“
小龍：”剛才我們也看過原始碼啦，可見 ArrayList 擴容：添加元素時使用 ensureCapacityInternal()方法來保證容量足夠，如果不夠時，需要使用 grow() 方法進行擴容“
小龍：”新容量的大小為 oldCapacity + (oldCapacity >> 1)，即 oldCapacity+oldCapacity/2，其中 oldCapacity >> 1 需要取整，所以新容量大約是舊容量的 1.5 倍左右，（oldCapacity 為偶數就是 1.5 倍，為奇數就是 1.5 倍-0.5）“
小龍：”擴容操作需要呼叫Arrays.copyOf() 把原陣列整個復制到新陣列中，這個操作代價很高，因此最好在創建 ArrayList 物件時就指定大概的容量大小，減少擴容操作的次數，最好會利用 modCount 記錄結構修改次數，“
面試官：”好小伙，基礎不錯，再問一下，你之前也有說這些都是非執行緒安全的，那當遇到需要考慮并發問題時，你怎么辦呢？“
獨白：”好家伙，我就知道你又要這樣問，得好我早就把八股給你準備好了，“
小龍：”談到執行緒安全，想必肯定都知道 Vector，Vector 和 ArrayList 差不多，不過它對資料操作的方法都加了synchronized，因此它是執行緒安全的，不過由于加了 synchronized，執行緒同步，導致 Vector 性能很差，“
面試官：”那有什么解決辦法嗎？“
小龍：”可以使用Collections.synchronizedList(list)方法或者使用 CopyOnWriteArrayList 集合“
面試官：”噢？還知道CopyOnWriteArrayList，不錯！那你能簡單介紹一下這個集合嗎？ “
獨白：”暈，這不是自己給自己挖坑嗎....，“
小龍：”CopyOnWriteArrayList，它是一個寫時復制的容器，何為寫時復制呢？顧名思義~“
小龍：”當我們往一個容器添加元素的時候，不是直接往當前容器添加，而是先將當前容器進行 copy一份，復制出一個新的容器，然后對新容器里面操作元素，最后將原容器的參考指向新的容器，“
小龍：”它實作了List介面，內部持有 ReentrantLock 物件，底層使用 volatile transient 宣告得陣列，能更好的處理鎖競爭問題，在并發高時，比 Vector 性能更佳，讀寫分離，寫時復制，先用 ReetrantLock 物件加鎖，然后會復制一份原陣列進行寫操作，寫完了再將新陣列值賦予原陣列，適合讀多寫少場景“
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;//寫時復制
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
面試官：”那意思就是 CopyOnWriteArrayList 就特別好嗎？“
小龍：”雙刃劍嘛，有利肯定有弊，正因為它寫時復制的特性，因此每次寫都要復制一個陣列，很耗費記憶體的，資料量大時，對記憶體壓力較大，可能會引起頻繁 GC，
小龍：”還有就是大量寫操作性能極差，所以只適合讀多寫少的，“
小龍：”并且無法保證實時性，Vector對于讀寫操作均加鎖同步，可以保證讀和寫的強一致性，而 CopyOnWriteArrayList 由于其實作策略的原因，寫和讀分別作用在新老不同容器上，在寫操作執行程序中，讀不會阻塞但讀取到的卻是老容器的資料，“
面試官：”你說無法保證實時性？何以見得呢？“
小龍：”因為 COW（CopyOnWrite）寫時復制，CopyOnWriteArrayList 讀取時不加鎖，只是寫入、洗掉、修改時加鎖，由于所有的寫操作都是在新陣列進行的，這個時候如果有執行緒并發的寫，則通過鎖來控制，如果有執行緒并發的讀，則分幾種情況，“
小龍：”1、如果寫操作未完成，那么直接讀取原陣列的資料；2、如果寫操作完成，但是參考還未指向新陣列，那么也是讀取原陣列資料；3、如果寫操作完成，并且參考已經指向了新的陣列，那么直接從新陣列中讀取資料，“
小龍：”因此，對 CopyOnWriteArrayList 進行增刪改操作，與此同時有其他執行緒來訪問 CopyOnWriteArrayList 中的元素，因為增刪改操作未完成，所以讀取元素的執行緒看不到新資料，可能會讀到臟資料，“
面試官：”此刻，我想為你豎起大拇指！！“
知識總結
本期我們通過面試模擬簡單介紹了集合，重點剖析了 List 相關集合，
面試重點
ArrayList 與 LinkedList 區別、ArrayList 擴容機制、CopyOnWriteArrayList 特點、場景、思想
-
ArrayList : 基于陣列實作的非執行緒安全的集合，實作 RandomAccess 介面，支持隨機訪問，查詢元素快，插入，洗掉中間元素慢，
-
LinkedList : 基于鏈表實作的非執行緒安全的集合，查詢元素慢，插入，洗掉中間元素快，一般情況占用空間大（維護雙指標），
-
Vector : 基于陣列實作的執行緒安全的集合，執行緒同步（方法被synchronized修飾），性能比 ArrayList 差，
-
CopyOnWriteArrayList : 基于陣列實作的執行緒安全的寫時復制集合，執行緒安全（ReentrantLock加鎖），性能比Vector高，適合讀多寫少的場景，最終一致性，
微信搜【 小龍coding】持續追更~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/413695.html
標籤：其他