1. 首頁 > 生活百科 > >

Java集合精選常見面試題( 三 )

生活百科


在 binarySearch（) 方法中，它要判斷傳入的 list 是否 RamdomAccess 的實例，如果是，調用indexedBinarySearch()方法，如果不是，那么調用iteratorBinarySearch()方法
public static <T>int binarySearch(List<? extends Comparable<? super T>> list ，  T key) {if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)return Collections.indexedBinarySearch(list，key);elsereturn Collections.iteratorBinarySearch(list，key);}ArrayList 實現了 RandomAccess 接口 ，  而 LinkedList 沒有實現 。為什么呢？我覺得還是和底層數據結構有關！ArrayList 底層是數組，而 LinkedList 底層是鏈表 。數組天然支持隨機訪問，時間復雜度為 O(1) ， 所以稱為快速隨機訪問 。鏈表需要遍歷到特定位置才能訪問特定位置的元素，時間復雜度為 O(n)，所以不支持快速隨機訪問 。，ArrayList 實現了 RandomAccess 接口，就表明了他具有快速隨機訪問功能 。RandomAccess 接口只是標識，并不是說 ArrayList 實現 RandomAccess 接口才具有快速隨機訪問功能的
3. 說一說 ArrayList 的擴容機制吧ArrayList核心源碼詳見這篇文章:通過源碼一步一步分析 ArrayList 擴容機制
先從 ArrayList 的構造函數說起（JDK8）ArrayList 有三種方式來初始化，構造方法源碼如下：
/*** 默認初始容量大小10*/private static final int DEFAULT_CAPACITY = 10;private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = https://www.huyubaike.com/biancheng/{};/***默認構造函數，使用初始容量10構造一個空列表(無參數構造)*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** 帶初始容量參數的構造函數 。（用戶自己指定容量）*/public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//初始容量大于0//創建initialCapacity大小的數組this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//初始容量等于0//創建空數組this.elementData = EMPTY_ELEMENTDATA;} else {//初始容量小于0，拋出異常throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}/***構造包含指定collection元素的列表，這些元素利用該集合的迭代器按順序返回*如果指定的集合為null，throws NullPointerException 。*/public ArrayList(Collection<? extends E> c) {elementData = https://www.huyubaike.com/biancheng/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;}}細心的同學一定會發現 ：以無參數構造方法創建 ArrayList 時，實際上初始化賦值的是一個空數組 。當真正對數組進行添加元素操作時，才真正分配容量 。即向數組中添加第一個元素時，數組容量擴為 10 。下面在我們分析 ArrayList 擴容時會講到這一點內容！

補充：JDK6 new 無參構造的 ArrayList 對象時，直接創建了長度是 10 的 Object[] 數組 elementData
add()
/*** 將指定的元素追加到此列表的末尾 。*/public boolean add(E e) {//添加元素之前，先調用ensureCapacityInternal方法ensureCapacityInternal(size + 1);// Increments modCount!!//這里看到ArrayList添加元素的實質就相當于為數組賦值elementData[size++] = e;return true;}ensureCapacityInternal()
（JDK7）可以看到 add 方法 首先調用了ensureCapacityInternal(size + 1)
//得到最小擴容量private void ensureCapacityInternal(int minCapacity) {if (elementData =https://www.huyubaike.com/biancheng/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 獲取默認的容量和傳入參數的較大值minCapacity = Math.max(DEFAULT_CAPACITY ， minCapacity);}ensureExplicitCapacity(minCapacity);}如果調用 ensureCapacityInternal() 方法就一定會進入（執行）這個方法 ， 下面我們來研究一下這個方法的源碼！
//判斷是否需要擴容private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)//調用grow方法進行擴容，調用此方法代表已經開始擴容了grow(minCapacity);}仔細分析一下：