Arraylist 與 LinkedList 異同
- 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ū)別：）吏恭； 詳細(xì)可閱讀JDK1.7-LinkedList循環(huán)鏈表優(yōu)化
-
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ǔ)惨篱，所以插入盏筐，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，都是近似 O（1）而數(shù)組為近似 O（n）砸讳。 -
4. 是否支持快速隨機(jī)訪問(wèn)： LinkedList 不支持高效的隨機(jī)元素訪問(wèn)琢融，而 ArrayList 支持〔炯牛快速隨機(jī)訪問(wèn)就是通過(guò)元素的序號(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ù)）常遂。
-**6. 發(fā)
補(bǔ)充內(nèi)容:RandomAccess接口
public interface RandomAccess {
}
查看源碼我們發(fā)現(xiàn)實(shí)際上 RandomAccess 接口中什么都沒(méi)有定義纳令。所以，在我看來(lái) RandomAccess 接口不過(guò)是一個(gè)標(biāo)識(shí)罷了克胳。標(biāo)識(shí)什么平绩？ 標(biāo)識(shí)實(shí)現(xiàn)這個(gè)接口的類具有隨機(jī)訪問(wèn)功能。
在binarySearch（）方法中漠另，它要判斷傳入的list 是否RamdomAccess的實(shí)例捏雌，如果是，調(diào)用indexedBinarySearch（）方法笆搓，如果不是性湿，那么調(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 沒(méi)有實(shí)現(xiàn)。為什么呢窘奏？我覺(jué)得還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)嘹锁！ArrayList 底層是數(shù)組，而 LinkedList 底層是鏈表着裹。數(shù)組天然支持隨機(jī)訪問(wèn)，時(shí)間復(fù)雜度為 O（1）米同，所以稱為快速隨機(jī)訪問(wèn)骇扇。鏈表需要遍歷到特定位置才能訪問(wèn)特定位置的元素，時(shí)間復(fù)雜度為 O（n）面粮，所以不支持快速隨機(jī)訪問(wèn)少孝。，ArrayList 實(shí)現(xiàn)了 RandomAccess 接口熬苍，就表明了他具有快速隨機(jī)訪問(wèn)功能稍走。 RandomAccess 接口只是標(biāo)識(shí)，并不是說(shuō) ArrayList 實(shí)現(xiàn) RandomAccess 接口才具有快速隨機(jī)訪問(wèn)功能的柴底！
下面再總結(jié)一下 list 的遍歷方式選擇：
- 實(shí)現(xiàn)了RandomAccess接口的list婿脸，優(yōu)先選擇普通for循環(huán) ，其次foreach,
- 未實(shí)現(xiàn)RandomAccess接口的ist柄驻， 優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過(guò)iterator實(shí)現(xiàn)的）狐树，大size的數(shù)據(jù)，千萬(wàn)不要使用普通for循環(huán)
補(bǔ)充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表
雙向鏈表也叫雙鏈表鸿脓，是鏈表的一種抑钟，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)野哭。所以在塔，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)拨黔。一般我們都構(gòu)造雙向循環(huán)鏈表蛔溃，如下圖所示，同時(shí)下圖也是LinkedList 底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)蓉驹。
ArrayList 與 Vector 區(qū)別
Vector類的所有方法都是同步的城榛。可以由兩個(gè)線程安全地訪問(wèn)一個(gè)Vector對(duì)象态兴、但是一個(gè)線程訪問(wèn)Vector的話代碼要在同步操作上耗費(fèi)大量的時(shí)間狠持。
Arraylist不是同步的，所以在不需要保證線程安全時(shí)時(shí)建議使用Arraylist瞻润。
HashMap的底層實(shí)現(xiàn)
JDK1.8之前
JDK1.8 之前 HashMap 底層是 數(shù)組和鏈表 結(jié)合在一起使用也就是 鏈表散列喘垂。HashMap 通過(guò) key 的 hashCode 經(jīng)過(guò)擾動(dòng)函數(shù)處理過(guò)后得到 hash 值甜刻，然后通過(guò) (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長(zhǎng)度），如果當(dāng)前位置存在元素的話正勒，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同得院，如果相同的話，直接覆蓋章贞，不相同就通過(guò)拉鏈法解決沖突祥绞。
所謂擾動(dòng)函數(shù)指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動(dòng)函數(shù)是為了防止一些實(shí)現(xiàn)比較差的 hashCode() 方法 換句話說(shuō)使用擾動(dòng)函數(shù)之后可以減少碰撞鸭限。
JDK 1.8 HashMap 的 hash 方法源碼:
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡(jiǎn)化蜕径，但是原理不變。
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位異或
// >>>:無(wú)符號(hào)右移败京，忽略符號(hào)位兜喻，空位都以0補(bǔ)齊
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
對(duì)比一下 JDK1.7的 HashMap 的 hash 方法源碼.
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會(huì)稍差一點(diǎn)點(diǎn)赡麦，因?yàn)楫吘箶_動(dòng)了 4 次朴皆。
所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合。也就是說(shuō)創(chuàng)建一個(gè)鏈表數(shù)組泛粹，數(shù)組中每一格就是一個(gè)鏈表遂铡。若遇到哈希沖突，則將沖突的值加到鏈表中即可戚扳。
JDK1.8之后
相比于之前的版本忧便， JDK1.8之后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)帽借，將鏈表轉(zhuǎn)化為紅黑樹(shù)珠增，以減少搜索時(shí)間。
TreeMap砍艾、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹(shù)蒂教。紅黑樹(shù)就是為了解決二叉查找樹(shù)的缺陷，因?yàn)槎娌檎覙?shù)在某些情況下會(huì)退化成一個(gè)線性結(jié)構(gòu)脆荷。
推薦閱讀：
- 《Java 8系列之重新認(rèn)識(shí)HashMap》 ：https://zhuanlan.zhihu.com/p/21673805
HashMap 和 Hashtable 的區(qū)別
-
線程是否安全： HashMap 是非線程安全的凝垛，HashTable 是線程安全的；HashTable 內(nèi)部的方法基本都經(jīng)過(guò)
synchronized修飾蜓谋。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧Ｃ纹ぁ）； - 效率： 因?yàn)榫€程安全的問(wèn)題桃焕，HashMap 要比 HashTable 效率高一點(diǎn)剑肯。另外，HashTable 基本被淘汰观堂，不要在代碼中使用它让网；
- 對(duì)Null key 和Null value的支持： HashMap 中呀忧，null 可以作為鍵，這樣的鍵只有一個(gè)溃睹，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為 null而账。。但是在 HashTable 中 put 進(jìn)的鍵值只要有一個(gè) null因篇，直接拋出 NullPointerException泞辐。
-
初始容量大小和每次擴(kuò)充容量大小的不同 ： ①創(chuàng)建時(shí)如果不指定容量初始值，Hashtable 默認(rèn)的初始大小為11竞滓，之后每次擴(kuò)充铛碑，容量變?yōu)樵瓉?lái)的2n+1。HashMap 默認(rèn)的初始化大小為16虽界。之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的2倍涛菠。②創(chuàng)建時(shí)如果給定了容量初始值莉御，那么 Hashtable 會(huì)直接使用你給定的大小，而 HashMap 會(huì)將其擴(kuò)充為2的冪次方大兴锥场（HashMap 中的
tableSizeFor()方法保證礁叔，下面給出了源代碼）。也就是說(shuō) HashMap 總是使用2的冪作為哈希表的大小,后面會(huì)介紹到為什么是2的冪次方迄薄。 - 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較大的變化琅关，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)讥蔽，以減少搜索時(shí)間涣易。Hashtable 沒(méi)有這樣的機(jī)制。
HasMap 中帶有初始容量的構(gòu)造函數(shù)：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
下面這個(gè)方法保證了 HashMap 總是使用2的冪作為哈希表的大小冶伞。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
HashMap 的長(zhǎng)度為什么是2的冪次方
為了能讓 HashMap 存取高效新症，盡量較少碰撞，也就是要盡量把數(shù)據(jù)分配均勻响禽。我們上面也講到了過(guò)了徒爹，Hash 值的范圍值-2147483648到2147483647，前后加起來(lái)大概40億的映射空間芋类，只要哈希函數(shù)映射得比較均勻松散隆嗅，一般應(yīng)用是很難出現(xiàn)碰撞的。但問(wèn)題是一個(gè)40億長(zhǎng)度的數(shù)組侯繁，內(nèi)存是放不下的胖喳。所以這個(gè)散列值是不能直接拿來(lái)用的。用之前還要先做對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算巫击，得到的余數(shù)才能用來(lái)要存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)禀晓。這個(gè)數(shù)組下標(biāo)的計(jì)算方法是“ (n - 1) & hash ”精续。（n代表數(shù)組長(zhǎng)度）。這也就解釋了 HashMap 的長(zhǎng)度為什么是2的冪次方粹懒。
這個(gè)算法應(yīng)該如何設(shè)計(jì)呢重付？
我們首先可能會(huì)想到采用%取余的操作來(lái)實(shí)現(xiàn)。但是凫乖，重點(diǎn)來(lái)了：“取余(%)操作中如果除數(shù)是2的冪次則等價(jià)于與其除數(shù)減一的與(&)操作（也就是說(shuō) hash%length==hash&(length-1)的前提是 length 是2的 n 次方确垫；）∶毖浚” 并且 采用二進(jìn)制位操作 &删掀，相對(duì)于%能夠提高運(yùn)算效率，這就解釋了 HashMap 的長(zhǎng)度為什么是2的冪次方导街。
HashMap 多線程操作導(dǎo)致死循環(huán)問(wèn)題
在多線程下披泪，進(jìn)行 put 操作會(huì)導(dǎo)致 HashMap 死循環(huán)，原因在于 HashMap 的擴(kuò)容 resize()方法搬瑰。由于擴(kuò)容是新建一個(gè)數(shù)組款票，復(fù)制原數(shù)據(jù)到數(shù)組。由于數(shù)組下標(biāo)掛有鏈表泽论，所以需要復(fù)制鏈表艾少，但是多線程操作有可能導(dǎo)致環(huán)形鏈表。復(fù)制鏈表過(guò)程如下:
以下模擬2個(gè)線程同時(shí)擴(kuò)容翼悴。假設(shè)缚够，當(dāng)前 HashMap 的空間為2（臨界值為1），hashcode 分別為 0 和 1鹦赎，在散列地址 0 處有元素 A 和 B谍椅，這時(shí)候要添加元素 C，C 經(jīng)過(guò) hash 運(yùn)算钙姊，得到散列地址為 1毯辅，這時(shí)候由于超過(guò)了臨界值，空間不夠煞额，需要調(diào)用 resize 方法進(jìn)行擴(kuò)容思恐，那么在多線程條件下，會(huì)出現(xiàn)條件競(jìng)爭(zhēng)膊毁，模擬過(guò)程如下：
線程一：讀取到當(dāng)前的 HashMap 情況胀莹，在準(zhǔn)備擴(kuò)容時(shí)，線程二介入
線程二：讀取 HashMap婚温，進(jìn)行擴(kuò)容
線程一：繼續(xù)執(zhí)行
這個(gè)過(guò)程為描焰，先將 A 復(fù)制到新的 hash 表中，然后接著復(fù)制 B 到鏈頭（A 的前邊：B.next=A），本來(lái) B.next=null荆秦，到此也就結(jié)束了（跟線程二一樣的過(guò)程）篱竭，但是，由于線程二擴(kuò)容的原因步绸，將 B.next=A掺逼，所以，這里繼續(xù)復(fù)制A瓤介，讓 A.next=B吕喘，由此，環(huán)形鏈表出現(xiàn)：B.next=A; A.next=B
注意：jdk1.8已經(jīng)解決了死循環(huán)的問(wèn)題刑桑。
HashSet 和 HashMap 區(qū)別
如果你看過(guò) HashSet 源碼的話就應(yīng)該知道：HashSet 底層就是基于 HashMap 實(shí)現(xiàn)的氯质。（HashSet 的源碼非常非常少，因?yàn)槌?clone() 方法祠斧、writeObject()方法闻察、readObject()方法是 HashSet 自己不得不實(shí)現(xiàn)之外，其他方法都是直接調(diào)用 HashMap 中的方法琢锋。）
ConcurrentHashMap 和 Hashtable 的區(qū)別
ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實(shí)現(xiàn)線程安全的方式上不同蜓陌。
- 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實(shí)現(xiàn)，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣吩蔑，數(shù)組+鏈表/紅黑二叉樹(shù)。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用 數(shù)組+鏈表 的形式填抬，數(shù)組是 HashMap 的主體烛芬，鏈表則是主要為了解決哈希沖突而存在的；
- 實(shí)現(xiàn)線程安全的方式（重要）： ① 在JDK1.7的時(shí)候飒责，ConcurrentHashMap（分段鎖） 對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)赘娄，每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)，多線程訪問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)宏蛉，就不會(huì)存在鎖競(jìng)爭(zhēng)遣臼，提高并發(fā)訪問(wèn)率。 到了 JDK1.8 的時(shí)候已經(jīng)摒棄了Segment的概念拾并，而是直接用 Node 數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)揍堰，并發(fā)控制使用 synchronized 和 CAS 來(lái)操作。（JDK1.6以后 對(duì) synchronized鎖做了很多優(yōu)化） 整個(gè)看起來(lái)就像是優(yōu)化過(guò)且線程安全的 HashMap嗅义，雖然在JDK1.8中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)屏歹，但是已經(jīng)簡(jiǎn)化了屬性，只是為了兼容舊版本之碗；② Hashtable(同一把鎖) :使用 synchronized 來(lái)保證線程安全蝙眶，效率非常低下。當(dāng)一個(gè)線程訪問(wèn)同步方法時(shí)褪那，其他線程也訪問(wèn)同步方法幽纷，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)式塌，如使用 put 添加元素，另一個(gè)線程不能使用 put 添加元素友浸，也不能使用 get峰尝，競(jìng)爭(zhēng)會(huì)越來(lái)越激烈效率越低。
兩者的對(duì)比圖：
圖片來(lái)源：http://www.cnblogs.com/chengxiao/p/6842045.html
HashTable:
JDK1.7的ConcurrentHashMap：
JDK1.8的ConcurrentHashMap（TreeBin: 紅黑二叉樹(shù)節(jié)點(diǎn)
Node: 鏈表節(jié)點(diǎn)）：
ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)
JDK1.7（上面有示意圖）
首先將數(shù)據(jù)分為一段一段的存儲(chǔ)尾菇，然后給每一段數(shù)據(jù)配一把鎖境析，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)派诬。
ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成劳淆。
Segment 實(shí)現(xiàn)了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色默赂。HashEntry 用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)沛鸵。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組。Segment 的結(jié)構(gòu)和HashMap類似缆八，是一種數(shù)組和鏈表結(jié)構(gòu)曲掰，一個(gè) Segment 包含一個(gè) HashEntry 數(shù)組，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素奈辰，每個(gè) Segment 守護(hù)著一個(gè)HashEntry數(shù)組里的元素栏妖，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得對(duì)應(yīng)的 Segment的鎖奖恰。
JDK1.8 （上面有示意圖）
ConcurrentHashMap取消了Segment分段鎖吊趾，采用CAS和synchronized來(lái)保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類似瑟啃，數(shù)組+鏈表/紅黑二叉樹(shù)论泛。
synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹(shù)的首節(jié)點(diǎn)，這樣只要hash不沖突蛹屿，就不會(huì)產(chǎn)生并發(fā)屁奏，效率又提升N倍。
集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)
Collection
1. List
- Arraylist： Object數(shù)組
- Vector： Object數(shù)組
-
LinkedList： 雙向鏈表(JDK1.6之前為循環(huán)鏈表错负，JDK1.7取消了循環(huán))
詳細(xì)可閱讀JDK1.7-LinkedList循環(huán)鏈表優(yōu)化
2. Set
- HashSet（無(wú)序坟瓢，唯一）: 基于 HashMap 實(shí)現(xiàn)的，底層采用 HashMap 來(lái)保存元素
- LinkedHashSet： LinkedHashSet 繼承與 HashSet犹撒，并且其內(nèi)部是通過(guò) LinkedHashMap 來(lái)實(shí)現(xiàn)的载绿。有點(diǎn)類似于我們之前說(shuō)的LinkedHashMap 其內(nèi)部是基于 Hashmap 實(shí)現(xiàn)一樣，不過(guò)還是有一點(diǎn)點(diǎn)區(qū)別的油航。
- TreeSet（有序崭庸，唯一）： 紅黑樹(shù)(自平衡的排序二叉樹(shù)。)
Map
- HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體怕享，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時(shí)有了較大的變化执赡，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)函筋，以減少搜索時(shí)間
- LinkedHashMap: LinkedHashMap 繼承自 HashMap沙合，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹(shù)組成。另外跌帐，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上首懈，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對(duì)的插入順序谨敛。同時(shí)通過(guò)對(duì)鏈表進(jìn)行相應(yīng)的操作究履，實(shí)現(xiàn)了訪問(wèn)順序相關(guān)邏輯。詳細(xì)可以查看：《LinkedHashMap 源碼詳細(xì)分析（JDK1.8）》
- HashTable: 數(shù)組+鏈表組成的脸狸，數(shù)組是 HashMap 的主體最仑，鏈表則是主要為了解決哈希沖突而存在的
- TreeMap: 紅黑樹(shù)（自平衡的排序二叉樹(shù)）
