1. 說說Java中常見的集合有哪些？
2. HashMap和HashTable的區別
3. HashSet和HashMap的區別
4. 談一下HashMap的特性？
5. 談一下HashMap的底層原理是什麼？
6. 談一下hashMap中get是如何實現的？
7. 談一下hashMap中put是如何實現的？
8. 談一下hashMap中什麼時候需要進行擴容，擴容resize()又是如何實現的？
9. 談一下HashMap中hash函數是怎麼實現的？還有哪些hash函數的實現方式？
10. HashMap為什麼不直接使用hashCode()處理後的哈希值直接作為table的下標？
10.1 為什麼是兩次擾動呢？
11.為什麼哈希數組的默認長度是16？為什麼擴容必須是2的冪？如果輸入值不是2的冪比如10會怎麼樣？
12. 談一下當兩個對象的hashCode相等時會怎麼樣？
13. 如果兩個鍵的hashcode相同，你如何獲取值對象？
14. 如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？
15. 請解釋一下HashMap的參數loadFactor，它的作用是什麼？
16.傳統hashMap的缺點(為什麼引入紅黑樹？)
17. 平時在使用HashMap時一般使用什麼類型的元素作為Key？
1. 說說Java中常見的集合有哪些？
答：Map接口和Collection接口是所有集合框架的父接口：
- Collection接口的子接口包括：Set接口和List接口
- Map接口的實現類主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
- Set接口的實現類主要有：HashSet、TreeSet、LinkedHashSet等
- List接口的實現類主要有：ArrayList、LinkedList、Stack以及Vector等
2. HashMap和HashTable的區別
- 線程安全性區別：HashMap沒有考慮同步，是線程不安全的；Hashtable使用了synchronized關鍵字，是線程安全的；
- HashMap允許K/V都為null；後者K/V都不允許為null；
- 父類不同：HashMap繼承自AbstractMap類；而Hashtable繼承自Dictionary類；
- 迭代器(Iterator)：HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結構（增加或者移除元素），將會拋出ConcurrentModificationException。
- 容量的初始值和增加方式都不一樣：HashMap默認的容量大小是16；增加容量時，每次將容量變為"原始容量x2"。Hashtable默認的容量大小是11；增加容量時，每次將容量變為"原始容量x2 + 1"；
- 添加key-value時的hash值算法不同：HashMap添加元素時，是使用自定義的哈希算法。Hashtable沒有自定義哈希算法，而直接採用的key的hashCode()。
3. HashSet和HashMap的區別
- HashMap實現了Map接口，HashSet實現了Set接口
- HashMap儲存鍵值對，HashSet僅僅存儲對象
- HashMap使用put()方法將元素放入map中，HashSet使用add()方法將元素放入set中
- HashMap中使用鍵對象來計算hashcode值，HashSet使用成員對象來計算hashcode值，對於兩個對象來說hashcode可能相同，所以equals()方法用來判斷對象的相等性，如果兩個對象不同的話，那麼返回false
- HashMap比較快，因為是使用唯一的鍵來獲取對象，HashSet較HashMap來說比較慢。
4. 談一下HashMap的特性？
- 1.HashMap存儲鍵值對實現快速存取，允許為null。key值不可重複，若key值重複則覆蓋。
- 2.非同步，線程不安全。
- 3.底層是hash表，不保證有序(比如插入的順序)
5. 談一下HashMap的底層原理是什麼？
- 數據結構：基於hashing的原理，jdk8後採用數組+鏈表+紅黑樹的數據結構，通過put和get存儲和獲取對象。
- 插入：當我們給put()方法傳遞鍵和值時，先對鍵做一個hashCode()的計算來得到它在bucket數組中的位置來存儲Entry對象。
- 讀取：當獲取對象時，通過get獲取到bucket的位置，再通過鍵對象的equals()方法找到正確的鍵值對，然後在返回值對象。
6. 談一下hashMap中get是如何實現的？
- 對key的hashCode進行hashing，與運算計算下標獲取bucket位置，如果在桶的首位上就可以找到就直接返回，否則在樹中找或者鏈表中遍歷找，如果有hash衝突，則利用equals方法去遍歷鏈表查找節點。
7. 談一下hashMap中put是如何實現的？
- 1. 計算關於key的hashcode值（與Key.hashCode的高16位做異或運算）
- 2. 如果散列表為空時，調用resize()初始化散列表
- 3. 如果沒有發生碰撞，直接添加元素到散列表中去
- 4. 如果發生了碰撞(hashCode值相同)，進行三種判斷：
a. 若key地址相同或者equals後內容相同，則替換舊值
b. 如果是紅黑樹結構，就調用樹的插入方法
c. 鏈表結構，循環遍歷直到鏈表中某個節點為空，尾插法進行插入，插入之後判斷鏈表個數是否到達變成紅黑樹的闕值8；也可以遍歷到有節點與插入元素的哈希值和內容相同，進行覆蓋。
- 5. 如果桶滿了大於閥值，則resize進行擴容
8. 談一下hashMap中什麼時候需要進行擴容，擴容resize()又是如何實現的？
hashMap擴容的觸發條件：
1.初始化數組table
2.當數組table的size達到闕值時即++size > load factor * capacity 時，也是在putVal函數中
擴容的詳細實現過程：
1. 通過判斷舊數組的容量是否大於0來判斷數組是否初始化過，否，則進行初始化：
- 判斷是否調用無參構造器，是：使用默認的大小（16）和闕值（0.75）
- 判斷是否調用無參構造器，否：使用構造函數中初始化的容量。當然這個容量是經過tableSizefor計算後的2的次冪數；
2. 已初始化，則進行擴容，擴容成兩倍(小於最大值的情況下)，之後在進行將元素重新進行與運算複製到新的散列表中。
概括的講：擴容需要重新分配一個新數組，新數組是老數組的2倍長，然後遍歷整個老結構，把所有的元素挨個重新hash分配到新結構中去。
9. 談一下HashMap中hash函數是怎麼實現的？還有哪些hash函數的實現方式？
對key的hashCode做hash操作，與高16位做異或運算
還有平方取中法，除留餘數法，偽隨機數法
10. HashMap為什麼不直接使用hashCode()處理後的哈希值直接作為table的下標？
- 只有當數組長度為2的冪次方時，h&(length-1)才等價於h%length，即實現了key的定位，2的冪次方也可以減少衝突次數，提高HashMap的查詢效率；
- 如果 length 為 2 的次冪 則 length-1 轉化為二進制必定是 11111……的形式，在於 h 的二進制與操作效率會非常的快，而且空間不浪費；如果 length 不是 2 的次冪，比如 length 為 15，則 length - 1 為 14，對應的二進制為 1110，在於 h 與操作，最後一位都為 0 ，而 0001，0011，0101，1001，1011，0111，1101 這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！這樣就會造成空間的浪費。
10.1 面試官：那為什麼是兩次擾動呢？
答：這樣就是加大哈希值低位的隨機性，使得分佈更均勻，從而提高對應數組存儲下標位置的隨機性&均勻性，最終減少Hash衝突，兩次就夠了，已經達到了高位低位同時參與運算的目的；
11.為什麼哈希數組的默認長度是16？為什麼擴容必須是2的冪？如果輸入值不是2的冪比如10會怎麼樣？
- 1.為了數據的均勻分佈，減少哈希碰撞。因為確定數組位置是用的位運算，若數據不是2的次冪則會增加哈希碰撞的次數和浪費數組空間。(PS:其實若不考慮效率，求餘也可以就不用位運算了也不用長度必需為2的冪次)
- 2.輸入數據若不是2的冪，HashMap通過一通位移運算和或運算得到的肯定是2的冪次數，並且是離那個數最近的數字
12. 談一下當兩個對象的hashCode相等時會怎麼樣？
會產生哈希碰撞，若key值相同則替換舊值，不然鏈接到鏈表後面，鏈表長度超過闕值8就轉為紅黑樹存儲，如果長度縮減小於閾值6則紅黑樹轉鏈表存儲。
13. 如果兩個鍵的hashcode相同，你如何獲取值對象？
HashCode相同，通過equals比較內容獲取值對象
14. 如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？
超過闕值會進行擴容操作，概括的講就是擴容後的數組大小是原數組的2倍，將原來的元素重新hashing放入到新的散列表中去。
15. 請解釋一下HashMap的參數loadFactor，它的作用是什麼？
loadFactor表示HashMap的擁擠程度，影響hash操作到同一個數組位置的概率。默認loadFactor等於0.75，當HashMap裡面容納的元素已經達到HashMap數組長度的75%時，表示HashMap太擠了，需要擴容，在HashMap的構造器中可以定製loadFactor。
16.傳統hashMap的缺點(為什麼引入紅黑樹？)
JDK 1.8 以前 HashMap 的實現是 數組+鏈表，即使哈希函數取得再好，也很難達到元素百分百均勻分佈。當 HashMap 中有大量的元素都存放到同一個桶中時，這個桶下有一條長長的鏈表，這個時候 HashMap 就相當於一個單鏈表，假如單鏈表有 n 個元素，遍歷的時間複雜度就是 O(n)，完全失去了它的優勢。針對這種情況，JDK 1.8 中引入了 紅黑樹（查找時間複雜度為 O(logn)）來優化這個問題。
17. 平時在使用HashMap時一般使用什麼類型的元素作為Key？
選擇Integer，String這種不可變的類型，像對String的一切操作都是新建一個String對象，對新的對象進行拼接分割等，這些類已經很規範的覆寫了hashCode()以及equals()方法。作為不可變類天生是線程安全的。
