collection裡面有什麼子類？（list和set是實現了collection介面的。） List： 1.可以允許重覆的對象（可重覆，有序集合）。2.可以插入多個null元素。3.常用的實現類有 ArrayList、LinkedList 和 Vector。ArrayList 最為流行，它提供了使 ...
collection裡面有什麼子類？（list和set是實現了collection介面的。）
List：
1.可以允許重覆的對象（可重覆，有序集合）。
2.可以插入多個null元素。
3.常用的實現類有 ArrayList、LinkedList 和 Vector。ArrayList 最為流行，它提供了使用索引的隨意訪問，而 LinkedList 則對於經常需要從 List 中添加或刪除元素的場合更為合適。
list去重：方法一:使用java8新特性stream進行List去重 。方法二:雙重for迴圈去重 。方法三:set集合判斷去重。方法四:遍歷後判斷賦給另一個list集合 。方法五:set和list轉換去重
————————————————
Set：
1.不允許重覆對象（不可重覆，無序集合）。
2 只允許一個 null 元素
3.Set 介面最流行的幾個實現類是 HashSet、LinkedHashSet 以及 TreeSet。最流行的是基於 HashMap 實現的 HashSet；TreeSet 還實現了 SortedSet 介面，因此 TreeSet 是一個根據其 compare() 和 compareTo() 的定義進行排序的有序集合。而且可以重覆。
————————————————
Map：
1.Map不是collection的子介面或者實現類。Map是一個介面。
2.不允許重覆元素。
3. Map 里你可以擁有隨意個 null 值但只能有一個 null （key）鍵。
4. Map 介面最流行的幾個實現類是 HashMap、LinkedHashMap、Hashtable 和 TreeMap。（HashMap、TreeMap最常用）
————————————————
List 的實現類有 ArrayList，Vector 和 LinkedList：
ArrayList 和 Vector 內部是數組結構，線程不安全，在查詢效率上會高很多。 Vector 是線程安全的，性能會稍慢一些。
LinkedList：是雙向鏈表的數據結構，在做查詢時會按照序號索引數據進行前向或後向遍歷，查詢效率偏低，插入速度較快。
Set 的實現類有 HashSet 和 TreeSet：
HashSet：內部是由哈希表（實際上是一個 HashMap 實例）支持的。集合元素可以是null,但只能放入一個null。無序的。
TreeSet：是二叉樹實現的，有序的，或者根據創建 set 時提供的 Comparator 進行排序。
LinkedHashSet：是根據元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護元素的次序。有序的，查詢快，插入慢。當遍歷該集合時候，LinkedHashSet將會以元素的添加順序訪問集合的元素。LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色於HashSet。
Map 的實現類有 HashMap，Hashtable、TreeMap和 LinkedHashMap：
Hashtable：存儲的鍵值對是無序的是按照哈希演算法進行排序，與 HashMap 最大的區別就是線程安全（用synchronized）。鍵或者值不能為 null，為 null 就會拋出空指針異常。
HashMap： 繼承Map介面，實現了哈希表，允許null，線程不安全。哈希表結構其實就是數組+鏈表；在JDK1.8中規定：當鏈表長度大於8時，鏈表長度就轉換為紅黑樹，大大 提高了查找效率。
TreeMap：基於紅黑樹 (二叉樹) 數據結構實現，按 key 排序，預設的排序方式是升序。
LinkedHashMap：有序的 Map 集合實現類，通過插入排序，相當於一個棧，先 put 進去的最後出來，先進後出。
————————————————-------------------------------------------------------------------------------------------------------------------
HashMap： 線程不安全，鏈表結構，效率高；
Hashtable ： 線程安全，但效率低，因為是Hashtable是使用synchronized的，所有線程競爭同一把鎖；
Synchronized Map： 線程安全，但效率低，一次性鎖住整張表來保證線程安全，所以每次只能有一個線程來訪問map。
ConcurrentHashMap：線程安全而且效率高，因為它包含一個segment數組，將數據分段存儲，給每一段數據配一把鎖。
在理想狀態下，ConcurrentHashMap 可支持16個線程執行併發寫操作，及任意數量線程的讀操作。
jdk1.7中採用Segment + HashEntry的方式進行實現。
jdk1.8中放棄了Segment臃腫的設計，取而代之的是採用Node + CAS + Synchronized來保證併發安全進行實現。（HashEntry在1.8中稱為Node）
Segment ： Segment 類繼承於 ReentrantLock 類，從而使得 Segment 對象能充當鎖的角色。
HashEntry ： 主要存儲鍵值對,可以叫節點、用來封裝散列映射表中的鍵值對。 https://blog.csdn.net/dfsaggsd/article/details/50572958
以下三種方式：用Hashtable、ConcurrentHashMap、或者Synchronized Map。
ConCurrentHashMap與HashTable區別？
兩者都是線程安全的，但是hashTable鎖住的是整個map，效率低下。而ConcurrentHashMap使用的是cas+synchronized機制，不會鎖定整個map，而是鎖定table數組位置對應的鏈表。
一般不要使用hashTable，推薦使用ConCurrentHashMap。
Hashmap的數據結構是什麼樣子的？自己如何實現一個hashmap？
主要數據結構即為數組+鏈表。預設長度是16。
Hashmap的底層數據結構是由數組+鏈表組成的，是線程不安全，允許key和value為null。
底層結構，數組叫哈希桶，而桶內則是鏈表，鏈表中的節點Node存放著實際的元素。
HashMap底層（原理）是如何實現的？
HashMap先得到key的散列值，在通過擾動函數（減少碰撞次數）得到Hash值，接著通過hash & （n -1 ），n位table的長度，運算後得到數組的索引值。如果當前節點存在元素，則通過比較hash值和key值是否相等，相等則替換，不相等則通過拉鏈法查找元素，直到找到相等或者下個節點為null時。
HashMap是如何put元素的？
HashMap在put方法中，調用內部方法putVal。它使用hashCode()和equals()方法。當我們通過傳遞key-value對調用put方法的時候，HashMap使用Key hashCode()和哈希演算法來找出存儲key-value對的索引。如果索引處為空，則直接插入到對應的數組中，否則哈希衝突，要判斷是否是紅黑樹，若是，則紅黑樹插入，否則遍歷鏈表，若長度超過8，則將鏈表轉為紅黑樹，轉成功之後 再插入。
什麼是Hash（哈希）、什麼是Hash演算法、什麼是哈希表？
hash的定義：Hash譯為散列，哈希是指一個過程，這個過程就是把任意長度的輸入，通過散列演算法，變換成固定長度的輸出，所輸出的稱為哈希值（散列值）。
Hash（哈希）演算法： 即散列函數。它是一種單向密碼體制，即它是一個從明文到密文的不可逆的映射，只有加密過程，沒有解密過程。
哈希表： 是根據設定的哈希函數（key）將一組關鍵字映射到一個有限的地址區間上，並以關鍵字在地址區間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。
Hash的計算規則（演算法）?
第一步：調用key.hashCode()。
第二步：用hashCode值高16位異或低16位（右移16位然後與原先的hashCode值異或，即自己的高半區與低半區做異或，這樣混合後的低位摻雜了高位的部分信息）：
return (key==null)?0:h=key.hashCode()^h>>>16;
第三步：取模運算：h&(length-1) 其中length為table數組長度。h&（length-1） 等價於h%length。
Hashmap的哈希怎麼求出下標位置？
1、進行哈希散列 hash();
int h=key.hashCode();
2、這裡得到的是二進位數：比如：
h=key.hashCode(); //得到的是32位二進位數
3、轉換成二進位後 >>>右移16位和hahsCode值進行位異或.
4、然後index=（16-1）&&hash； 轉換成二進位後index=2就是存儲在數組中的下標位置。
HashMap的長度為什麼是2的倍數？
在HashMap的操作流程中，首先會對key進行hash演算法得到一個索引值，這個索引值就是對應哈希桶數組的索引。為了得到這個索引值必須對擾動後的數跟數組長度進行取餘運算。即 hash % n (n為hashmap的長度)，又因為&比%運算快。n如果為2的倍數，就可以將%轉換為&，結果就是 hash & (n-1)。所以這就解釋了為什麼HashMap長度是2的倍數。
哈希碰撞（衝突）是什麼，怎麼解決？ https://www.cnblogs.com/williamjie/p/9377028.html
兩個不同的原始值在經過哈希運算後得到同樣的結果，這樣就是哈希碰撞。
解決方法：
開放定址法： 原理是在HashMap中，把同樣哈希值的位置以一串鏈表存儲起來數據，把多個原始值不同而哈希結果相同的數據以鏈表存儲起來。
拉鏈法（鏈表法）： 當發生地址衝突時，按照某種方法繼續探測哈希表中的其他存儲單元，直到找到空位置為止。
在哈希法： 當發生衝突時，使用第二個、第三個、哈希函數計算地址，直到無衝突時。缺點：計算時間增加。
談一下hashMap中什麼時候需要進行擴容，擴容resize()又是如何實現的？
調用場景：
1.當hashmap中的元素個數超過當前數組的長度 乘以 loadFactor（載入因數的值）時，就會進行數組擴容（loadFactor：預設值為0.75）
擴容resize()實現過程：
resize：原數組中的數據必須重新計算其在新數組中的位置，並放進去。
1.通過判斷舊數組的容量是否大於0來判斷數組是否初始化過
2、否：進行初始化。
3、是，進行擴容，擴容成兩倍(小於最大值的情況下)，之後在進行將元素重新進行與運算複製到新的散列表中
概括的講：擴容需要重新分配一個新數組，新數組是老數組的2倍長，然後遍歷整個老結構，把所有的元素挨個重新hash分配到新結構中去。
JDK 1.7 HashMap擴容導致死迴圈的主要原因？
HashMap擴容導致死迴圈的主要原因在於擴容後鏈表中的節點在新的hash桶使用頭插法插入。（鏈表倒置以及鏈表過長。）
新的hash桶會倒置原hash桶中的單鏈表，那麼在多個線程同時擴容的情況下就可能導致產生一個存在閉環的單鏈表，從而導致死迴圈。
JDK 1.8 HashMap擴容不會造成死迴圈的原因？
使用的是尾插法，不會導致單鏈表的倒置，所以擴容的時候不會導致死迴圈。
談一下hashMap中get是如何實現的？
對key的hashCode進行hashing，與運算計算下標獲取bucket位置，如果在桶的首位上就可以找到就直接返回，否則在樹中找或者鏈表中遍歷找，如果有hash衝突，則利用equals方法去遍歷鏈表查找節點。
談一下HashMap中hash函數是怎麼實現的？還有哪些hash函數的實現方式？
對key的hashCode做hash操作，與高16位做異或運算
還有平方取中法，除留餘數法，偽隨機數法
為什麼不直接將key作為哈希值而是與高16位做異或運算？
因為數組位置的確定用的是與運算，僅僅最後四位有效，設計者將key的哈希值與高16為做異或運算使得在做&運算確定數組的插入位置時，此時的低位實際是高位與低位的結合，增加了隨機性，減少了哈希碰撞的次數。
為什麼是16？為什麼必須是2的冪？如果輸入值不是2的冪比如10會怎麼樣？
https://blog.csdn.net/sidihuo/article/details/78489820
https://blog.csdn.net/eaphyy/article/details/84386313
1.為了數據的均勻分佈，減少哈希碰撞。因為確定數組位置是用的位運算，若數據不是2的次冪則會增加哈希碰撞的次數和浪費數組空間。(PS:其實若不考慮效率，求餘也可以就不用位運算了也不用長度必需為2的冪次)
2.輸入數據若不是2的冪，HashMap通過一通位移運算和或運算得到的肯定是2的冪次數，並且是離那個數最近的數字
談一下當兩個對象的hashCode相等時會怎麼樣？
會產生哈希碰撞，若key值相同則替換舊值，不然鏈接到鏈表後面，鏈表長度超過闕值8就轉為紅黑樹存儲
如果兩個鍵的hashcode相同，你如何獲取值對象？
HashCode相同，通過equals比較內容獲取值對象
1. java語言CAS底層如何實現？
利用java（unsafe）提供的原子性操作方法。原子操作類，指的是java.util.concurrent.atomic包下，一系列以Atomic開頭的包裝類。
2.什麼事ABA問題？怎麼解決？
當一個值從A變成B，又更新回A，普通CAS機制會誤判通過檢測。
利用版本號比較可以有效解決ABA問題。
