集合類
上述集合類都是線程不安全的集合類，若要使其線程安全，使用Collections提供的synchronizedXxx()方法將其包裝
詳細使用http://www.itdecent.cn/p/17adcb394104中前半部分
HashMap
怎么實現(xiàn)線程安全
1.直接使用Hashtable類(性能會降低)
2.直接使用ConcurrentHashMap(沒有全局鎖，性能高)
3.使用Collections中的synchronizedXxx()將其包裝為線程安全Map
怎么解決哈希沖突
鏈表長度超過閾值 鏈表->紅黑樹
鏈表長度小于閾值 紅黑樹->鏈表
ArrayList和LinkedList區(qū)別
1.ArrayList實現(xiàn)基于數(shù)組，因此隨機訪問快，插入刪除慢，占內(nèi)存相對后者小
2.LinkedList實現(xiàn)基于鏈表，因此隨機訪問慢，插入刪除快，占內(nèi)存相對較大
TreeSet和HashSet區(qū)別
1.HashSet中元素可為null，不保證元素排列，采用哈希表實現(xiàn)
2.TreeSet中元素不能為null，元素自然或定制順序排列，采用紅黑樹實現(xiàn)
HashMap和HashTable區(qū)別
1.Hashtable是一個線程安全的Map實現(xiàn)，但HashMap是線程不安全的實現(xiàn)，所
以HashMap比Hashtable的性能高一點。
2.Hashtable不允許使用null作為key和value，如果試圖把null值放進Hashtable中，將會引發(fā)空指針異常，但HashMap可以使用null作為key或value。
Map接口的實現(xiàn)類
HashMap：優(yōu)先使用，性能最好，線程非安全，不保證排序
LinkedHashMap：需要按插入順序排序
TreeMap：需要將key按自然順序排序甚至自定義排序序列
ConcurrentHashMap：線程安全，不保證排序
Map和Set區(qū)別
Set代表無序的，元素不可重復(fù)的集合
Map代表具有映射關(guān)系(key-value)的集合，其所有的key是一個Set集合，key無序且不重復(fù)
HashMap的底層實現(xiàn)原理
基于hash算法，通過put和get方法存儲和獲取對象
- 存儲對象時，將
K/V傳給put方法，它調(diào)用K的hashCode計算hash從而得到bucket位置。
之后HsahMap會根據(jù)當前bucket的占用情況自動調(diào)整容量。 - 獲取對象時，將
K傳給get，它調(diào)用K的hashCode計算hash從而得到bucket位置。
進一步調(diào)用equals()方法確定鍵值對
Map put的過程
put時采用分段鎖/CAS的加鎖機制
- 首次擴容：先判斷數(shù)組是否為空，若數(shù)組為空則進行第一次擴容（resize）；
- 計算索引：通過hash算法，計算鍵值對在數(shù)組中的索引；
- 插入數(shù)據(jù)：
如果當前位置元素為空，則直接插入數(shù)據(jù)；
如果當前位置元素非空，且key已存在，則直接覆蓋其value；
如果當前位置元素非空，且key不存在，則將數(shù)據(jù)鏈到鏈表末端；
若鏈表長度達到8，則將鏈表轉(zhuǎn)換成紅黑樹，并將數(shù)據(jù)插入樹中； - 再次擴容：如果數(shù)組中元素個數(shù)（size）超過
threshold，則再次進行擴容操作。
2021-04-15_103920.png
JDK7和JDK8HashMap的區(qū)別
- JDK7：
是基于數(shù)組+鏈表來實現(xiàn)的，它的底層維護一個Entry數(shù)組。
計算的hashCode將對應(yīng)的KV鍵值對存儲到數(shù)組中，
發(fā)生hashCode沖突，將該KV鍵值對放到對應(yīng)的已有元素的后面，
此時便形成了一個鏈表式的存儲結(jié)構(gòu)。
(可頻繁發(fā)生沖突時會導(dǎo)致鏈表過于冗長) - JDK8：
基于數(shù)組+鏈表+紅黑樹來實現(xiàn)的，它的底層維護一個Node數(shù)組。
鏈表存儲的數(shù)據(jù)個數(shù)大于等于8的時候，不再采用鏈表存儲，而采用了紅黑樹存儲
結(jié)構(gòu)。
這么做主要是在查詢的時間復(fù)雜度上進行優(yōu)化，鏈表為O(N)，而紅黑樹一直是O(logN)
JDK8通過鏈表和紅黑樹的不斷轉(zhuǎn)換，來解決哈希沖突問題
HashSet的底層結(jié)構(gòu)
HashSet是基于HashMap實現(xiàn)的(采用Hash表實現(xiàn))
默認構(gòu)造函數(shù)是構(gòu)建一個初始容量為16，負載因子為0.75的HashMap
封裝了一個HashMap來存儲所有的集合元素
所有放入HashSet的集合元素實際上由HashMap的key來保存
HashMap的value則存儲一個PRESENT，是一個靜態(tài)Object對象
紅黑樹
自平衡二叉查找樹
