1. HashMap簡介

HashMap - 顧名思義，就是用哈希表存儲鍵值映射昼汗，實現(xiàn)通過關鍵字查找對應值的功能肴熏；哈希表就是一種用于高效查找的數(shù)據結構。

2. 哈希表

哈希表（Hash Table）顷窒，又稱為散列表蛙吏，本質上是一個數(shù)組，其作用是能夠對大量的無規(guī)律數(shù)據進行高效的隨機存取操作鞋吉。

2.1 實現(xiàn)思想

哈希表的思想就是在元素的存儲位置（實際就是數(shù)組的下標）和元素的特征值（這個特征值可以是元素的值鸦做，關鍵字或其他可以標識該元素的屬性）之間建立某種直接關系，那么在進行存取時谓着，就無需做比較或只做很少次的比較泼诱，按照這種關系就可以直接由特征值找到相應記錄的位置；

2.2 為什么要使用哈希表

比如你有大量的字符串赊锚，現(xiàn)在要對這些字符串進行任意的隨機存取操作治筒，因為要進行隨機存取操作，所以適合采用順序存儲法改抡，可以將這些字符串存儲到一個數(shù)組中矢炼；這個時候，如果你要查找某一個字符串阿纤，就必須遍歷數(shù)組，與數(shù)組元素進行挨個比對夷陋，這十分的低效欠拾，同時由于元素是字符串胰锌，而折半查找或者構造2叉搜索樹等方法，都需要對元素進行排序藐窄，而對大量的字符串進行排序操作本身也是非常低效的操作资昧。有什么方法能夠對這些字符出進行高效的存取呢？我們可以采用哈希表荆忍，用某種計算法將字符串的特征值和數(shù)組的下標關聯(lián)起來格带，這樣在進行查找的時候，通過計算就可以對需要查找的值進行快速定位刹枉。

在計算機系統(tǒng)中叽唱，對于數(shù)據集合的存儲方式有兩種，一種是順序存儲法（數(shù)組微宝，向量棺亭，矩陣就是順序存儲法），一種是鏈式存儲法（比如鏈表蟋软，樹镶摘，圖都是鏈式存儲）；

2.3 如何實現(xiàn)哈希表

要實現(xiàn)哈希表岳守，需要考慮三個問題：1. 構造哈希函數(shù)凄敢；2. 處理哈希沖突；3. 調整裝填因子

2.3.1 構造哈希函數(shù)

哈希函數(shù)就是用來計算元素的哈希地址的方法 index=hash(key湿痢，length)涝缝，其中 index 就是哈希地址，實際就是數(shù)組下標蒙袍，key 是元素的特征值俊卤，length 是哈希表數(shù)組的長度，index 的值需要小于 length害幅。
構造哈希函數(shù)的方法很多消恍，應根據具體問題構造不同的函數(shù)，通常應遵循2個原則以现，考慮4個因素狠怨；

構造哈希函數(shù)需要遵循的兩個原則：

1. 函數(shù)計算要簡單，每一個特征值只能有一個哈希地址與其相對應邑遏；
2. 計算出的哈希地址的范圍必須在數(shù)組長度范圍內佣赖，并且分布應均勻，盡可能的減少沖突记盒；

構造哈希函數(shù)時需要考慮下面4個因素：

1. 哈希表的長度（也就是數(shù)組的大性鞲颉）；
2. 元素特征值分布情況；
3. 哈希函數(shù)的計算時間俩檬；
4. 記錄的查找頻率萎胰；

根據這兩個原則和四個因素，我們可以看到棚辽，高效的哈希表實現(xiàn)一定具有良好的特征值分布和適當大小的長度以及高效的哈希函數(shù)技竟；良好的特征值分布和適當?shù)拈L度可以使計算出的哈希地址盡量均勻，從而減少沖突屈藐；而高效的哈希函數(shù)可以快速的計算出哈希地址榔组；

2.3.2 處理哈希沖突

在實際應用中，可以盡量減少哈希沖突联逻，但卻不可避免搓扯，所以就需要處理哈希沖突，一般處理哈希沖突的方法有兩種：

• 開放地址法遣妥；基本思路就是把元素都存儲到哈希表的數(shù)組中擅编，當發(fā)生哈希沖突時，就在沖突地址的基礎上選擇合適的計算方法（比如線性探測法箫踩、二次探測法爱态、偽隨機探測法）重新計算新的地址，直到不發(fā)生沖突為止境钟；
• 鏈地址法锦担；基本思路就是把具有相同哈希地址的元素保存在同一個單鏈表中，而將單鏈表的頭部元素存放到哈希表的數(shù)組中慨削；當發(fā)生哈希沖突時洞渔，只需要把發(fā)生沖突的元素插入到對應哈希地址的鏈表的尾部即可；

而在實際應用中缚态，由于開放地址法可能發(fā)生二次聚集現(xiàn)象（線性探測法）以及不能保證一定找到不發(fā)生沖突的地址（二次探測法和偽隨機探測法）等問題磁椒，所以一般都采用鏈地址法；而鏈地址法并不局限于只采用單鏈表來保存發(fā)生沖突的元素玫芦，我們知道浆熔，單鏈表進行隨機查找的效率是很低的，需要進行遍歷比對桥帆，所以當某一個地址沖突的元素很多医增，鏈表很長，并且查找頻率又比較高時老虫，這時查找的效率就會很低叶骨，此時再采用單鏈表就不是很好，可以轉化成為其他數(shù)據結構以提高查詢效率祈匙。

2.3.3 調整裝填因子

影響到哈希表性能的第三個因素就是裝填因子忽刽，裝填因子定義為 α = 記錄數(shù) / 表長度；裝填因子 α 表示哈希表的裝滿程序，根據哈希表的實現(xiàn)思想我們可以看到缔恳，哈希沖突的可能性和裝填因子成正比宝剖，α 越大洁闰，表示表中的記錄越多歉甚，再加入新元素時，發(fā)生沖突的概率就越大扑眉，查找時纸泄，需要進行鏈表比對的次數(shù)也就越多；但是腰素，過低的裝填因子雖然有好的查找效率聘裁，但是卻浪費了存儲空間，因此在實現(xiàn)哈希表時弓千，需要確定將裝填因子的上限保持在某個水平衡便，如何確定裝填因子的上限呢？我們看下表：其中 α 表示裝填因子

用幾種不同方法處理沖突時哈希表的平均查找長度 - 表選自《數(shù)據結構》（嚴蔚敏）第二版

3. JDK中HashMap的實現(xiàn)

上一章我們討論了要實現(xiàn)一個高效的哈希表需要考慮的三個問題，本章我們看看JDK在實現(xiàn) HashMap 的過程中汁展，是如何解決這三個問題的鹊碍。

3.1 HashMap的哈希函數(shù)

HashMap 通過 key 的 hashCode 經過擾動函數(shù) (h = key.hashCode()) ^ (h >>> 16) 處理過后得到 hash 值，然后通過 (n - 1) & hash（這里的 n 指的是數(shù)組的長度）計算key 的哈希地址（數(shù)組下標）食绿；我們可以看到HashMap使用擾動過的hashCode作為key的特征值來計算哈希地址侈咕，這是因為hashCode默認是由對象的內存地址轉化而來，而對象存儲在內存的哪一個位置是完全隨機的器紧，并且符合均勻分布耀销，但是因為Object的hashCode的方法可以被子類重寫，因此為了防止那些由重寫的hashCode方法生成的hash碼的分布情況不夠均勻品洛，因此加入了擾動函數(shù)树姨。
從 HashMap 的哈希函數(shù)的源碼我們可以看到，HashMap 默認選擇由元素的內存地址轉化的 hashCode 作為元素特征值來計算哈希地址桥状，這樣的特征值符合均勻分布帽揪，使計算出的哈希地址盡量均勻，使哈希沖突發(fā)生的概率盡可能懈ㄕ濉转晰；同時 HashMap 使用了1次移位，2次邏輯運算就能夠計算出哈希地址，簡單高效查邢。

(h = key.hashCode()) ^ (h >>> 16) 表示：將 key 的 hashCode 的低16位與高16位進行異或蔗崎。

3.2 HashMap的沖突處理機制

HashMap 采用鏈地址法來解決哈希沖突；HashMap 將哈希地址沖突的元素保存在一個單鏈表中扰藕，哈希地址對應的數(shù)組位置保存該單鏈表的頭節(jié)點缓苛；當單鏈表的長度大于閾值（默認為8），此時如果哈希表的長度大于等于64邓深，單鏈表就會轉化成為一顆紅黑樹未桥，以加快查找速度，否則就要進行擴容resize操作芥备。
HashMap 這種沖突處理機制冬耿，不會出現(xiàn)二次聚集，可能無法找到無沖突地址的問題萌壳，并且查找效率高亦镶，插入移除元素易于實現(xiàn)，而且因為節(jié)點是動態(tài)生成的袱瓮，特別適合哈希表的長度需要經常變化的情況缤骨。

3.3 HashMap的裝填因子

HashMap 默認的裝填因子臨界值是0.75，為了保證哈希表的查詢效率懂讯，HashMap 會動態(tài)調整哈希表的大小荷憋，就是進行 resize 操作，來保持裝填因子不大于0.75褐望。
HashMap 每次進行 resize 操作勒庄，首先分配一個長度是舊表2倍的新表，然后遍歷舊表中的所有元素瘫里，重新計算每一個元素在新表中的哈希地址实蔽，讓后將元素插入到新表中，這個過程稱為rehash谨读，再哈希過程中局装，如果發(fā)生碰撞，還需要重新構建鏈表劳殖。
動態(tài)擴容機制可以使HashMap的裝填因子始終不超過臨界值铐尚，保證了查找效率，同時又提高了存儲空間的使用效率哆姻。但是由于動態(tài)擴容操作需要進行 rehash 操作宣增，尤其是當使用HashMap保存大量鍵值對的時候，rehash 會非常耗時矛缨，從而引起程序響應性問題爹脾。

3.4 HashMap小結

通過上一章的講解我們可以總結出 JDK 在實現(xiàn) HashMap 時采用了以下方法和機制：

1. 默認使用對象內存地址轉化而來的hashCode作為特征值來計算哈希地址帖旨，因為默認的hashCode符合均勻分布，可以將哈希碰撞的可能性降低到最辛榉痢解阅；
2. 使用移位和邏輯運算計算哈希地址，因為在計算機系統(tǒng)中泌霍，移位運算和邏輯運算比數(shù)學運算要快的多货抄，所以使用移位和邏輯運算計算哈希地址，簡單高效烹吵；
3. 使用拉鏈法來解決哈希沖突碉熄，當單鏈表的長度大于閾值（默認為8），哈希表長度大于64時肋拔，單鏈表會轉化成為紅黑樹，保證哈希查找的效率呀酸；
4. 采用動態(tài)擴容機制保證裝填因子始終不超過臨界值凉蜂，保證了查找效率，同時又提高了存儲空間的使用效率性誉。

4. 使用優(yōu)化

雖然JDK中的 HashMap 是一種高效的哈希表實現(xiàn)窿吩，但我們在使用過程中仍然需要注意以下問題：

1. 因為 Object 的hashCode方法可以被子類重寫，雖然 HashMap 使用了擾動函數(shù)错览，但是如果重寫的hashCode 方法返回的值的分布狀態(tài)非常不均勻纫雁，那么即使在裝填因子很低的時候，仍然會發(fā)生大量的哈希碰撞倾哺，導致查詢效率變低轧邪。因此如果需要重寫鍵對象的 hashCode 方法，那么應當確保重寫后的hashCode 方法返回的哈希碼要符合隨機的均勻分布羞海。
2. 因為動態(tài)擴容機制雖然使HashMap的裝填因子始終不超過臨界值忌愚，保證了查找效率，提高了存儲空間利用率却邓，但是動態(tài)擴容導致的 rehash 是一項很耗時的操作硕糊，尤其當 HashMap 很大時，需要在使用時盡量避免動態(tài)擴容（resize）操作腊徙。這就需要在使用時根據應用場景简十，事先規(guī)劃 HashMap 的容量大小和裝填因子，在創(chuàng)建時就指定表長度和裝填因子撬腾。當然在實際應用中螟蝙，無法一開始就確定 HashMap 的合適大小，可以先對需要優(yōu)化使用的HashMap 進行監(jiān)控时鸵，收集其每次動態(tài)擴容時元素的數(shù)量胶逢，集合的大小厅瞎，以及耗時等指標信息，然后再進行評估優(yōu)化初坠。

5. HashSet

java.util.HashSet<T> 是 Set 的實現(xiàn)類和簸，是一種集合，集合的最主要特性就是互異性（就是集合中任何兩個元素都認為是不相同的碟刺，即每個元素只能出現(xiàn)一次）锁保；HashSet 是使用裝飾器模式利用 HashMap 實現(xiàn)的集合類，底層就是一個 HashMap半沽，插入 HashSet 的元素作為鍵值和一個默認作為值的對象 PRESENT 組成鍵值對存儲在HashMap 中爽柒，HashSet 利用 Map 鍵值的不可重復特性來保證 Set 元素的不可重復特性，HashSet 是采用哈希表來保存元素的的集合類者填，可以對元素進行排重浩村，同時又能夠對這些數(shù)據進行高效的查詢。

HashSet 類的主要屬性：

private transient HashMap<E,Object> map; //用于存儲元素的HashMap
private static final Object PRESENT = new Object(); //一個靜態(tài)的全局對象PRESENT占哟，作為元素的value