HashMap實作原理分析

• hash概念
• HashMap概念
• • • 概念
    • 資料結構
• HashMap的基本存儲原理和工作原理
• • • HashMap的基本存儲原理以及存儲内容的組成
    • HashMap的工作原理以及存取方法過程
• HashMap具體分析
• • • HashMap具體的存取過程
    • HashMap中的碰撞探測(collision detection)以及碰撞的解決方法
    • HashMap擴容機制（如何調整HashMap的大小）
    • HashMap擴容可能存在的問題

hash概念

hashing(散列法或哈希法)的概念

散列法（Hashing）是一種将字元組成的字元串轉換為固定長度（一般是更短長度）的數值或索引值的方法，稱為散列法，也叫哈希法。由于通過更短的哈希值比用原始值進行資料庫搜尋更快，這種方法一般用來在資料庫中建立索引并進行搜尋，同時還用在各種解密算法中。

HashMap概念

概念

HashMap是基于哈希表的Map接口的非同步實作。此實作提供所有可選的映射操作，并允許使用null值和null鍵。HashMap儲存的是鍵值對，HashMap很快。此類不保證映射的順序，特别是，它不保證該順序恒久不變。

HashMap在Map體系中的位置：

資料結構

HashMap實際上是一個“連結清單散列”的資料結構，即數組和連結清單的結合體。

數組：存儲區間連續，占用記憶體嚴重，尋址容易，插入删除困難；

連結清單：存儲區間離散，占用記憶體比較寬松，尋址困難，插入删除容易；

Hashmap綜合應用了這兩種資料結構，實作了尋址容易，插入删除也容易。

HashMap的結構示意圖如下（本圖轉自阿裡雲）：

HashMap的基本存儲原理和工作原理

HashMap的基本存儲原理以及存儲内容的組成

基本原理：先聲明一個下标範圍比較大的數組來存儲元素。另外設計一個哈希函數（也叫做散列函數）來獲得每一個元素的Key（關鍵字）的函數值（即數組下标，hash值）相對應，數組存儲的元素是一個Entry類，這個類有三個資料域，key、value（鍵值對），next(指向下一個Entry)。

例如， 第一個鍵值對A進來。通過計算其key的hash得到的index=0。記做:Entry[0] = A。

第二個鍵值對B，通過計算其index也等于0， HashMap會将B.next =A,Entry[0] =B,

第三個鍵值對 C,index也等于0,那麼C.next = B,Entry[0] = C；這樣我們發現index=0的地方事實上存取了A,B,C三個鍵值對,它們通過next這個屬性連結在一起。我們可以将這個地方稱為桶。 對于不同的元素，可能計算出了相同的函數值，這樣就産生了“沖突”，這就需要解決沖突，“直接定址”與“解決沖突”是哈希表的兩大特點。

HashMap的工作原理以及存取方法過程

HashMap的工作原理 ：HashMap是基于散列法（又稱哈希法hashing）的原理，使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中擷取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，傳回的hashCode用于找到bucket（桶）位置來儲存Entry對象。”HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。并不是僅僅隻在bucket中存儲值。

HashMap具體分析

HashMap具體的存取過程

put鍵值對的方法的過程是（本圖轉自美團）：

①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；

②.根據鍵值key計算hash值得到插入的數組索引 i ，如果table[i]==null，直接建立節點添加，轉向⑥，如果table[i]不為空，轉向③；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆寫value，否則轉向④，這裡的相同指的是hashCode以及equals；

④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；

⑤.周遊table[i]，判斷連結清單長度是否大于8，大于8的話把連結清單轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行連結清單的插入操作；周遊過程中若發現key已經存在直接覆寫value即可；

⑥.插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。

get鍵值方法的過程是:

1、指定key 通過hash函數得到key的hash值 int hash=key.hashCode();

2、調用内部方法 getNode()，得到桶号(一般都為hash值對桶數求模)

int index =hash%Entry[].length;

3、比較桶的内部元素是否與key相等，若都不相等，則沒有找到。相等，則取出相等記錄的value。

4、如果得到 key 所在的桶的頭結點恰好是紅黑樹節點，就調用紅黑樹節點的 getTreeNode() 方法，否則就周遊連結清單節點。getTreeNode 方法使通過調用樹形節點的 find()方法進行查找。由于之前添加時已經保證這個樹是有序的，是以查找時基本就是折半查找，效率很高。

5、如果對比節點的哈希值和要查找的哈希值相等，就會判斷 key 是否相等，相等就直接傳回；不相等就從子樹中遞歸查找。

HashMap中直接位址用hash函數生成；解決沖突，用比較函數解決。如果每個桶内部隻有一個元素，那麼查找的時候隻有一次比較。當許多桶内沒有值時，許多查詢就會更快了(指查不到的時候)。

HashMap中的碰撞探測(collision detection)以及碰撞的解決方法

1、當兩個對象的hashcode相同時，會發生什麼？

當兩個對象的hashcode相同時，它們的bucket位置相同，‘碰撞’會發生。因為HashMap使用LinkedList存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在LinkedList中。這兩個對象就算hashcode相同，但是它們可能并不相等。

2、當兩個對象的hashcode相同時，那如何擷取這兩個對象的值呢？

當兩個對象的hashcode相同時，我們調用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，周遊LinkedList直到找到值對象。找到bucket位置之後，會調用keys.equals()方法去找到LinkedList中正确的節點，最終找到要找的值對象使用不可變的、聲明作final的對象，并且采用合适的equals()和hashCode()方法的話，将會減少碰撞的發生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這将提高整個擷取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。

HashMap擴容機制（如何調整HashMap的大小）

擴容(resize)就是重新計算容量，向HashMap對象裡不停地添加元素，而HashMap對象内部的數組無法裝載更多的元素時，對象就需要擴大數組的長度，以便能裝入更多的元素。

HashMap的一個執行個體有兩個影響其性能的參數： 初始容量和負載因子。 容量是哈希表中的桶數，初始容量隻是建立哈希表時的容量。 負載因子是在容量自動增加之前允許哈希表得到滿足的度量。 當在散清單中的條目的數量超過了負載因數和電流容量的乘積，哈希表被重新散列（即，内部資料結構被重建），使得哈希表具有桶的大約兩倍。

作為一般規則，預設負載因子（0.75）提供了時間和空間成本之間的良好折中。 更高的值會降低空間開銷，但會增加查找成本（反映在HashMap類的大部分操作中，包括 get 和 put ）。在設定其初始容量時，應考慮 Map 中預期的條目數及其負載因子，以便最小化重新多點傳播操作的數量。 如果初始容量大于最大條目數除以負載因子，則不會發生重新排列操作。

HashMap擴容可能存在的問題

當重新調整HashMap大小的時候，在多線程的情況下，可能存在條件競争(race condition)，因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試着調整大小。在調整大小的過程中，存儲在連結清單中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會将元素放在連結清單的尾部，而是放在頭部，這是為了避免尾部周遊(tail traversing)。如果條件競争發生了，那麼就死循環了。

參照：

http://www.importnew.com/7099.html

https://blog.csdn.net/excellentyuxiao/article/details/52344819