底層數(shù)據(jù)結(jié)構(gòu)

Collection

List：（有序，可重復(fù)）

• ArrayList：Object數(shù)組

• Vector： Object數(shù)組

• LinkedList：雙向鏈表（JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)），更擅長進(jìn)行插入、刪除、修改等操作

Set：

• HashSet（無序，唯一）：基于HashMap實(shí)現(xiàn)的，底層采用HashMap來保存元素

• LinkedHashSet：LinkedHashSet繼承于HashSet，并且其內(nèi)部是通過LinkedHashMap來實(shí)現(xiàn)的。

• TreeSet（有序，唯一）：紅黑樹（自平衡的排序二叉樹）。

唯一性:是要靠元素重寫HashCode()和equals()方法,如果不重寫則無法保證元素唯一

Map

• HashMap：JDK1.8之前HashMap是由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解哈希沖突而存在的（“拉鏈法”解決哈希沖突）。JDK1.8之后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長度大于閾值（默認(rèn)為8）并且數(shù)組長度大于64時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間

注意：如果鏈表長度大于閾值（默認(rèn)為8）時(shí)并且數(shù)組的長度小于64時(shí)，鏈表不會(huì)轉(zhuǎn)換為紅黑樹，而是將數(shù)組進(jìn)行擴(kuò)容。這樣做的目的考慮到數(shù)組的長度較小，盡量避開紅黑樹，這種情況下，轉(zhuǎn)為紅黑樹，反而會(huì)降低效率問題，因?yàn)榧t黑樹需要左旋，右旋，變色操作來保持平衡，所以當(dāng)數(shù)組長度小于64，搜索時(shí)間會(huì)相對(duì)快些，考慮到性能和減少搜索的時(shí)間，只有當(dāng)鏈表長度大于閾值（默認(rèn)為8）時(shí)并且數(shù)組的長度大于64時(shí)，鏈表將會(huì)轉(zhuǎn)換為紅黑樹。

• LinkedHashMap：LinkedHashMap繼承自HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap在上面結(jié)構(gòu)的基礎(chǔ)上，增加一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對(duì)的插入順序。同時(shí)通過對(duì)鏈表進(jìn)行相應(yīng)的操作，實(shí)現(xiàn)了訪問順序相關(guān)邏輯。

• TreeMap：紅黑樹（自平衡的排序二叉樹）。

• Hashtable：數(shù)組+鏈表組成的，數(shù)組是Hashtable的主體，鏈表則是主要為了解決哈希沖突而存在的

擴(kuò)容機(jī)制

ArrayList

以無參構(gòu)造方法創(chuàng)建ArrayList時(shí)，實(shí)際上初始化賦值的是一個(gè)空數(shù)組。當(dāng)真正對(duì)數(shù)組進(jìn)行添加元素操作時(shí)，才真正分配容量。即向數(shù)組中添加第一個(gè)元素時(shí)，數(shù)組容量擴(kuò)為10。

  /**
   * Default initial capacity.
   */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * Shared empty array instance used for empty instances.
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

因?yàn)樵谠创a中，int newCapacity = oldCapacity + (oldCapacity >> 1)，所以ArrayList每次擴(kuò)容之后容量都會(huì)變?yōu)樵瓉淼?.5倍。

  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

ArrayList擴(kuò)容的核心方法grow( )，下面將針對(duì)三種情況對(duì)該方法進(jìn)行解析：

1. 當(dāng)前數(shù)組是由默認(rèn)構(gòu)造方法生成的空數(shù)組并且第一次添加數(shù)據(jù)。此時(shí)minCapacity等于默認(rèn)的容量（10）那么根據(jù)下面邏輯可以看到最后數(shù)組的容量會(huì)從0擴(kuò)容成10。而后的數(shù)組擴(kuò)容才是按照當(dāng)前容量的1.5倍進(jìn)行擴(kuò)容；

2. 當(dāng)前數(shù)組是由自定義初始容量構(gòu)造方法創(chuàng)建并且指定初始容量為0。此時(shí)minCapacity等于1那么根據(jù)下面邏輯可以看到最后數(shù)組的容量會(huì)從0變成1。這邊可以看到一個(gè)嚴(yán)重的問題，一旦我們執(zhí)行了初始容量為0，那么根據(jù)下面的算法前四次擴(kuò)容每次都 +1，在第5次添加數(shù)據(jù)進(jìn)行擴(kuò)容的時(shí)候才是按照當(dāng)前容量的1.5倍進(jìn)行擴(kuò)容。

3. 當(dāng)擴(kuò)容量（newCapacity）大于ArrayList數(shù)組定義的最大值后會(huì)調(diào)用hugeCapacity來進(jìn)行判斷。如果minCapacity已經(jīng)大于Integer的最大值（溢出為負(fù)數(shù)）那么拋出OutOfMemoryError（內(nèi)存溢出）否則的話根據(jù)與MAX_ARRAY_SIZE的比較情況確定是返回Integer最大值還是MAX_ARRAY_SIZE。這邊也可以看到1. ArrayList允許的最大容量就是Integer的最大值（-2的31次方~2的31次方減1）。

  private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

HashMap

• capacity 即容量，默認(rèn)16。

• loadFactor 加載因子，默認(rèn)是0.75

• threshold 閾值。閾值=容量*加載因子。默認(rèn)12。當(dāng)元素?cái)?shù)量超過閾值時(shí)便會(huì)觸發(fā)擴(kuò)容。

什么時(shí)候觸發(fā)擴(kuò)容？

一般情況下，當(dāng)元素?cái)?shù)量超過閾值時(shí)便會(huì)觸發(fā)擴(kuò)容。每次擴(kuò)容的容量都是之前容量的2倍。

HashMap的容量是有上限的，必須小于2^30，即1073741824。如果容量超出了這個(gè)數(shù)，則不再增長，且閾值會(huì)被設(shè)置為Integer.MAX_VALUE（ [圖片上傳失敗...(image-44e830-1602040324581)]

，即永遠(yuǎn)不會(huì)超出閾值了）。

JDK8的擴(kuò)容機(jī)制

JDK8的擴(kuò)容做了許多調(diào)整。

HashMap的容量變化通常存在以下幾種情況：

1. 空參數(shù)的構(gòu)造函數(shù)：實(shí)例化的HashMap默認(rèn)內(nèi)部數(shù)組是null，即沒有實(shí)例化。第一次調(diào)用put方法時(shí)，則會(huì)開始第一次初始化擴(kuò)容，長度為16。

2. 有參構(gòu)造函數(shù)：用于指定容量。會(huì)根據(jù)指定的正整數(shù)找到不小于指定容量的2的冪數(shù)，將這個(gè)數(shù)設(shè)置賦值給閾值（threshold）。第一次調(diào)用put方法時(shí)，會(huì)將閾值賦值給容量，然后讓閾值=容量×負(fù)載因子。（因此并不是我們手動(dòng)指定了容量就一定不會(huì)觸發(fā)擴(kuò)容，當(dāng)元素?cái)?shù)量超過閾值后一樣會(huì)擴(kuò)容?。。?/p>

3. 如果不是第一次擴(kuò)容，則容量變?yōu)樵瓉淼?倍，閾值也變?yōu)樵瓉淼?倍。（容量和閾值都變?yōu)樵瓉淼?倍時(shí)，負(fù)載因子還是不變）

此外還有幾個(gè)細(xì)節(jié)需要注意：

• 首次put時(shí)，先會(huì)觸發(fā)擴(kuò)容（算是初始化），然后存入數(shù)據(jù)，然后判斷是否需要擴(kuò)容；

• 不是首次put，則不再初始化，直接存入數(shù)據(jù)，然后判斷是否需要擴(kuò)容；

List集合的四種遍歷方式

//(1)集合的迭代器遍歷。
 Iterator<String> it=list.iterator();
 while (it.hasNext())
     System.out.println(it.next());

 System.out.println("===================");

 //(2)使用增強(qiáng)for循環(huán)遍歷
 for (String ele:list)
     System.out.println(ele);

 System.out.println("===================");

 //(3)使用JDK1.8后的新技術(shù)，lambda表達(dá)式。
 list.forEach(e-> System.out.println(e));

 System.out.println("===================");

 //(4)for循環(huán)結(jié)合索引遍歷

 for (int i = 0; i <list.size() ; i++) {
     System.out.print(list.get(i)+" ");
 }
 System.out.println();

ArrayList和LinkedList的區(qū)別是什么？為什么要用ArrayList取代Vector？

ArrayList與LinkedList的區(qū)別

1. 是否保證線程安全：ArrayList和LinkedList都是不同步的，也就是不保證線程安全

2. 底層數(shù)據(jù)結(jié)構(gòu)：ArrayList底層使用的是Object數(shù)組；LinkedList底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別，下面有介紹到）

3. 插入和刪除是否受元素位置的影響：① ArrayList采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。比如：執(zhí)行add(E e)方法的時(shí)候，ArrayList會(huì)默認(rèn)在指定的元素追加到此列表的末尾，這種情況的時(shí)間復(fù)雜度就是O(1)。但是如果要在指定位置i插入和刪除元素的話(add ( int index, E element))時(shí)間復(fù)雜度就是O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第i和第i個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作。② LinkedList采用鏈表存儲(chǔ)，所以對(duì)于add(E e)方法的插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，近似O(1)，如果是要在指定位置i插入和刪除元素的話，(add ( int index, E element))時(shí)間復(fù)雜度近似為O(n)，因?yàn)樾枰纫苿?dòng)到指定位置再插入。

4. 是否支持快速隨機(jī)訪問：LinkedList不支持高效的隨機(jī)元素訪問，而ArrayList支持。快速隨機(jī)訪問就是通過元素的序號(hào)快速獲取元素對(duì)象（對(duì)應(yīng)于get(int index) 方法）。

5. 內(nèi)存空間占用：ArrayList的空間浪費(fèi)主要體現(xiàn)在 在list列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而LinkedList的容量空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比ArrayList更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。

ArrayList取代Vector的原因

Vector類的索引方法都是同步的?？梢杂袃蓚€(gè)線程安全地訪問一個(gè)Vector對(duì)象，但是一個(gè)線程訪問Vector的話代碼要在同步操作上耗費(fèi)大量時(shí)間。

ArrayList不是同步的，所以不需要保證線程安全時(shí)建議使用ArrayList

HashMap與Hashtable的區(qū)別

1. 線程是否安全：HashMap是非線程安全的，Hashtable是線程安全的；Hashtable內(nèi)部的方法基本都經(jīng)過synchronized修飾。（如果一定要保證線程安全的話可以使用ConcurrentHash）；

2. 效率：因?yàn)榫€程安全的問題，HashMap要比Hashtable效率高一點(diǎn)。另外，Hashtable基本被淘汰，不要在代碼中使用它；

3. 對(duì) Null key 和 Null value 的支持：HashMap中，null可以作為鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null。但是在Hashtable中put進(jìn)的鍵值只要有一個(gè)null，就直接拋出 NullPointerException。

4. 初始容量大小和每次擴(kuò)容量大小的不同： ① 創(chuàng)建時(shí)如果不指定容量初始值，Hashtable默認(rèn)的初始大小為11，之后每次擴(kuò)容，容量變?yōu)樵瓉淼?n+1。HashMap默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉淼?倍。② 創(chuàng)建時(shí)如果給定了容量初始值，那么Hashtable會(huì)直接使用你給定的大小，而HashMap會(huì)將其擴(kuò)充為2的冪次方大小。也就是說HashMap總是使用2的冪次方作為哈希表的大小。

5. 底層數(shù)據(jù)結(jié)構(gòu)：JDK1.8以后的HashMap在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，以減少搜索時(shí)間。Hashtable沒有這樣的機(jī)制。

List、Set、Map三者的區(qū)別

• List（有序、重復(fù)）：

  List接口存儲(chǔ)一組不唯一（可以有多個(gè)元素引用相同的對(duì)象），有序的對(duì)象

• Set（無序、不重復(fù)）：

  不允許重復(fù)的集合。不會(huì)有多個(gè)元素引用相同的對(duì)象。

• Map（KV鍵值對(duì)集合）：

  使用鍵值對(duì)來存儲(chǔ)。Map會(huì)維護(hù)與Key有關(guān)聯(lián)的值。兩個(gè)Key可以引用相同的對(duì)象。但Key不能重復(fù)，典型的Key是String類型，但也可以是任何對(duì)象。

RandomAccess接口

public interface RandomAccess {
}

通過查看源碼可以發(fā)現(xiàn)實(shí)際上RandomAccess接口中什么都沒有定義。所以我認(rèn)為RandomAccess接口只是一個(gè)標(biāo)識(shí)，標(biāo)識(shí)實(shí)現(xiàn)這個(gè)接口的類具有隨機(jī)訪問功能。

在binarySearch( ) 方法中，它要判斷傳入的list是否為RandomAccess接口的實(shí)現(xiàn)類的實(shí)例，如果是，調(diào)用indexBinarySearch( )方法，如果不是，則調(diào)用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);
        else
            return Collections.iteratorBinarySearch(list, key);
}

ArrayList實(shí)現(xiàn)了RandomAccess接口，而LinkedList沒有實(shí)現(xiàn)。是什么原因？

我認(rèn)為還是與底層數(shù)據(jù)結(jié)構(gòu)有關(guān)。ArrayList底層是數(shù)組，而LinkedList底層是鏈表。數(shù)組天然支持隨機(jī)訪問，時(shí)間復(fù)雜度為O(1)，所以稱為快速隨機(jī)訪問。鏈表需要遍歷到特定位置才能訪問到特定位置的元素，時(shí)間復(fù)雜度為O(n)，所以不支持快速隨機(jī)訪問。ArrayList實(shí)現(xiàn)了RandomAccess接口，就表明了他具有快速隨機(jī)訪問功能。RandomAccess接口只是標(biāo)識(shí)，并不是說ArrayList實(shí)現(xiàn)RandomAccess接口才具有快速隨機(jī)訪問功能的！

ConcurrentHashMap

ConcurrentHashMap中的分段鎖稱為Segment，它即類似于HashMap（JDK7與JDK8中HashMap的實(shí)現(xiàn)）的結(jié)構(gòu)，即內(nèi)部擁有一個(gè)Entry數(shù)組，數(shù)組中的每個(gè)元素又是一個(gè)鏈表；同時(shí)又是一個(gè)ReentrantLock（Segment繼承了ReentrantLock)。

當(dāng)需要put元素的時(shí)候，并不是對(duì)整個(gè)hashmap進(jìn)行加鎖，而是先通過hashcode來知道他要放在那一個(gè)分段中，然后對(duì)這個(gè)分段進(jìn)行加鎖，所以當(dāng)多線程put的時(shí)候，只要不是放在一個(gè)分段中，就實(shí)現(xiàn)了真正的并行的插入。

但是，在統(tǒng)計(jì)size的時(shí)候，可就是獲取hashmap全局信息的時(shí)候，就需要獲取所有的分段鎖才能統(tǒng)計(jì)。

分段鎖的設(shè)計(jì)目的是細(xì)化鎖的粒度，當(dāng)操作不需要更新整個(gè)數(shù)組的時(shí)候，就僅僅針對(duì)數(shù)組中的一項(xiàng)進(jìn)行加鎖操作。

舉個(gè)直觀一點(diǎn)的例子：

既然不能全鎖（HashTable）又不能不鎖（HashMap），所以就搞個(gè)部分鎖，只鎖部分，用到哪部分就鎖哪部分。一個(gè)大倉庫，里面有若干個(gè)隔間，每個(gè)隔間都有鎖，同時(shí)只允許一個(gè)人進(jìn)隔間存取東西。但是，在存取東西之前，需要有一個(gè)全局索引，告訴你要操作的資源在哪個(gè)隔間里，然后當(dāng)你看到隔間空閑時(shí)，就可以進(jìn)去存取，如果隔間正在占用，那你就得等著。

comparable 和 Comparator 的區(qū)別

1. comparable 接口實(shí)際上是出自java.lang包 它有一個(gè) compareTo(Object obj)方法用來排序

   comparator接口實(shí)際上是出自 java.util 包它有一個(gè)compare(Object obj1, Object obj2)方法用來排序

2. Comparable是排序接口，若一個(gè)類實(shí)現(xiàn)了Comparable接口，就意味著“該類支持排序”。而Comparator是比較器，我們?nèi)粜枰刂颇硞€(gè)類的次序，可以建立一個(gè)“該類的比較器”來進(jìn)行排序。

3. Comparable相當(dāng)于“內(nèi)部比較器”，而Comparator相當(dāng)于“外部比較器”。

   兩種方法各有優(yōu)劣， 用Comparable 簡(jiǎn)單， 只要實(shí)現(xiàn)Comparable 接口的對(duì)象直接就成為一個(gè)可以比較的對(duì)象，但是需要修改源代碼。 用Comparator 的好處是不需要修改源代碼， 而是另外實(shí)現(xiàn)一個(gè)比較器， 當(dāng)某個(gè)自定義的對(duì)象需要作比較的時(shí)候，把比較器和對(duì)象一起傳遞過去就可以比大小了， 并且在Comparator 里面用戶可以自己實(shí)現(xiàn)復(fù)雜的可以通用的邏輯，使其可以匹配一些比較簡(jiǎn)單的對(duì)象，那樣就可以節(jié)省很多重復(fù)勞動(dòng)了（靈活，擴(kuò)展性強(qiáng)）。