一跺撼、集合的分類

關系結構圖

二、線程安全性

List:vector

Set:谷歌的guava其實已經(jīng)實現(xiàn)了線程安全的ConcurrentHashSet

Map:HashTable和ConcurrentHashMap

重點：線程安全的集合效率會比線程不安全的集合低邓萨，所以在單線程時優(yōu)先考慮線程不安全的集合，要的是工作效率，但是多線程時需要考慮到安全性這時盡量采用線程安全的集合次泽。

三变秦、小知識點總結

①成榜、 Collection 和 Collections 有什么區(qū)別？

②蹦玫、List赎婚、Set刘绣、Map 之間的區(qū)別是什么？

③挣输、HashMap是無序的纬凤，但如果你要對一個 key 集合進行有序的遍歷，那 TreeMap 是更好的選擇撩嚼。

④停士、如何解決Hash沖突問題？

當計算出的 hash 值相同時完丽，我們稱之為 hash 沖突恋技，HashMap 的做法是用鏈表和紅黑樹存儲相同 hash 值的 value。當 hash 沖突的個數(shù)比較少時舰涌，使用鏈表否則使用紅黑樹猖任。

⑤、關于容量和擴容

JDK1.7之前——單列集合的初始容量是10瓷耙，雙列集合是16朱躺；

JDK1.8之后——初始默認容量是0；

擴容——ArrayList 和 Vector 都會根據(jù)實際的需要動態(tài)的調整容量搁痛，只不過在 Vector 擴容每次會增加 1 倍长搀，而 ArrayList 只會增加 50%。

⑥鸡典、數(shù)據(jù)結構中的什么是數(shù)組源请？什么是鏈表？

所謂數(shù)組彻况，是相同數(shù)據(jù)類型的元素按一定順序排列的集合

數(shù)組：存儲區(qū)間是連續(xù)的谁尸，占用內存嚴重，故空間復雜的很大纽甘。但數(shù)組的二分查找時間復雜度小良蛮，為O(1)；數(shù)組的特點是：尋址容易悍赢，插入和刪除困難决瞳；

所謂鏈表，鏈表是一種物理存儲單元上非連續(xù)左权、非順序的存儲結構皮胡，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成赏迟，結點可以在運行時動態(tài)生成屡贺。每個結點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構烹笔，操作復雜裳扯。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度谤职，比另一種線性表順序表快得多饰豺，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)允蜈。

鏈表:鏈表存儲區(qū)間離散冤吨，占用內存比較寬松，故空間復雜度很小饶套，但時間復雜度很大漩蟆，達O（N）。鏈表的特點是：尋址困難妓蛮，插入和刪除容易怠李。

⑦、什么是哈希表蛤克？

從問題⑥中可以看到數(shù)組和鏈表各有優(yōu)缺點捺癞，那么我們能不能綜合兩者的特性，做出一種尋址容易构挤，插入刪除也容易的數(shù)據(jù)結構髓介？答案是肯定的，這就是我們要提起的哈希表筋现。哈希表的結構是鏈表+數(shù)組的組合形式唐础，哈希表（(Hash table）既滿足了數(shù)據(jù)的查找方便，同時不占用太多的內容空間矾飞，使用也十分方便一膨。

⑧、Set 里的元素是不能重復的,那么用什么方法來區(qū)分重復與否呢?是用==還是equals()?它們有何區(qū)別?

equals 方法（是String類從它的超類Object中繼承的）被用來檢測兩個對象是否相等洒沦，即兩個對象的內容是否相等豹绪。

==用于比較引用和比較基本數(shù)據(jù)類型時具有不同的功能：

比較基本數(shù)據(jù)類型，如果兩個值相同微谓，則結果為true

而在比較引用時，如果引用指向內存中的同一對象输钩，結果為true

在比較Set中的元素時豺型，先比較hashCode是否相同，如果不同則肯定不是同一對象买乃，如果相同再比較值姻氨，值也相同則為同一對象

⑨、HashMap的工作原理

HashMap是基于hashing的原理剪验，我們使用put(key, value)存儲對象到HashMap中肴焊，使用get(key)從HashMap中獲取對象前联。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法娶眷，返回的hashCode用于找到bucket位置來儲存Entry對象似嗤。”這里關鍵點在于指出届宠，HashMap是在bucket中儲存鍵對象和值對象烁落，作為Map.Entry。這一點有助于理解獲取對象的邏輯豌注。如果你沒有意識到這一點伤塌，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯轧铁。這個答案相當?shù)恼_每聪，也顯示出面試者確實知道hashing以及HashMap的工作原理。但是這僅僅是故事的開始齿风，當面試官加入一些Java程序員每天要碰到的實際場景的時候药薯，錯誤的答案頻現(xiàn)。下個問題可能是關于HashMap中的碰撞探測(collision detection)以及碰撞的解決方法：

“當兩個對象的hashcode相同會發(fā)生什么聂宾？” 從這里開始果善，真正的困惑開始了，一些面試者會回答因為hashcode相同系谐，所以兩個對象是相等的巾陕，HashMap將會拋出異常，或者不會存儲它們纪他。然后面試官可能會提醒他們有equals()和hashCode()兩個方法鄙煤，并告訴他們兩個對象就算hashcode相同，但是它們可能并不相等茶袒。一些面試者可能就此放棄梯刚，而另外一些還能繼續(xù)挺進，他們回答“因為hashcode相同薪寓，所以它們的bucket位置相同亡资，‘碰撞’會發(fā)生。因為HashMap使用鏈表存儲對象向叉，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中锥腻。”這個答案非常的合理母谎，雖然有很多種處理碰撞的方法瘦黑，這種方法是最簡單的，也正是HashMap的處理方法。但故事還沒有完結幸斥，面試官會繼續(xù)問：

“如果兩個鍵的hashcode相同匹摇，你如何獲取值對象？” 面試者會回答：當我們調用get()方法甲葬，HashMap會使用鍵對象的hashcode找到bucket位置廊勃，然后獲取值對象。面試官提醒他如果有兩個值對象儲存在同一個bucket演顾，他給出答案:將會遍歷鏈表直到找到值對象供搀。面試官會問因為你并沒有值對象去比較，你是如何確定確定找到值對象的钠至？除非面試者直到HashMap在鏈表中存儲的是鍵值對葛虐，否則他們不可能回答出這一題。

其中一些記得這個重要知識點的面試者會說棉钧，找到bucket位置之后屿脐，會調用keys.equals()方法去找到鏈表中正確的節(jié)點，最終找到要找的值對象宪卿。完美的答案的诵！

許多情況下，面試者會在這個環(huán)節(jié)中出錯佑钾，因為他們混淆了hashCode()和equals()方法西疤。因為在此之前hashCode()屢屢出現(xiàn)，而equals()方法僅僅在獲取值對象的時候才出現(xiàn)休溶。一些優(yōu)秀的開發(fā)者會指出使用不可變的代赁、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話兽掰，將會減少碰撞的發(fā)生芭碍，提高效率。不可變性使得能夠緩存不同鍵的hashcode孽尽，這將提高整個獲取對象的速度窖壕，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇杉女。

如果你認為到這里已經(jīng)完結了瞻讽，那么聽到下面這個問題的時候，你會大吃一驚熏挎∷儆拢“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦婆瓜？”除非你真正知道HashMap的工作原理快集，否則你將回答不出這道題。默認的負載因子大小為0.75廉白，也就是說个初，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣猴蹂，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組院溺，來重新調整map的大小，并將原來的對象放入新的bucket數(shù)組中磅轻。這個過程叫作rehashing珍逸，因為它調用hash方法找到新的bucket位置。

如果你能夠回答這道問題聋溜，下面的問題來了：“你了解重新調整HashMap大小存在什么問題嗎谆膳？”你可能回答不上來，這時面試官會提醒你當多線程的情況下撮躁，可能產生條件競爭(race condition)漱病。

當重新調整HashMap大小的時候，確實存在條件競爭把曼，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調整大小了杨帽，它們會同時試著調整大小。在調整大小的過程中嗤军，存儲在鏈表中的元素的次序會反過來注盈，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部叙赚，而是放在頭部老客，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了纠俭，那么就死循環(huán)了沿量。這個時候，你可以質問面試官冤荆，為什么這么奇怪朴则，要在多線程的環(huán)境下使用HashMap呢？：）

熱心的讀者貢獻了更多的關于HashMap的問題：

為什么String, Interger這樣的wrapper類適合作為鍵钓简？ String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了乌妒，而且String最為常用。因為String是不可變的外邓，也是final的撤蚊，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點损话。不可變性是必要的侦啸，因為為了要計算hashCode()槽唾，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話光涂，那么就不能從HashMap中找到你想要的對象庞萍。不可變性還有其他的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的忘闻，那么請這么做吧钝计。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的齐佳。如果兩個不相等的對象返回不同的hashcode的話私恬，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能炼吴。

我們可以使用自定義的對象作為鍵嗎本鸣？ 這是前一個問題的延伸。當然你可能使用任何對象作為鍵硅蹦，只要它遵守了equals()和hashCode()方法的定義規(guī)則永高，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的提针，那么它已經(jīng)滿足了作為鍵的條件命爬，因為當它創(chuàng)建之后就已經(jīng)不能改變了。

我們可以使用CocurrentHashMap來代替Hashtable嗎辐脖？這是另外一個很熱門的面試題饲宛，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的嗜价，但是ConcurrentHashMap同步性能更好艇抠，因為它僅僅根據(jù)同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable久锥，但是HashTable提供更強的線程安全性家淤。