面試題一：Java中有哪些容器（集合類(lèi)）？

Java 中的集合類(lèi)主要由「Collection」和「Map」這兩個(gè)接口派生而出，其中 Collection 接口又派生出三個(gè)子接口，分別是 Set、List、Queue。所有的 Java 集合類(lèi)，都是 Set、List、Queue、Map 這四個(gè)接口的實(shí)現(xiàn)類(lèi)，這四個(gè)接口將集合分成了四大類(lèi)，其中 Set 代表無(wú)序的，元素不可重復(fù)的集合；List 代表有序的，元素可以重復(fù)的集合；Queue 代表先進(jìn)先出（FIFO）的隊(duì)列；Map 代表具有映射關(guān)系（key-value）的集合。
這些接口擁有眾多的實(shí)現(xiàn)類(lèi)，其中最常用的實(shí)現(xiàn)類(lèi)有HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap等。


注：紫色框體代表接口，白色框體代表實(shí)現(xiàn)類(lèi)，其中帶有灰色的是常用實(shí)現(xiàn)類(lèi)。

追問(wèn)：Java中的容器，線程安全和線程不安全的分別有哪些？

java.util 包下的集合類(lèi)大部分都是線程不安全的，例如我們常用的「HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap」這些都是線程不安全的集合類(lèi)，但是它們的優(yōu)點(diǎn)是性能好。如果需要使用線程安全的集合類(lèi)，則可以使用「Collections 工具類(lèi)提供的 synchronizedXxx()」方法，將這些集合類(lèi)包裝成線程安全的集合類(lèi)。

java.util 包下也有線程安全的集合類(lèi)，例如 Vector、Hashtable。這些集合類(lèi)都是比較古老的 API，雖然實(shí)現(xiàn)了線程安全，但是性能很差。所以即便是需要使用線程安全的集合類(lèi)，也建議將線程不安全的集合類(lèi)包裝成線程安全集合類(lèi)的方式，而不是直接使用這些古老的 API。

從 Java5 開(kāi)始，Java 在 java.util.concurrent 包下提供了大量支持高效并發(fā)訪問(wèn)的集合類(lèi)，它們既能包裝良好的訪問(wèn)性能，有能包裝線程安全。這些集合類(lèi)可以分為兩部分，它們的特征如下：

• 以 Concurrent 開(kāi)頭的集合類(lèi)：以 Concurrent 開(kāi)頭的集合類(lèi)代表了支持并發(fā)訪問(wèn)的集合，它們可以支持多個(gè)線程并發(fā)寫(xiě)入訪問(wèn)，這些寫(xiě)入線程的所有操作都是線程安全的，但讀取操作不必鎖定。以 Concurrent 開(kāi)頭的集合類(lèi)采用了更復(fù)雜的算法來(lái)保證永遠(yuǎn)不會(huì)鎖住整個(gè)集合，因此在并發(fā)寫(xiě)入時(shí)有較好的性能。
• 以 CopyOnWrite 開(kāi)頭的集合類(lèi)：以 CopyOnWrite 開(kāi)頭的集合類(lèi)采用復(fù)制底層數(shù)組的方式來(lái)實(shí)現(xiàn)寫(xiě)操作。當(dāng)線程對(duì)此類(lèi)集合執(zhí)行讀取操作時(shí)，線程將會(huì)直接讀取集合本身，無(wú)須加鎖與阻塞。當(dāng)線程對(duì)此類(lèi)集合執(zhí)行寫(xiě)入操作時(shí)，集合會(huì)在底層復(fù)制一份新的數(shù)組，接下來(lái)對(duì)新的數(shù)組執(zhí)行寫(xiě)入操作。由于對(duì)集合的寫(xiě)入操作都是對(duì)數(shù)組的副本執(zhí)行操作，因此它是線程安全的。

面試題二： HashMap 的實(shí)現(xiàn)原理/底層數(shù)據(jù)結(jié)構(gòu)？ JDK1.7 和 JDK1.8

JDK1.7： Entry數(shù)組 + 鏈表
JDK1.8： Node 數(shù)組 + 鏈表/紅黑樹(shù)，當(dāng)鏈表上的元素個(gè)數(shù)超過(guò)「8」個(gè)并且數(shù)組長(zhǎng)度「>= 64」時(shí)自動(dòng)轉(zhuǎn)化成紅黑樹(shù)，節(jié)點(diǎn)變成樹(shù)節(jié)點(diǎn)，以提高搜索效率和插入效率到 O(logN)。
Entry 和 Node 都包含 key、 value、 hash、 next 屬性。

追問(wèn)一：當(dāng)new一個(gè)HashMap的時(shí)候，會(huì)發(fā)生什么嗎？

HashMap 有幾個(gè)構(gòu)造方法，但最主要的就是指定初始值大小和負(fù)載因子的大小。如果我們不指定，默認(rèn)HashMap的大小為16，負(fù)載因子的大小為0.75。

HashMap 的大小只能是「2次冪」的，假設(shè)你傳一個(gè) 10 進(jìn)去，實(shí)際上最終 HashMap 的大小是 16，你傳一個(gè) 7 進(jìn)去，HashMap 最終的大小是 8 ，具體的實(shí)現(xiàn)在「tableSizeFor」可以看到。

我們把元素放進(jìn) HashMap 的時(shí)候，需要算出這個(gè)元素所在的位置（hash），在 HashMap 里用的是位運(yùn)算來(lái)代替取模，能夠更加高效地算出該元素所在的位置。為什么 HashMap 的大小只能是 2 次冪，因?yàn)橹挥写笮?2 次冪時(shí)，才能合理用位運(yùn)算替代取模。
負(fù)載因子的大小決定著哈希表的擴(kuò)容和哈希沖突。

比如現(xiàn)在 我默認(rèn)的 HashMap 大小為 16，負(fù)載因子為 0.75，這意味著數(shù)組最多只能放 12 個(gè)元素，一旦超過(guò) 12 個(gè)元素，則哈希表需要擴(kuò)容。怎么算出是 12 呢？很簡(jiǎn)單，就是「16*0.75」。每次 put 元素進(jìn)去的時(shí)候，都會(huì)檢查HashMap 的大小有沒(méi)有超過(guò)這個(gè)閾值，如果有，則需要擴(kuò)容。

鑒于上面的說(shuō)法（HashMap 的大小只能是 2 次冪），所以擴(kuò)容的時(shí)候時(shí)候默認(rèn)是擴(kuò)原來(lái)的 2 倍。擴(kuò)容這個(gè)操作肯定是耗時(shí)的，那能不能把負(fù)載因子調(diào)高一點(diǎn)，比如我要調(diào)至為 1，那我的 HashMap 就等到 16 個(gè)元素的時(shí)候才擴(kuò)容呢。是可以的，但是不推薦。負(fù)載因子調(diào)高了，這意味著哈希沖突的概率會(huì)增高，哈希沖突概率增高，同樣會(huì)耗時(shí)（因?yàn)椴檎业乃俣茸兟?#xff09; 。

追問(wèn)二：描述一下 Map put 的過(guò)程

直接看這個(gè)->> 畫(huà)了一張圖，簡(jiǎn)單描述了一下 HashMap 的 put 方法的執(zhí)行過(guò)程

追問(wèn)三： JDK 7和 JDK 8中的 HashMap 有什么區(qū)別？

JDK7 中的 HashMap ，是基于「數(shù)組+鏈表」來(lái)實(shí)現(xiàn)的，它的底層維護(hù)一個(gè)「Entry數(shù)組」。它會(huì)根據(jù)計(jì)算的hashCode 將對(duì)應(yīng)的「KV鍵值對(duì)」存儲(chǔ)到該數(shù)組中，一旦發(fā)生 hashCode 沖突，那么就會(huì)將該 KV 鍵值對(duì)放到對(duì)應(yīng)的已有元素的后面， 此時(shí)便形成了一個(gè)鏈表式的存儲(chǔ)結(jié)構(gòu)。

JDK7 中 HashMap 的實(shí)現(xiàn)方案有一個(gè)明顯的缺點(diǎn)，即當(dāng) Hash 沖突嚴(yán)重時(shí)，在桶上形成的鏈表會(huì)變得越來(lái)越長(zhǎng)，這樣在查詢時(shí)的效率就會(huì)越來(lái)越低，其時(shí)間復(fù)雜度為O(N)。

JDK8 中的 HashMap，是基于「數(shù)組+鏈表+紅黑樹(shù)」來(lái)實(shí)現(xiàn)的，它的底層維護(hù)一個(gè)「Node」數(shù)組。當(dāng)鏈表的存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)大于等于 8 的時(shí)候，不再采用鏈表存儲(chǔ)，而采用了紅黑樹(shù)存儲(chǔ)結(jié)構(gòu)。這么做主要是在查詢的時(shí)間復(fù)雜度上進(jìn)行優(yōu)化，鏈表為O(N)，而紅黑樹(shù)一直是O(logN)，可以大大的提高查找性能。

面試題三：hash 碰撞是什么以及如何解決

直接看這個(gè)->> 大白話解釋hash碰撞是什么以及如何解決