HashMap底層實(shí)現(xiàn)原理/HashMap與HashTable區(qū)別/HashMap與HashSet區(qū)別
①HashMap的工作原理
HashMap基于hashing原理妨猩，我們通過put()和get()方法儲(chǔ)存和獲取對(duì)象。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)，它調(diào)用鍵對(duì)象的hashCode()方法來計(jì)算hashcode，讓后找到bucket位置來儲(chǔ)存值對(duì)象俭令。當(dāng)獲取對(duì)象時(shí)原在，通過鍵對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回值對(duì)象批糟。HashMap使用鏈表來解決碰撞問題，當(dāng)發(fā)生碰撞了看铆，對(duì)象將會(huì)儲(chǔ)存在鏈表的下一個(gè)節(jié)點(diǎn)中徽鼎。 HashMap在每個(gè)鏈表節(jié)點(diǎn)中儲(chǔ)存鍵值對(duì)對(duì)象。
當(dāng)兩個(gè)不同的鍵對(duì)象的hashcode相同時(shí)會(huì)發(fā)生什么？ 它們會(huì)儲(chǔ)存在同一個(gè)bucket位置的鏈表中否淤。鍵對(duì)象的equals()方法用來找到鍵值對(duì)悄但。
因?yàn)镠ashMap的好處非常多，我曾經(jīng)在電子商務(wù)的應(yīng)用中使用HashMap作為緩存石抡。因?yàn)榻鹑陬I(lǐng)域非常多的運(yùn)用Java檐嚣，也出于性能的考慮，我們會(huì)經(jīng)常用到HashMap和ConcurrentHashMap汁雷。
②HashMap和Hashtable的區(qū)別
HashMap和Hashtable都實(shí)現(xiàn)了Map接口净嘀，但決定用哪一個(gè)之前先要弄清楚它們之間的分別。主要的區(qū)別有：線程安全性侠讯，同步(synchronization)挖藏，以及速度。
- HashMap幾乎可以等價(jià)于Hashtable厢漩，除了HashMap是非synchronized的膜眠，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)溜嗜。
- HashMap是非synchronized宵膨，而Hashtable是synchronized，這意味著Hashtable是線程安全的炸宵，多個(gè)線程可以共享一個(gè)Hashtable辟躏；而如果沒有正確的同步的話，多個(gè)線程是不能共享HashMap的土全。Java 5提供了ConcurrentHashMap捎琐，它是HashTable的替代，比HashTable的擴(kuò)展性更好裹匙。
- 另一個(gè)區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器瑞凑，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）概页，將會(huì)拋出ConcurrentModificationException籽御，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常。但這并不是一個(gè)一定發(fā)生的行為惰匙，要看JVM技掏。這條同樣也是Enumeration和Iterator的區(qū)別。
- 由于Hashtable是線程安全的也是synchronized项鬼，所以在單線程環(huán)境下它比HashMap要慢零截。如果你不需要同步，只需要單一線程秃臣，那么使用HashMap性能要好過Hashtable。
- HashMap不能保證隨著時(shí)間的推移Map中的元素次序是不變的。
要注意的一些重要術(shù)語(yǔ)：
sychronized意味著在一次僅有一個(gè)線程能夠更改Hashtable奥此。就是說任何線程要更新Hashtable時(shí)要首先獲得同步鎖弧哎，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable。
Fail-safe和iterator迭代器相關(guān)稚虎。如果某個(gè)集合對(duì)象創(chuàng)建了Iterator或者ListIterator撤嫩，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對(duì)象，將會(huì)拋出ConcurrentModificationException異常蠢终。但其它線程可以通過set()方法更改集合對(duì)象是允許的序攘，因?yàn)檫@并沒有從“結(jié)構(gòu)上”更改集合。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改寻拂，再調(diào)用set()方法程奠，將會(huì)拋出IllegalArgumentException異常。
結(jié)構(gòu)上的更改指的是刪除或者插入一個(gè)元素祭钉，這樣會(huì)影響到map的結(jié)構(gòu)瞄沙。
我們能否讓HashMap同步？
HashMap可以通過下面的語(yǔ)句進(jìn)行同步：
Map m = Collections.synchronizeMap(hashMap);
結(jié)論
Hashtable和HashMap有幾個(gè)主要的不同：線程安全以及速度慌核。僅在你需要完全的線程安全的時(shí)候使用Hashtable距境，而如果你使用Java 5或以上的話，請(qǐng)使用ConcurrentHashMap吧垮卓。
ashMap和HashSet的區(qū)別是Java面試中最常被問到的問題垫桂。如果沒有涉及到Collection框架以及多線程的面試，可以說是不完整粟按。而Collection框架的問題不涉及到HashSet和HashMap诬滩，也可以說是不完整。HashMap和HashSet都是collection框架的一部分钾怔，它們讓我們能夠使用對(duì)象的集合碱呼。collection框架有自己的接口和實(shí)現(xiàn)，主要分為Set接口宗侦，List接口和Queue接口愚臀。它們有各自的特點(diǎn)，Set的集合里不允許對(duì)象有重復(fù)的值矾利，List允許有重復(fù)姑裂，它對(duì)集合中的對(duì)象進(jìn)行索引，Queue的工作原理是FCFS算法(First Come, First Serve)男旗。
首先讓我們來看看什么是HashMap和HashSet舶斧，然后再來比較它們之間的分別。
③HashMap和HashSet的區(qū)別
HashMap和HashSet的區(qū)別是Java面試中最常被問到的問題察皇。如果沒有涉及到Collection框架以及多線程的面試茴厉，可以說是不完整泽台。而Collection框架的問題不涉及到HashSet和HashMap，也可以說是不完整矾缓。HashMap和HashSet都是collection框架的一部分怀酷，它們讓我們能夠使用對(duì)象的集合。collection框架有自己的接口和實(shí)現(xiàn)嗜闻，主要分為Set接口蜕依，List接口和Queue接口。它們有各自的特點(diǎn)琉雳，Set的集合里不允許對(duì)象有重復(fù)的值样眠，List允許有重復(fù)，它對(duì)集合中的對(duì)象進(jìn)行索引翠肘，Queue的工作原理是FCFS算法(First Come, First Serve)檐束。
首先讓我們來看看什么是HashMap和HashSet，然后再來比較它們之間的分別锯茄。
什么是HashSet
HashSet實(shí)現(xiàn)了Set接口厢塘，它不允許集合中有重復(fù)的值，當(dāng)我們提到HashSet時(shí)肌幽，第一件事情就是在將對(duì)象存儲(chǔ)在HashSet之前晚碾，要先確保對(duì)象重寫equals()和hashCode()方法，這樣才能比較對(duì)象的值是否相等喂急，以確保set中沒有儲(chǔ)存相等的對(duì)象格嘁。如果我們沒有重寫這兩個(gè)方法，將會(huì)使用這個(gè)方法的默認(rèn)實(shí)現(xiàn)廊移。
public boolean add(Object o)方法用來在Set中添加元素糕簿，當(dāng)元素值重復(fù)時(shí)則會(huì)立即返回false，如果成功添加的話會(huì)返回true狡孔。
什么是HashMap
HashMap實(shí)現(xiàn)了Map接口懂诗，Map接口對(duì)鍵值對(duì)進(jìn)行映射。Map中不允許重復(fù)的鍵苗膝。Map接口有兩個(gè)基本的實(shí)現(xiàn)殃恒，HashMap和TreeMap。TreeMap保存了對(duì)象的排列次序辱揭，而HashMap則不能离唐。HashMap允許鍵和值為null。HashMap是非synchronized的问窃，但collection框架提供方法能保證HashMap synchronized亥鬓，這樣多個(gè)線程同時(shí)訪問HashMap時(shí)，能保證只有一個(gè)線程更改Map域庇。
public Object put(Object Key,Object value)方法用來將元素添加到map中嵌戈。
HashSet和HashMap的區(qū)別
| HashMap | HashSet |
|---|---|
| HashMap實(shí)現(xiàn)了Map接口 | HashSet實(shí)現(xiàn)了Set接口 |
| HashMap儲(chǔ)存鍵值對(duì) | HashSet僅僅存儲(chǔ)對(duì)象 |
| 使用put()方法將元素放入map中 | 使用add()方法將元素放入set中 |
| HashMap中使用鍵對(duì)象來計(jì)算hashcode值 | HashSet使用成員對(duì)象來計(jì)算hashcode值覆积，對(duì)于兩個(gè)對(duì)象來說hashcode可能相同，所以equals()方法用來判斷對(duì)象的相等性咕别，如果兩個(gè)對(duì)象不同的話技健，那么返回false |
| HashMap比較快，因?yàn)槭鞘褂梦ㄒ坏逆I來獲取對(duì)象 | HashSet較HashMap來說比較慢 |
④面試題
HashMap的工作原理是近年來常見的Java面試題惰拱。幾乎每個(gè)Java程序員都知道HashMap，都知道哪里要用HashMap啊送，知道Hashtable和HashMap之間的區(qū)別偿短，那么為何這道面試題如此特殊呢？是因?yàn)檫@道題考察的深度很深馋没。這題經(jīng)常出現(xiàn)在高級(jí)或中高級(jí)面試中昔逗。投資銀行更喜歡問這個(gè)問題，甚至?xí)竽銓?shí)現(xiàn)HashMap來考察你的編程能力篷朵。ConcurrentHashMap和其它同步集合的引入讓這道題變得更加復(fù)雜勾怒。讓我們開始探索的旅程吧！
“你用過HashMap嗎声旺？” “什么是HashMap笔链？你為什么用到它？”
幾乎每個(gè)人都會(huì)回答“是的”腮猖，然后回答HashMap的一些特性鉴扫，譬如HashMap可以接受null鍵值和值，而Hashtable則不能澈缺；HashMap是非synchronized;HashMap很快坪创；以及HashMap儲(chǔ)存的是鍵值對(duì)等等。這顯示出你已經(jīng)用過HashMap姐赡，而且對(duì)它相當(dāng)?shù)氖煜だ吃ぁ５敲嬖嚬賮韨€(gè)急轉(zhuǎn)直下，從此刻開始問出一些刁鉆的問題项滑，關(guān)于HashMap的更多基礎(chǔ)的細(xì)節(jié)依沮。面試官可能會(huì)問出下面的問題：
“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎杖们？”
你也許會(huì)回答“我沒有詳查標(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位置來儲(chǔ)存Entry對(duì)象》咽玻”這里關(guān)鍵點(diǎn)在于指出钾恢，HashMap是在bucket中儲(chǔ)存鍵對(duì)象和值對(duì)象，作為Map.Entry鸳址。這一點(diǎn)有助于理解獲取對(duì)象的邏輯瘩蚪。如果你沒有意識(shí)到這一點(diǎn)，或者錯(cuò)誤的認(rèn)為僅僅只在bucket中存儲(chǔ)值的話稿黍，你將不會(huì)回答如何從HashMap中獲取對(duì)象的邏輯疹瘦。這個(gè)答案相當(dāng)?shù)恼_，也顯示出面試者確實(shí)知道hashing以及HashMap的工作原理巡球。但是這僅僅是故事的開始言沐，當(dāng)面試官加入一些Java程序員每天要碰到的實(shí)際場(chǎng)景的時(shí)候，錯(cuò)誤的答案頻現(xiàn)酣栈。下個(gè)問題可能是關(guān)于HashMap中的碰撞探測(cè)(collision detection)以及碰撞的解決方法：
“當(dāng)兩個(gè)對(duì)象的hashcode相同會(huì)發(fā)生什么险胰？” 從這里開始，真正的困惑開始了钉嘹，一些面試者會(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的處理方法疗涉。但故事還沒有完結(jié)拿霉，面試官會(huì)繼續(xù)問：
“如果兩個(gè)鍵的hashcode相同，你如何獲取值對(duì)象咱扣？” 面試者會(huì)回答：當(dāng)我們調(diào)用get()方法绽淘，HashMap會(huì)使用鍵對(duì)象的hashcode找到bucket位置，然后獲取值對(duì)象闹伪。面試官提醒他如果有兩個(gè)值對(duì)象儲(chǔ)存在同一個(gè)bucket沪铭，他給出答案:將會(huì)遍歷鏈表直到找到值對(duì)象。面試官會(huì)問因?yàn)槟悴]有值對(duì)象去比較偏瓤，你是如何確定確定找到值對(duì)象的伦意？除非面試者直到HashMap在鏈表中存儲(chǔ)的是鍵值對(duì)，否則他們不可能回答出這一題硼补。
其中一些記得這個(gè)重要知識(shí)點(diǎn)的面試者會(huì)說，找到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)秀的開發(fā)者會(huì)指出使用不可變的昔榴、聲明作final的對(duì)象辛藻，并且采用合適的equals()和hashCode()方法的話，將會(huì)減少碰撞的發(fā)生互订，提高效率吱肌。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個(gè)獲取對(duì)象的速度仰禽，使用String氮墨，Interger這樣的wrapper類作為鍵是非常好的選擇。
如果你認(rèn)為到這里已經(jīng)完結(jié)了吐葵，那么聽到下面這個(gè)問題的時(shí)候规揪，你會(huì)大吃一驚。“如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量温峭，怎么辦猛铅？”除非你真正知道HashMap的工作原理，否則你將回答不出這道題诚镰。默認(rèn)的負(fù)載因子大小為0.75奕坟，也就是說祥款，當(dāng)一個(gè)map填滿了75%的bucket時(shí)候，和其它集合類(如ArrayList等)一樣月杉，將會(huì)創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組刃跛，來重新調(diào)整map的大小，并將原來的對(duì)象放入新的bucket數(shù)組中苛萎。這個(gè)過程叫作rehashing桨昙，因?yàn)樗{(diào)用hash方法找到新的bucket位置。
如果你能夠回答這道問題腌歉，下面的問題來了：“你了解重新調(diào)整HashMap大小存在什么問題嗎蛙酪？”你可能回答不上來，這時(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)整大小的過程中汰瘫，存儲(chǔ)在鏈表中的元素的次序會(huì)反過來狂打，因?yàn)橐苿?dòng)到新的bucket位置的時(shí)候，HashMap并不會(huì)將元素放在鏈表的尾部混弥，而是放在頭部趴乡，這是為了避免尾部遍歷(tail traversing)。如果條件競(jìng)爭(zhēng)發(fā)生了蝗拿，那么就死循環(huán)了晾捏。這個(gè)時(shí)候，你可以質(zhì)問面試官蛹磺，為什么這么奇怪粟瞬，要在多線程的環(huán)境下使用HashMap呢？：）
熱心的讀者貢獻(xiàn)了更多的關(guān)于HashMap的問題：
- 為什么String, Interger這樣的wrapper類適合作為鍵萤捆？ String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了裙品，而且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)如線程安全。如果你可以僅僅通過將某個(gè)field聲明成final就能保證hashCode是不變的戚篙，那么請(qǐng)這么做吧五鲫。因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法，那么鍵對(duì)象正確的重寫這兩個(gè)方法是非常重要的岔擂。如果兩個(gè)不相等的對(duì)象返回不同的hashcode的話位喂，那么碰撞的幾率就會(huì)小些，這樣就能提高HashMap的性能乱灵。
- 我們可以使用自定義的對(duì)象作為鍵嗎塑崖？ 這是前一個(gè)問題的延伸。當(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來代替Hashtable嗎颠区？這是另外一個(gè)很熱門的面試題，因?yàn)镃oncurrentHashMap越來越多人用了通铲。我們知道Hashtable是synchronized的毕莱，但是ConcurrentHashMap同步性能更好，因?yàn)樗鼉H僅根據(jù)同步級(jí)別對(duì)map的一部分進(jìn)行上鎖颅夺。ConcurrentHashMap當(dāng)然可以代替HashTable朋截，但是HashTable提供更強(qiáng)的線程安全性“苫疲看看這篇博客查看Hashtable和ConcurrentHashMap的區(qū)別部服。
我個(gè)人很喜歡這個(gè)問題，因?yàn)檫@個(gè)問題的深度和廣度拗慨，也不直接的涉及到不同的概念廓八。讓我們?cè)賮砜纯催@些問題設(shè)計(jì)哪些知識(shí)點(diǎn)：
- hashing的概念
- HashMap中解決碰撞的方法
- equals()和hashCode()的應(yīng)用，以及它們?cè)贖ashMap中的重要性
- 不可變對(duì)象的好處
- HashMap多線程的條件競(jìng)爭(zhēng)
- 重新調(diào)整HashMap的大小
