Java最全面試題專題---2、Java集合容器（2）

Map接口

說一下 HashMap 的實現原理？

HashMap概述： HashMap是基于哈希表的Map接口的非同步實現。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。

HashMap的數據結構：在Java編程語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針（引用），所有的數據結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結合體。

HashMap 基于 Hash 算法實現的

當我們往Hashmap中put元素時，利用key的hashCode重新hash計算出當前對象的元素在數組中的下標
存儲時，如果出現hash值相同的key，此時有兩種情況。(1)如果key相同，則覆蓋原始值；(2)如果key不同（出現沖突），則將當前的key-value放入鏈表中
獲取時，直接找到hash值對應的下標，在進一步判斷key是否相同，從而找到對應值。
理解了以上過程就不難明白HashMap是如何解決hash沖突的問題，核心就是使用了數組的存儲方式，然后將沖突的key的對象放入鏈表中，一旦發現沖突就在鏈表中做進一步的對比。

需要注意Jdk 1.8中對HashMap的實現做了優化，當鏈表中的節點數據超過八個之后，該鏈表會轉為紅黑樹來提高查詢效率，從原來的O(n)到O(logn)

HashMap在JDK1.7和JDK1.8中有哪些不同？

HashMap的底層實現

在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。數組的特點是：尋址容易，插入和刪除困難；鏈表的特點是：尋址困難，但插入和刪除容易；所以我們將數組和鏈表結合在一起，發揮兩者各自的優勢，使用一種叫做拉鏈法的方式可以解決哈希沖突。

JDK1.8之前

JDK1.8之前采用的是拉鏈法。拉鏈法：將鏈表和數組相結合。也就是說創建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。

JDK1.8之后

相比于之前的版本，jdk1.8在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。

JDK1.7 VS JDK1.8 比較

DK1.8主要解決或優化了一下問題：

resize 擴容優化
引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率，紅黑樹算法請參考
解決了多線程死循環問題，但仍是非線程安全的，多線程時可能會造成數據丟失問題。

HashMap的put方法的具體流程？

當我們put的時候，首先計算 key的hash值，這里調用了 hash方法，hash方法實際是讓key.hashCode()與key.hashCode()>>>16進行異或操作，高16bit補0，一個數和0異或不變，所以 hash 函數大概的作用就是：高16bit不變，低16bit和高16bit做了一個異或，目的是減少碰撞。按照函數注釋，因為bucket數組大小是2的冪，計算下標index = (table.length - 1) & hash，如果不做 hash 處理，相當于散列生效的只有幾個低 bit 位，為了減少散列的碰撞，設計者綜合考慮了速度、作用、質量之后，使用高16bit和低16bit異或來簡單處理減少碰撞，而且JDK8中用了復雜度 O（logn）的樹結構來提升碰撞下的性能。

putVal方法執行流程圖
在這里插入圖片描述

1 public V put(K key, V value) {
2 return putVal(hash(key), key, value, false, true);
3 }
4
5 static final int hash(Object key) {
6 int h;
7 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
8 }
9
10 //實現Map.put和相關方法
11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12 boolean evict) {
13 Node<K,V>[] tab; Node<K,V> p; int n, i;
14 // 步驟①：tab為空則創建
15 // table未初始化或者長度為0，進行擴容
16 if ((tab = table) == null || (n = tab.length) == 0)
17 n = (tab = resize()).length;
18 // 步驟②：計算index，并對null做處理
19 // (n ‐ 1) & hash 確定元素存放在哪個桶中，桶為空，新生成結點放入桶中(此時，這
個結點是放在數組中)
20 if ((p = tab[i = (n ‐ 1) & hash]) == null)
21 tab[i] = newNode(hash, key, value, null);
22 // 桶中已經存在元素
23 else {
24 Node<K,V> e; K k;
25 // 步驟③：節點key存在，直接覆蓋value
26 // 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
27 if (p.hash == hash &&
28 ((k = p.key) == key || (key != null && key.equals(k))))
29 // 將第一個元素賦值給e，用e來記錄
30 e = p;
31 // 步驟④：判斷該鏈為紅黑樹
32 // hash值不相等，即key不相等；為紅黑樹結點
33 // 如果當前元素類型為TreeNode，表示為紅黑樹，putTreeVal返回待存放的node, e可
能為null
34 else if (p instanceof TreeNode)
35 // 放入樹中
36 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
37 // 步驟⑤：該鏈為鏈表
38 // 為鏈表結點
39 else {
40 // 在鏈表最末插入結點
41 for (int binCount = 0; ; ++binCount) {
42 // 到達鏈表的尾部
43
44 //判斷該鏈表尾部指針是不是空的
45 if ((e = p.next) == null) {
46 // 在尾部插入新結點
47 p.next = newNode(hash, key, value, null);
48 //判斷鏈表的長度是否達到轉化紅黑樹的臨界值，臨界值為8
49 if (binCount >= TREEIFY_THRESHOLD ‐ 1) // ‐1 for 1st
50 //鏈表結構轉樹形結構
51 treeifyBin(tab, hash);
52 // 跳出循環
53 break;
54 }
55 // 判斷鏈表中結點的key值與插入的元素的key值是否相等
56 if (e.hash == hash &&
57 ((k = e.key) == key || (key != null && key.equals(k))))
58 // 相等，跳出循環
59 break;
60 // 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表
61 p = e;
62 }
63 }
64 //判斷當前的key已經存在的情況下，再來一個相同的hash值、key值時，返回新來的val
ue這個值
65 if (e != null) {
66 // 記錄e的value
67 V oldValue = e.value;
68 // onlyIfAbsent為false或者舊值為null
69 if (!onlyIfAbsent || oldValue == null)
70 //用新值替換舊值
71 e.value = value;
72 // 訪問后回調
73 afterNodeAccess(e);
74 // 返回舊值
75 return oldValue;
76 }
77 }
78 // 結構性修改
79 ++modCount;
80 // 步驟⑥：超過最大容量就擴容
81 // 實際大小大于閾值則擴容
82 if (++size > threshold)
83 resize();
84 // 插入后回調
85 afterNodeInsertion(evict);
86 return null;
87 }

①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；
②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向⑥，如果table[i]不為空，轉向③；
③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向
④，這里的相同指的是hashCode以及equals；
④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；
⑤.遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可；
⑥.插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。

HashMap的擴容操作是怎么實現的？

①.在jdk1.8中，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就調用resize方法進行擴容；
②.每次擴展的時候，都是擴展2倍；
③.擴展后Node對象的位置要么在原位置，要么移動到原偏移量兩倍的位置。在putVal()中，我們看到在這個函數里面使用到了2次resize()方法，resize()方法表示的在進行第一次初始化時會對其進行擴容，或者當該數組的實際大小大于其臨界值值(第一次為12),這個時候在擴容的同時也會伴隨的桶上面的元素進行重新分發，這也是JDK1.8版本的一個優化的地方，在1.7中，擴容之后需要重新去計算其Hash值，根據Hash值對其進行分發，但在1.8版本中，則是根據在同一個桶的位置中進行判斷(e.hash & oldCap)是否為0，重新進行hash分配后，該元素的位置要么停留在原始位置，要么移動到原始位置+增加的數組大小這個位置上

1 final Node<K,V>[] resize() {
2 Node<K,V>[] oldTab = table;//oldTab指向hash桶數組
3 int oldCap = (oldTab == null) ? 0 : oldTab.length;
4 int oldThr = threshold;
5 int newCap, newThr = 0;
6 if (oldCap > 0) {//如果oldCap不為空的話，就是hash桶數組不為空
7 if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就賦值為整數最大的閥
值
8 threshold = Integer.MAX_VALUE;
9 return oldTab;//返回
10 }//如果當前hash桶數組的長度在擴容后仍然小于最大容量 并且oldCap大于默認值16
11 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
12 oldCap >= DEFAULT_INITIAL_CAPACITY)
13 newThr = oldThr << 1; // double threshold 雙倍擴容閥值threshold
14 }
15 // 舊的容量為0，但threshold大于零，代表有參構造有cap傳入，threshold已經被初
始化成最小2的n次冪
16 // 直接將該值賦給新的容量
17 else if (oldThr > 0) // initial capacity was placed in threshold
18 newCap = oldThr;
19 // 無參構造創建的map，給出默認容量和threshold 16, 16*0.75
20 else { // zero initial threshold signifies using defaults
21 newCap = DEFAULT_INITIAL_CAPACITY;
22 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
23 }
24 // 新的threshold = 新的cap * 0.75
25 if (newThr == 0) {
26 float ft = (float)newCap * loadFactor;
27 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
28 (int)ft : Integer.MAX_VALUE);
29 }
30 threshold = newThr;
31 // 計算出新的數組長度后賦給當前成員變量table
32 @SuppressWarnings({"rawtypes","unchecked"})
33 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶數組
34 table = newTab;//將新數組的值復制給舊的hash桶數組
35 // 如果原先的數組沒有初始化，那么resize的初始化工作到此結束，否則進入擴容元素
重排邏輯，使其均勻的分散
36 if (oldTab != null) {
37 // 遍歷新數組的所有桶下標
38 for (int j = 0; j < oldCap; ++j) {
39 Node<K,V> e;
40 if ((e = oldTab[j]) != null) {
41 // 舊數組的桶下標賦給臨時變量e，并且解除舊數組中的引用，否則就數組無法被GC回收
42 oldTab[j] = null;
43 // 如果e.next==null，代表桶中就一個元素，不存在鏈表或者紅黑樹
44 if (e.next == null)
45 // 用同樣的hash映射算法把該元素加入新的數組
46 newTab[e.hash & (newCap ‐ 1)] = e;
47 // 如果e是TreeNode并且e.next!=null，那么處理樹中元素的重排
48 else if (e instanceof TreeNode)
49 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
50 // e是鏈表的頭并且e.next!=null，那么處理鏈表中元素重排
51 else { // preserve order
52 // loHead,loTail 代表擴容后不用變換下標，見注1
53 Node<K,V> loHead = null, loTail = null;
54 // hiHead,hiTail 代表擴容后變換下標，見注1
55 Node<K,V> hiHead = null, hiTail = null;
56 Node<K,V> next;
57 // 遍歷鏈表
58 do {
59 next = e.next;
60 if ((e.hash & oldCap) == 0) {
61 if (loTail == null)
62 // 初始化head指向鏈表當前元素e，e不一定是鏈表的第一個元素，初始化后loHead
63 // 代表下標保持不變的鏈表的頭元素
64 loHead = e;
65 else
66 // loTail.next指向當前e
67 loTail.next = e;
68 // loTail指向當前的元素e
69 // 初始化后，loTail和loHead指向相同的內存，所以當loTail.next指向下一個元素
時，
70 // 底層數組中的元素的next引用也相應發生變化，造成lowHead.next.next.....
71 // 跟隨loTail同步，使得lowHead可以鏈接到所有屬于該鏈表的元素。
72 loTail = e;
73 }
74 else {
75 if (hiTail == null)
76 // 初始化head指向鏈表當前元素e, 初始化后hiHead代表下標更改的鏈表頭元素
77 hiHead = e;
78 else
79 hiTail.next = e;
80 hiTail = e;
81 }
82 } while ((e = next) != null);
83 // 遍歷結束, 將tail指向null，并把鏈表頭放入新數組的相應下標，形成新的映射。
84 if (loTail != null) {
85 loTail.next = null;
86 newTab[j] = loHead;
87 }
88 if (hiTail != null) {
89 hiTail.next = null;
90 newTab[j + oldCap] = hiHead;
91 }
92 }
93 }
94 }
95 }
96 return newTab;
97 }

HashMap是怎么解決哈希沖突的？

答：在解決這個問題之前，我們首先需要知道什么是哈希沖突，而在了解哈希沖
突之前我們還要知道什么是哈希才行；

什么是哈希？

Hash，一般翻譯為“散列”，也有直接音譯為“哈希”的，這就是把任意長度的輸入通過散列算法，變換成固定長度的輸出，該輸出就是散列值（哈希值）；

這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

所有散列函數都有如下一個基本特性**：根據同一散列函數計算出的散列值如果
不同，那么輸入值肯定也不同。但是，根據同一散列函數計算出的散列值如果相
同，輸入值不一定相同**。

什么是哈希沖突？

當兩個不同的輸入值，根據同一散列函數計算出相同的散列值的現象，我們就把它叫做碰撞（哈希碰撞）。

HashMap的數據結構

在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。數組的特點是：尋址容易，插入和刪除困難；鏈表的特點是：尋址困難，但插入和刪除容易；所以我們將數組和鏈表結合在一起，發揮兩者各自的優勢，使用一種叫做鏈地址法的方式可以解決哈希沖突：
在這里插入圖片描述
這樣我們就可以將擁有相同哈希值的對象組織成一個鏈表放在hash值所對應的bucket下，但相比于hashCode返回的int類型，我們HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要遠小于int類型的范圍，所以我們如果只是單純的用hashCode取余來獲取對應的bucket這將會大大增加哈希碰撞的概率，并且最壞情況下還會將HashMap變成一個單鏈表，所以我們還需要對hashCode作一定的優化

hash()函數

上面提到的問題，主要是因為如果使用hashCode取余，那么相當于參與運算的只有hashCode的低位，高位是沒有起到任何作用的，所以我們的思路就是讓hashCode取值出的高位也參與運算，進一步降低hash碰撞的概率，使得數據分布更平均，我們把這樣的操作稱為擾動，在JDK 1.8中的hash()函數如下：

1 static final int hash(Object key) {
2 int h;
3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 與自己右
移16位進行異或運算（高低位異或）
4 }

這比在JDK 1.7中，更為簡潔，相比在1.7中的4次位運算，5次異或運算（9次
擾動），在1.8中，只進行了1次位運算和1次異或運算（2次擾動）；

JDK1.8新增紅黑樹

通過上面的鏈地址法（使用散列表）和擾動函數我們成功讓我們的數據分布更平均，哈希碰撞減少，但是當我們的HashMap中存在大量數據時，加入我們某個bucket下對應的鏈表有n個元素，那么遍歷時間復雜度就為O(n)，為了針對這個問題，JDK1.8在HashMap中新增了紅黑樹的數據結構，進一步使得遍歷復雜度降低至O(logn)；

總結

簡單總結一下HashMap是使用了哪些方法來有效解決哈希沖突的：

使用鏈地址法（使用散列表）來鏈接擁有相同hash值的數據；
使用2次擾動函數（hash函數）來降低哈希沖突的概率，使得數據分布更平均；
引入紅黑樹進一步降低遍歷的時間復雜度，使得遍歷更快；

能否使用任何類作為 Map 的 key？

可以使用任何類作為 Map 的 key，然而在使用之前，需要考慮以下幾點：

如果類重寫了 equals() 方法，也應該重寫 hashCode() 方法。
類的所有實例需要遵循與 equals() 和hashCode() 相關的規則。
如果一個類沒有使用 equals()，不應該在 hashCode() 中使用它。
用戶自定義 Key類最佳實踐是使之為不可變的，這樣 hashCode() 值

可以被緩存起來，擁有更好的性能。不可變的類也可以確保 hashCode()和 equals() 在未來不會改變，這樣就會解決與可變相關的問題了。

為什么HashMap中String、Integer這樣的包裝類適合作為K？

答：String、Integer等包裝類的特性能夠保證Hash值的不可更改性和計算準確性，能夠有效的減少Hash碰撞的幾率

都是final類型，即不可變性，保證key的不可更改性，不會存在獲取hash值不同的情況
內部已重寫了equals()、hashCode()等方法，遵守了HashMap內部的規范（不清楚可以去上面看看putValue的過程），不容易出現Hash值計算錯誤的情況；

如果使用Object作為HashMap的Key，應該怎么辦呢？

答：重寫hashCode()和equals()方法

重寫hashCode()是因為需要計算存儲數據的存儲位置，需要注意不要試圖從散列碼計算中排除掉一個對象的關鍵部分來提高性能，這樣雖然能更快但可能會導致更多的Hash碰撞；
重寫equals()方法，需要遵守自反性、對稱性、傳遞性、一致性以及對于任何非null的引用值x，x.equals(null)必須返回false的這幾個特性，目的是為了保證key在哈希表中的唯一性；

HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？

答：hashCode()方法返回的是int整數類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有40億個映射空間，而HashMap的容量范圍是在16（初始化默認值）~2 ^30，HashMap通常情況下是取不到最大值的，并且設備上也難以提供這么多的存儲空間，從而導致通過hashCode()計算出的哈希值可能不在數組大小范圍內，進而無法匹配存儲位置；

那怎么解決呢？

HashMap自己實現了自己的hash()方法，通過兩次擾動使得它自己的哈希值高低位自行進行異或運算，降低哈希碰撞概率也使得數據分布更平均；
在保證數組長度為2的冪次方的時候，使用hash()運算之后的值與運算（&）（數組長度 - 1）來獲取數組下標的方式進行存儲，這樣一來是比取余操作更加有效率，二來也是因為只有當數組長度為2的冪次方時，h&(length-1)才等價于h%length，三來解決了“哈希值與數組大小范圍不匹配”的問題；

HashMap 的長度為什么是2的冪次方

為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數據分配均勻，每個鏈表/紅黑樹長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的算法。

這個算法應該如何設計呢？

我們首先可能會想到采用%取余的操作來實現。但是，重點來了：“取余(%)操作中如果除數是2的冪次則等價于與其除數減一的與(&)操作（也就是說hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且采用二進制位操作 &，相對于%能夠提高運算效率，這就解釋了 HashMap的長度為什么是2的冪次方。

那為什么是兩次擾動呢？

答：這樣就是加大哈希值低位的隨機性，使得分布更均勻，從而提高對應數組存儲下標位置的隨機性&均勻性，最終減少Hash沖突，兩次就夠了，已經達到了高位低位同時參與運算的目的；

HashMap 與 HashTable 有什么區別？

線程安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內部的方法基本都經過 synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）；
效率：因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；
對Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。但是在HashTable 中 put 進的鍵值只要有一個 null，直接拋NullPointerException。
4.初始容量大小和每次擴充容量大小的不同： ①創建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之后每次擴充，容量變為原來的2n+1。HashMap 默認的初始化大小為16。之后每次擴充，容量變為原來的2倍。②創建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大小。也就是說 HashMap 總是使用2的冪作為哈希表的大小，后面會介紹到為什么是2的冪次方。
底層數據結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。
推薦使用：在 Hashtable 的類注釋可以看到，Hashtable 是保留類不建議使用，推薦在單線程環境下使用 HashMap 替代，如果需要多線程使用則用 ConcurrentHashMap 替代。

如何決定使用 HashMap 還是TreeMap？

對于在Map中插入、刪除和定位元素這類操作，HashMap是最好的選擇。然而，假如你需要對一個有序的key集合進行遍歷，TreeMap是更好的選擇。基于你的collection的大小，也許向HashMap中添加元素會更快，將map換為TreeMap進行有序key的遍歷。

HashMap 和 ConcurrentHashMap 的區別

ConcurrentHashMap對整個桶數組進行了分割分段(Segment)，然后在每一個分段上都用lock鎖進行保護，相對于HashTable的synchronized鎖的粒度更精細了一些，并發性能更好，而HashMap沒有鎖機制，不是線程安全的。（JDK1.8之后ConcurrentHashMap啟用了一種全新的方式實現,利用CAS算法。）
HashMap的鍵值對允許有null，但是ConCurrentHashMap都不允許。

ConcurrentHashMap 和 Hashtable 的區別？

ConcurrentHashMap 和 Hashtable 的區別主要體現在實現線程安全的方式上不同。

底層數據結構： JDK1.7的 ConcurrentHashMap 底層采用分段的數組+鏈表實現，JDK1.8 采用的數據結構跟HashMap1.8的結構一樣，數組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數據結構類似都是采用數組+鏈表的形式，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的；
實現線程安全的方式（重要）： ① 在JDK1.7的時候，ConcurrentHashMap（分段鎖）對整個桶數組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數據，多線程訪問容器里不同數據段的數據，就不會存在鎖競爭，提高并發訪問率。（默認分配16個Segment，比Hashtable效率提高16倍。）到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用Node 數組+鏈表+紅黑樹的數據結構來實現，并發控制使用synchronized 和 CAS 來操作。（JDK1.6以后對 synchronized鎖做了很多優化）整個看起來就像是優化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數據結構，但是已經簡化了屬性，只是為了兼容舊版本；②Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當
一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。

ConcurrentHashMap 底層具體實現知道嗎？實現原理是什么？

JDK1.7
首先將數據分為一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據時，其他段的數據也能被其他線程訪問。在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式進行實
現，結構如下：
一個 ConcurrentHashMap 里包含一個 Segment 數組。Segment 的結構和HashMap類似，是一種數組和鏈表結構，一個 Segment 包含一個 HashEntry數組，每個 HashEntry 是一個鏈表結構的元素，每個 Segment 守護著一個HashEntry數組里的元素，當對 HashEntry 數組的數據進行修改時，必須首先獲得對應的 Segment的鎖。
在這里插入圖片描述

該類包含兩個靜態內部類 HashEntry 和 Segment ；前者用來封裝映射表的鍵值對，后者用來充當鎖的角色；
Segment 是一種可重入的鎖 ReentrantLock，每個 Segment 守護一個HashEntry 數組里得元素，當對 HashEntry 數組的數據進行修改時，必須首先獲得對應的 Segment 鎖。

JDK1.8
在JDK1.8中，放棄了Segment臃腫的設計，取而代之的是采用Node + CAS+ Synchronized來保證并發安全進行實現，synchronized只鎖定當前鏈表或紅黑二叉樹的首節點，這樣只要hash不沖突，就不會產生并發，效率又提升N倍。
在這里插入圖片描述

輔助工具類

Array 和 ArrayList 有何區別？

Array 可以存儲基本數據類型和對象，ArrayList 只能存儲對象。
Array 是指定固定大小的，而 ArrayList大小是自動擴展的。
Array 內置方法沒有 ArrayList 多，比如 addAll、removeAll、iteration 等方法

對于基本類型數據，集合使用自動裝箱來減少編碼工作量。但是，當處理固定大小的基本數據類型的時候，這種方式相對比較慢。

如何實現 Array 和 List 之間的轉換？

Array 轉 List： Arrays. asList(array) ；
List 轉 Array：List 的 toArray() 方法。

comparable 和 comparator的區別？

comparable接口實際上是出自java.lang包，它有一個 compareTo(Object obj)方法用來排序
comparator接口實際上是出自 java.util 包，它有一個compare(Object obj1,Object obj2)方法用來排序

一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo方法或compare方法，當我們需要對某一個集合實現兩種排序方式，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話，我們可以重寫compareTo方法和使用自制的Comparator方法或者以兩個Comparator來實現歌名排序和歌星名排序，第二種代表我們只能使用兩個參數版的Collections.sort().

Collection 和 Collections 有什么區別？

java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實現。Collection接口的意義是為各種具體的集合提供了最大化的統一操作方式，其直
接繼承接口有List與Set。
Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜態方法，用于對集合中元素進行排序、搜索以及線程安全等各種操作。