HashMap的put實現原理：
第一步：將k和v封裝到Node對象當中(節(jié)點)
第二步：底層調用k的hashCode()方法得出hash值
第三步：通過哈希表函數/哈希算法，將hash值轉換成數組的下標耗式。
注意：如果下標位置上沒有任何元素，就把Node添加到這個位置上
如果說下標對應位置的上有鏈表，那么就會調用equals()方法比較k
如果equals()方法返回的是false水慨，那么這個新的節(jié)點將添加到鏈表的末尾瞧捌。
如果equals()方法返回的是true空入，那么這個新的節(jié)點value將會被覆蓋。
HashMap的get實現原理：
第一步：調用k的hashCode()方法得出哈希值纠吴，通過哈希算法轉換成數組下標。
第二步：通過數組下標快速定位到某個位置上慧瘤。
注意：如果這個位置上什么都沒用戴已，則返回null。
如果這個位置上有單向列表锅减，那么就會用參數k和單向鏈表上的每一個節(jié)點的k進行equals比較
如果equals返回false糖儡，則get方法返回null。
如果equals返回true怔匣，那么此時節(jié)點的value就是我們要找的value了握联，get方法最終返回這個要找的value。
為何隨機增刪劫狠、查詢效率都很高的原因是
增刪是在鏈表上完成的拴疤，而查詢只需掃描部分，則效率高
HashMap集合的key独泞，會先后調用兩個方法呐矾，hashCode and equals方法，這這兩個方法都需要重寫懦砂。
為什么放在hashMap集合key部分的元素需要重寫equals方法蜒犯？
因為equals默認比較是兩個對象內存地址
JDK8之后，如果哈希表單向鏈表中元素超過8個荞膘，那么單向鏈表這種數據結構會變成紅黑樹數據結構罚随。當紅黑樹上的節(jié)點數量小于6個，會重新把紅黑樹變成單向鏈表數據結構羽资。
HashMap底層實現原理
數組+鏈表
數組特點：存儲區(qū)間是連續(xù)淘菩，且占用內存嚴重，空間復雜也很大。
數組優(yōu)點：數組是連續(xù)的潮改，隨機讀取效率高狭郑，隨機訪問性強，查找熟讀快
數組缺點：插入和刪除數據效率低汇在，因為插入數據翰萨，這個位置后面的數據在內存中要往后移，而且大小固定不易動態(tài)擴展糕殉。
鏈表特點：區(qū)間離散亩鬼，占用內存寬松，空間復雜度小阿蝶。
鏈表優(yōu)點：插入刪除速度快雳锋，內存利用率高，沒用大小固定赡磅，擴展靈活魄缚。
鏈表缺點：不能隨機查找，每次都是從第一個開始遍歷焚廊，查詢效率低
HashMap的工作原理
HashMap基于hashing原理冶匹，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時咆瘟，它調用鍵對象的hashCode()方法來計算hashcode嚼隘，讓后找到bucket位置來儲存值對象，來放entry鍵值對袒餐。當獲取對象時飞蛹，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象灸眼。HashMap使用鏈表來解決碰撞問題卧檐，當發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中焰宣。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象霉囚。
HashMap：有序，添加刪除映射性能高匕积。
線程不安全
基于哈希表的Map接口實現盈罐，快速查找性能高
允許null值和null鍵
繼承AbstractMap類；覆蓋了hashcode() 和equals() 方法闪唆，以確保兩個相等的映射返回相同的哈希值盅粪；
TreeMap：實現了java.util.SortedMap接口，因此有序
線程不安全
添加刪除定位映射關系性能差
不允許鍵為null
有序的key 集合進行遍歷悄蕾，TreeMap 是更好的選擇
TreeMap繼承SortedMap類票顾；他保持鍵的有序順序；
基于紅黑樹實現的；TreeMap就沒有調優(yōu)選項库物，因為紅黑樹總是處于平衡的狀態(tài)霸旗；
HashMap初始化大小是 16 ，擴容因子默認0.75（可以指定初始化大小戚揭，和擴容因子）
例如：初始大小為16，擴容因子 0.75 撵枢，當容量為12的時候民晒，比例已經是0.75 。觸發(fā)擴容锄禽，擴容后的大小為 32（一倍擴容）
線程：
Hashtable線程安全潜必。HashMap線程不安全。
Hashtable的實現方法里面都添加了synchronized關鍵字來確保線程同步沃但，因此相對而言HashMap性能會高一些磁滚，我們平時使用時若無特殊需求建議使用HashMap，在多線程環(huán)境下若使用HashMap需要使用Collections.synchronizedMap()方法來獲取一個線程安全的集合宵晚。
擴容：
HashMap的初始容量為16垂攘，Hashtable初始容量為11，兩者的填充因子默認都是0.75淤刃。
HashMap擴容時是當前容量翻倍即:capacity*2晒他，Hashtable擴容時是容量翻倍+1即:capacity*2+1。
Hash沖突：
HashMap使用鏈表來解決碰撞問題逸贾，當發(fā)生碰撞了陨仅，對象將會儲存在鏈表的下一個節(jié)點中。
HashMap和Hashtable的區(qū)別
HashMap和Hashtable都實現了Map接口铝侵，但決定用哪一個之前先要弄清楚它們之間的分別灼伤。主要的區(qū)別有：線程安全性，同步(synchronization)咪鲜，以及速度狐赡。
HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的嗜诀，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)猾警，而Hashtable則不行)。
HashMap是非synchronized隆敢，而Hashtable是synchronized发皿，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable拂蝎；而如果沒有正確的同步的話穴墅，多個線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代玄货，比HashTable的擴展性更好皇钞。
另一個區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的松捉。所以當有其它線程改變了HashMap的結構（增加或者移除元素）夹界，將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常隘世。但這并不是一個一定發(fā)生的行為可柿，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別丙者。
由于Hashtable是線程安全的也是synchronized复斥，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步械媒，只需要單一線程目锭，那么使用HashMap性能要好過Hashtable。
HashMap不能保證隨著時間的推移Map中的元素次序是不變的纷捞。痢虹、
面試題
HashMap的工作原理是近年來常見的Java面試題。幾乎每個Java程序員都知道HashMap兰绣，都知道哪里要用HashMap世分，知道Hashtable和HashMap之間的區(qū)別，那么為何這道面試題如此特殊呢缀辩？是因為這道題考察的深度很深臭埋。這題經常出現在高級或中高級面試中。投資銀行更喜歡問這個問題臀玄，甚至會要求你實現HashMap來考察你的編程能力瓢阴。ConcurrentHashMap和其它同步集合的引入讓這道題變得更加復雜。讓我們開始探索的旅程吧健无！
“你用過HashMap嗎荣恐？” “什么是HashMap？你為什么用到它累贤？”
幾乎每個人都會回答“是的”叠穆，然后回答HashMap的一些特性，譬如HashMap可以接受null鍵值和值臼膏，而Hashtable則不能硼被；HashMap是非synchronized;HashMap很快；以及HashMap儲存的是鍵值對等等渗磅。這顯示出你已經用過HashMap嚷硫，而且對它相當的熟悉检访。但是面試官來個急轉直下，從此刻開始問出一些刁鉆的問題仔掸，關于HashMap的更多基礎的細節(jié)脆贵。面試官可能會問出下面的問題：
“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎起暮？”
你也許會回答“我沒有詳查標準的Java API卖氨，你可以看看Java源代碼或者Open JDK⌒常”“我可以用Google找到答案双泪。”
但一些面試者可能可以給出答案密似，“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中葫盼，使用get(key)從HashMap中獲取對象残腌。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法贫导，返回的hashCode用于找到bucket位置來儲存Entry對象抛猫。”這里關鍵點在于指出孩灯，HashMap是在bucket中儲存鍵對象和值對象闺金，作為Map.Entry。這一點有助于理解獲取對象的邏輯峰档。如果你沒有意識到這一點败匹，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯讥巡。這個答案相當的正確掀亩，也顯示出面試者確實知道hashing以及HashMap的工作原理。但是這僅僅是故事的開始欢顷，當面試官加入一些Java程序員每天要碰到的實際場景的時候槽棍，錯誤的答案頻現。下個問題可能是關于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()屢屢出現，而equals()方法僅僅在獲取值對象的時候才出現燎潮。一些優(yōu)秀的開發(fā)者會指出使用不可變的喻鳄、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話确封，將會減少碰撞的發(fā)生除呵，提高效率再菊。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度颜曾，使用String纠拔，Interger這樣的wrapper類作為鍵是非常好的選擇。
如果你認為到這里已經完結了泛豪，那么聽到下面這個問題的時候稠诲，你會大吃一驚」钍铮“如果HashMap的大小超過了負載因子(load factor)定義的容量臀叙，怎么辦？”除非你真正知道HashMap的工作原理价卤，否則你將回答不出這道題劝萤。默認的負載因子大小為0.75，也就是說慎璧，當一個map填滿了75%的bucket時候稳其，和其它集合類(如ArrayList等)一樣，將會創(chuàng)建原來HashMap大小的兩倍的bucket數組炸卑，來重新調整map的大小，并將原來的對象放入新的bucket數組中煤傍。這個過程叫作rehashing盖文，因為它調用hash方法找到新的bucket位置。
如果你能夠回答這道問題蚯姆，下面的問題來了：“你了解重新調整HashMap大小存在什么問題嗎五续？”你可能回答不上來，這時面試官會提醒你當多線程的情況下龄恋，可能產生條件競爭(race condition)疙驾。
當重新調整HashMap大小的時候，確實存在條件競爭郭毕，因為如果兩個線程都發(fā)現HashMap需要重新調整大小了它碎，它們會同時試著調整大小。在調整大小的過程中显押，存儲在鏈表中的元素的次序會反過來扳肛，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部乘碑，而是放在頭部挖息，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了兽肤，那么就死循環(huán)了套腹。
我們假設有兩個線程同時需要執(zhí)行resize操作绪抛，我們原來的桶數量為2，記錄數為3电禀，需要resize桶到4幢码，原來的記錄分別為：[3,A],[7,B],[5,C]，在原來的map里面鞭呕，我們發(fā)現這三個entry都落到了第二個桶里面蛤育。
假設線程thread1執(zhí)行到了transfer方法的Entry next = e.next這一句，然后時間片用完了葫松，此時的e = [3,A], next = [7,B]瓦糕。線程thread2被調度執(zhí)行并且順利完成了resize操作，需要注意的是腋么，此時的[7,B]的next為[3,A]咕娄。此時線程thread1重新被調度運行，此時的thread1持有的引用是已經被thread2 resize之后的結果珊擂。線程thread1首先將[3,A]遷移到新的數組上圣勒，然后再處理[7,B]，而[7,B]被鏈接到了[3,A]的后面摧扇，處理完[7,B]之后圣贸，就需要處理[7,B]的next了啊，而通過thread2的resize之后扛稽，[7,B]的next變?yōu)榱薣3,A]吁峻，此時，[3,A]和[7,B]形成了環(huán)形鏈表在张，在get的時候用含，如果get的key的桶索引和[3,A]和[7,B]一樣，那么就會陷入死循環(huán)帮匾。
為什么String, Interger這樣的wrapper類適合作為鍵啄骇？?String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用瘟斜。因為String是不可變的缸夹，也是final的，而且已經重寫了equals()和hashCode()方法了哼转。其他的wrapper類也有這個特點明未。不可變性是必要的，因為為了要計算hashCode()壹蔓，就要防止鍵值改變趟妥，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象佣蓉。不可變性還有其他的優(yōu)點如線程安全披摄。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的亲雪，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法疚膊，那么鍵對象正確的重寫這兩個方法是非常重要的义辕。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些寓盗，這樣就能提高HashMap的性能灌砖。
