1.總結(jié)一下java集合。

Set集合 ：無(wú)序集合（存儲(chǔ)空間不連續(xù)）蕾哟，元素不可以重復(fù)

• HashSet ：可以這樣理解谭确，1.繼承了set集合的特點(diǎn)（無(wú)序逐哈，不重復(fù)）昂秃。2.線程不安全杜窄。3.元素值可以是null塞耕。4.調(diào)用或重寫equals()和hashCode()方法進(jìn)行比較。
• TreeSet ：1.同樣繼承set集合的特點(diǎn)莉钙。2.線程不安全。3.元素有序（不是存儲(chǔ)空間是連續(xù)的停忿，而是可以有序輸出）瞎嬉。4.可以自然排序以及定制排序氧枣。
• LinkedHashSet：1.具有set集合特點(diǎn)便监。2.線程不安全烧董。3.元素的插入順序總是與添加順序一致逊移。

Queue集合：模擬隊(duì)列的數(shù)據(jù)結(jié)構(gòu)龙填，“先進(jìn)先出”扇商。

• Deque:雙端隊(duì)列案铺，也可以是棧梆靖。此接口方法很多暇番。
• ArrayDeque:基于數(shù)組的雙端隊(duì)列，可以在一開(kāi)始就指定長(zhǎng)度恨课，默認(rèn)長(zhǎng)度為16。
• LinkedList: 雖然是list集合希俩，但實(shí)現(xiàn)了Deque接口颜武，可以當(dāng)成雙端隊(duì)列使用鳞上。內(nèi)部是以鏈表的形式保存元素吊档。

List集合：元素有序篙议，可重復(fù)的集合鬼贱。

• ArrayList:1.數(shù)組隊(duì)列这难，可動(dòng)態(tài)增加容量姻乓。2.線程不安全。3.可通過(guò)索引隨機(jī)訪問(wèn)元素星澳，效率很高。
• LinkedList:1.雙向鏈表,它也可以被當(dāng)作堆棧旱易、隊(duì)列或雙端隊(duì)列進(jìn)行操作.2.線程不安全禁偎。3.逐個(gè)遍歷很快，隨機(jī)遍歷效率不高阀坏。

2.比較一下各集合的關(guān)系

Set和Map的關(guān)系

• Map集合的Key的特征是：不能重復(fù)如暖，沒(méi)有順序。而Set的特征也是一樣忌堂。因此你會(huì)發(fā)現(xiàn)盒至，所有的Key其實(shí)是可以組成Set集合的。
• 如果把Map集合的key-values看成一個(gè)整體，values是key的一個(gè)附屬品枷遂，那么就可以把Map集合看成一個(gè)Set集合。

以上兩點(diǎn)關(guān)系有什么用呢？在Map集合建立Key的時(shí)候，就可以參照Set集合的存儲(chǔ)元素規(guī)則：根據(jù)equals()和hashCode()比較兩元素是否相等。

HashMap和HashSet的關(guān)系

• HashMap和HashSet的關(guān)系跟Map和Set的關(guān)系很像。
• HashSet根據(jù)hash算法決定元素存儲(chǔ)位置度苔。
• HashMap先把values當(dāng)做是key的附屬品甩骏，再根據(jù)hash算法決定元素存儲(chǔ)位置福青。
• HashSet封裝了一個(gè)HashMap對(duì)象來(lái)存儲(chǔ)所有集合祝谚，所以HashSet的絕大多數(shù)方法是通過(guò)調(diào)用HashMap的方法實(shí)現(xiàn)的穿仪。

在判斷HashMap集合的元素是否相等是用equals()和hashCode()兩個(gè)方法比較的。（如果重寫這兩個(gè)方法返回值必須保持一致，以下是返回值的不同情況）
1.當(dāng)兩個(gè)都true，代表兩元素是相等的，此時(shí)就不會(huì)添加進(jìn)集合里。
2.如果第一個(gè)是false，第二個(gè)是true。此時(shí)就會(huì)添加在集合里榛丢，但是同一個(gè)地址怎
么放兩個(gè)元素呢？其實(shí)在初始化集合的時(shí)候，劃分的內(nèi)存空間是一個(gè)數(shù)組隘谣，該數(shù)
組叫做Entry數(shù)組,該數(shù)組里的每一個(gè)元素成為“bucket”，每個(gè)bucket都有索引澄耍，系統(tǒng)可以通過(guò)索引快速尋找到bucket存儲(chǔ)的元素选酗。每個(gè)bucket都只存儲(chǔ)一個(gè)Entry,但如何存儲(chǔ)兩個(gè)甚至更多呢（因?yàn)閔ashCode一樣啊，所以這些元素都應(yīng)該在同一個(gè)bucket里）？此時(shí)就用到了Entry鏈表了。因?yàn)镋ntry可以包含一個(gè)引用對(duì)象，這樣就可以指向另一個(gè)Entry了殖熟。這樣就實(shí)現(xiàn)了相等hashCode下，存儲(chǔ)多個(gè)元素的問(wèn)題了饼齿。

深度截圖20170620212715.png

3.如果第一個(gè)true，第二個(gè)false返干。雖然元素會(huì)添加到集合里沦补，但是當(dāng)你需要根據(jù)key刪除或者調(diào)用values的時(shí)候，往往是失敗的。因?yàn)橛幸粋€(gè)key炮赦，兩個(gè)索引诵姜，系統(tǒng)不知道取哪一個(gè)瞎惫。

TreeMap和TreeSet的關(guān)系

• TreeSet封裝了一個(gè)TreeMap對(duì)象來(lái)存儲(chǔ)所有集合伞辛，所以TreeSet的絕大多數(shù)方法是通過(guò)調(diào)用TreeMap的方法實(shí)現(xiàn)的姐呐。
• 對(duì)于TreeMap而言，它是采用一種被稱為“紅黑樹(shù)”的排序二叉樹(shù)來(lái)保存Map中的Entry--每個(gè)Entry都被當(dāng)成“紅黑樹(shù)”的一個(gè)節(jié)點(diǎn)對(duì)待坡锡。

紅黑樹(shù)是一種自平衡二叉查找樹(shù)绵疲，樹(shù)中每一個(gè)節(jié)點(diǎn)的值挤茄，都大于或等于在它的左子樹(shù)中的所有節(jié)點(diǎn)的值评凝，并且少于或等于在它的右子樹(shù)中的所有節(jié)點(diǎn)的值朱浴，這確保紅黑樹(shù)運(yùn)行時(shí)可以快速地在書中查找和定位的所需節(jié)點(diǎn)。

Map和List的關(guān)系

• Map接口提供了get(K key)方法允許Map對(duì)象根據(jù)key來(lái)取得value施敢。
• List接口提供了get(int index)方法允許List對(duì)象根據(jù)元素索引來(lái)取得value默怨。

ArrayList ,LinkedList 和 Vector的關(guān)系

• ArrayList 是一個(gè)可改變大小的數(shù)組.當(dāng)更多的元素加入到 ArrayList 中時(shí), 其大小將會(huì)動(dòng)態(tài)地增長(zhǎng). 內(nèi)部的元素可以直接通過(guò) get 與 set 方法進(jìn)行訪問(wèn), 因?yàn)?ArrayList 本質(zhì)上就是一個(gè)數(shù)組.
• LinkedList 是一個(gè)雙鏈表, 在添加和刪除元素時(shí)具有比 ArrayList 更好的性能. 但在 get 與 set 方面弱于ArrayList. 當(dāng)然, 這些對(duì)比都是指數(shù)據(jù)量很大或者操作很頻繁的情況下的對(duì)比, 如果數(shù)據(jù)和運(yùn)算量很小,那么對(duì)比將失去意義.
• Vector 和 ArrayList 類似, 但屬于強(qiáng)同步類规辱。如果你的程序本身是線程安全的(thread-safe,沒(méi)有在多個(gè)線程之間共享同一個(gè)集合/對(duì)象),那么使用 ArrayList 是更好的選擇碍岔。Vector 和 ArrayList 在更多元素添加進(jìn)來(lái)時(shí)會(huì)請(qǐng)求更大的空間。Vector 每次請(qǐng)求其大小的雙倍空間鸵赫，而 ArrayList每次對(duì) size 增長(zhǎng) 50%.
  而 LinkedList 還實(shí)現(xiàn)了 Queue 接口, 該接口比 List 提供了更多的方法,包括 offer(), peek(), poll()等.

注意: 默認(rèn)情況下 ArrayList 的初始容量非常小, 所以如果可以預(yù)估數(shù)據(jù)量的話, 分配一個(gè)較大的初始值屬于最佳實(shí)踐, 這樣可以減少調(diào)整大小的開(kāi)銷洒闸。
LinkedList 更適用于:
沒(méi)有大規(guī)模的隨機(jī)讀取
大量的增加/刪除操作

以下是引用一些網(wǎng)上很好的問(wèn)題深纲。

“你用過(guò)HashMap嗎？” “什么是HashMap劲妙？你為什么用到它湃鹊？”

幾乎每個(gè)人都會(huì)回答“是的”，然后回答HashMap的一些特性镣奋，譬如HashMap可以接受null鍵值和值币呵，而Hashtable則不能；HashMap是非synchronized;HashMap很快侨颈；以及HashMap儲(chǔ)存的是鍵值對(duì)等等余赢。這顯示出你已經(jīng)用過(guò)HashMap芯义，而且對(duì)它相當(dāng)?shù)氖煜ぁ５敲嬖嚬賮?lái)個(gè)急轉(zhuǎn)直下妻柒，從此刻開(kāi)始問(wèn)出一些刁鉆的問(wèn)題扛拨，關(guān)于HashMap的更多基礎(chǔ)的細(xì)節(jié)。面試官可能會(huì)問(wèn)出下面的問(wèn)題：

“你知道HashMap的工作原理嗎举塔？” “你知道HashMap的get()方法的工作原理嗎绑警？”

你也許會(huì)回答“我沒(méi)有詳查標(biāo)準(zhǔn)的Java API，你可以看看Java源代碼或者Open JDK央渣〖坪校”“我可以用Google找到答案”砸伲”
但一些面試者可能可以給出答案章郁，“HashMap是基于hashing的原理，我們使用put(key, value)存儲(chǔ)對(duì)象到HashMap中志衍，使用get(key)從HashMap中獲取對(duì)象暖庄。當(dāng)我們給put()方法傳遞鍵和值時(shí)，我們先對(duì)鍵調(diào)用hashCode()方法楼肪，返回的hashCode用于找到bucket位置來(lái)儲(chǔ)存Entry對(duì)象培廓。”這里關(guān)鍵點(diǎn)在于指出春叫，HashMap是在bucket中儲(chǔ)存鍵對(duì)象和值對(duì)象肩钠，作為Map.Entry。這一點(diǎn)有助于理解獲取對(duì)象的邏輯暂殖。如果你沒(méi)有意識(shí)到這一點(diǎn)价匠，或者錯(cuò)誤的認(rèn)為僅僅只在bucket中存儲(chǔ)值的話，你將不會(huì)回答如何從HashMap中獲取對(duì)象的邏輯呛每。這個(gè)答案相當(dāng)?shù)恼_踩窖，也顯示出面試者確實(shí)知道hashing以及HashMap的工作原理。但是這僅僅是故事的開(kāi)始晨横，當(dāng)面試官加入一些Java程序員每天要碰到的實(shí)際場(chǎng)景的時(shí)候洋腮，錯(cuò)誤的答案頻現(xiàn)。下個(gè)問(wèn)題可能是關(guān)于HashMap中的碰撞探測(cè)(collision detection)以及碰撞的解決方法：

“當(dāng)兩個(gè)對(duì)象的hashcode相同會(huì)發(fā)生什么手形？”

從這里開(kāi)始啥供，真正的困惑開(kāi)始了，一些面試者會(huì)回答因?yàn)閔ashcode相同库糠，所以兩個(gè)對(duì)象是相等的伙狐，HashMap將會(huì)拋出異常，或者不會(huì)存儲(chǔ)它們。然后面試官可能會(huì)提醒他們有equals()和hashCode()兩個(gè)方法鳞骤，并告訴他們兩個(gè)對(duì)象就算hashcode相同窒百，但是它們可能并不相等。一些面試者可能就此放棄豫尽，而另外一些還能繼續(xù)挺進(jìn)篙梢，他們回答“因?yàn)閔ashcode相同，所以它們的bucket位置相同美旧，‘碰撞’會(huì)發(fā)生渤滞。因?yàn)镠ashMap使用鏈表存儲(chǔ)對(duì)象，這個(gè)Entry(包含有鍵值對(duì)的Map.Entry對(duì)象)會(huì)存儲(chǔ)在鏈表中榴嗅⊥唬”這個(gè)答案非常的合理，雖然有很多種處理碰撞的方法嗽测，這種方法是最簡(jiǎn)單的绪励，也正是HashMap的處理方法。但故事還沒(méi)有完結(jié)唠粥，面試官會(huì)繼續(xù)問(wèn)：

“如果兩個(gè)鍵的hashcode相同疏魏，你如何獲取值對(duì)象？”

面試者會(huì)回答：當(dāng)我們調(diào)用get()方法晤愧，HashMap會(huì)使用鍵對(duì)象的hashcode找到bucket位置大莫，然后獲取值對(duì)象。面試官提醒他如果有兩個(gè)值對(duì)象儲(chǔ)存在同一個(gè)bucket官份，他給出答案:將會(huì)遍歷鏈表直到找到值對(duì)象只厘。面試官會(huì)問(wèn)因?yàn)槟悴](méi)有值對(duì)象去比較，你是如何確定確定找到值對(duì)象的舅巷？除非面試者直到HashMap在鏈表中存儲(chǔ)的是鍵值對(duì)羔味，否則他們不可能回答出這一題。
其中一些記得這個(gè)重要知識(shí)點(diǎn)的面試者會(huì)說(shuō)钠右，找到bucket位置之后赋元，會(huì)調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點(diǎn)，最終找到要找的值對(duì)象爬舰。完美的答案！
許多情況下寒瓦，面試者會(huì)在這個(gè)環(huán)節(jié)中出錯(cuò)情屹，因?yàn)樗麄兓煜薶ashCode()和equals()方法。因?yàn)樵诖酥癶ashCode()屢屢出現(xiàn)杂腰，而equals()方法僅僅在獲取值對(duì)象的時(shí)候才出現(xiàn)垃你。一些優(yōu)秀的開(kāi)發(fā)者會(huì)指出使用不可變的、聲明作final的對(duì)象，并且采用合適的equals()和hashCode()方法的話惜颇，將會(huì)減少碰撞的發(fā)生皆刺，提高效率。不可變性使得能夠緩存不同鍵的hashcode凌摄，這將提高整個(gè)獲取對(duì)象的速度羡蛾，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇锨亏。
如果你認(rèn)為到這里已經(jīng)完結(jié)了痴怨，那么聽(tīng)到下面這個(gè)問(wèn)題的時(shí)候，你會(huì)大吃一驚器予。
“如果HashMap的大小超過(guò)了負(fù)載因子(load factor)定義的容量浪藻，怎么辦？”
除非你真正知道HashMap的工作原理乾翔，否則你將回答不出這道題爱葵。默認(rèn)的負(fù)載因子大小為0.75，也就是說(shuō)反浓，當(dāng)一個(gè)map填滿了75%的bucket時(shí)候萌丈，和其它集合類(如ArrayList等)一樣，將會(huì)創(chuàng)建原來(lái)HashMap大小的兩倍的bucket數(shù)組勾习，來(lái)重新調(diào)整map的大小浓瞪，并將原來(lái)的對(duì)象放入新的bucket數(shù)組中。這個(gè)過(guò)程叫作rehashing巧婶，因?yàn)樗{(diào)用hash方法找到新的bucket位置乾颁。
如果你能夠回答這道問(wèn)題，下面的問(wèn)題來(lái)了：

“你了解重新調(diào)整HashMap大小存在什么問(wèn)題嗎艺栈？”

你可能回答不上來(lái)英岭，這時(shí)面試官會(huì)提醒你當(dāng)多線程的情況下，可能產(chǎn)生條件競(jìng)爭(zhēng)(race condition)湿右。
當(dāng)重新調(diào)整HashMap大小的時(shí)候诅妹，確實(shí)存在條件競(jìng)爭(zhēng)，因?yàn)槿绻麅蓚€(gè)線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了毅人，它們會(huì)同時(shí)試著調(diào)整大小吭狡。在調(diào)整大小的過(guò)程中，存儲(chǔ)在鏈表中的元素的次序會(huì)反過(guò)來(lái)丈莺，因?yàn)橐苿?dòng)到新的bucket位置的時(shí)候划煮，HashMap并不會(huì)將元素放在鏈表的尾部，而是放在頭部缔俄，這是為了避免尾部遍歷(tail traversing)弛秋。如果條件競(jìng)爭(zhēng)發(fā)生了器躏，那么就死循環(huán)了。這個(gè)時(shí)候蟹略，你可以質(zhì)問(wèn)面試官登失，為什么這么奇怪，要在多線程的環(huán)境下使用HashMap呢挖炬？：）
熱心的讀者貢獻(xiàn)了更多的關(guān)于HashMap的問(wèn)題：

為什么String, Interger這樣的wrapper類適合作為鍵揽浙？

String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過(guò)了，而且String最為常用茅茂。因?yàn)镾tring是不可變的捏萍，也是final的，而且已經(jīng)重寫了equals()和hashCode()方法了空闲。其他的wrapper類也有這個(gè)特點(diǎn)令杈。不可變性是必要的，因?yàn)闉榱艘?jì)算hashCode()碴倾，就要防止鍵值改變逗噩，如果鍵值在放入時(shí)和獲取時(shí)返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對(duì)象跌榔。不可變性還有其他的優(yōu)點(diǎn)如線程安全异雁。如果你可以僅僅通過(guò)將某個(gè)field聲明成final就能保證hashCode是不變的，那么請(qǐng)這么做吧僧须。因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法纲刀，那么鍵對(duì)象正確的重寫這兩個(gè)方法是非常重要的。如果兩個(gè)不相等的對(duì)象返回不同的hashcode的話担平，那么碰撞的幾率就會(huì)小些示绊，這樣就能提高HashMap的性能。

我們可以使用自定義的對(duì)象作為鍵嗎？

這是前一個(gè)問(wèn)題的延伸。當(dāng)然你可能使用任何對(duì)象作為鍵纬黎，只要它遵守了equals()和hashCode()方法的定義規(guī)則，并且當(dāng)對(duì)象插入到Map中之后將不會(huì)再改變了展哭。如果這個(gè)自定義對(duì)象時(shí)不可變的，那么它已經(jīng)滿足了作為鍵的條件闻蛀，因?yàn)楫?dāng)它創(chuàng)建之后就已經(jīng)不能改變了匪傍。

我們可以使用CocurrentHashMap來(lái)代替Hashtable嗎？

這是另外一個(gè)很熱門的面試題觉痛，因?yàn)镃oncurrentHashMap越來(lái)越多人用了役衡。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好秧饮，因?yàn)樗鼉H僅根據(jù)同步級(jí)別對(duì)map的一部分進(jìn)行上鎖映挂。ConcurrentHashMap當(dāng)然可以代替HashTable，但是HashTable提供更強(qiáng)的線程安全性盗尸「檀看看 這篇博客 查看Hashtable和ConcurrentHashMap的區(qū)別。

我個(gè)人很喜歡這個(gè)問(wèn)題泼各，因?yàn)檫@個(gè)問(wèn)題的深度和廣度鞍时，也不直接的涉及到不同的概念。讓我們?cè)賮?lái)看看這些問(wèn)題設(shè)計(jì)哪些知識(shí)點(diǎn)：

• hashing的概念

• HashMap中解決碰撞的方法
• equals()和hashCode()的應(yīng)用扣蜻，以及它們?cè)贖ashMap中的重要性
• 不可變對(duì)象的好處
• HashMap多線程的條件競(jìng)爭(zhēng)
• 重新調(diào)整HashMap的大小