HashMap提供高效的查找，插入和刪除。是怎么做到的？

HashMap的存儲結構

HashMap底層是以數組方式進行存儲的。將key-value鍵值對作為數組的一個元素進行存儲。
Key-value都是Map.Entry中的屬性。其中將key的值進行hash之后進行存儲，即每一個key都是計算hash值，然后再存儲。每一個hash值對應一個數組下標，數組下標是根據hash值和數組長度計算得來的。
由于不同的key值可能具有相同的hash值，即一個數組的某個位置出現兩個相同的元素，對于這種情況，hashmap采用鏈表的形式進行存儲。

hashing(哈希法)的概念

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

對比：Hashtable、HashMap、TreeMap

Hashtable 是早期Java類庫提供的一個哈希表實現，本身是同步的，不支持 null 鍵和值，由于同步導致的性能開銷，所以已經很少被推薦使用。

HashMap與 HashTable主要區別在于 HashMap 不是同步的，支持 null 鍵和值等。通常情況下，HashMap 進行 put 或者 get 操作，可以達到常數時間的性能，所以它是絕大部分利用鍵值對存取場景的首選。

TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map，和 HashMap 不同，它的 get、put、remove 之類操作都是 O（log(n)）的時間復雜度，具體順序可以由指定的 Comparator 來決定，或者根據鍵的自然順序來判斷。

HashMap概念和底層結構

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

HashMap 內部結構：可以看作是數組和鏈表結合組成的復合結構，數組被分為一個個桶（bucket），每個桶存儲有一個或多個Entry對象，每個Entry對象包含三部分key（鍵）、value（值），next(指向下一個Entry），通過哈希值決定了Entry對象在這個數組的尋址；哈希值相同的Entry對象（鍵值對），則以鏈表形式存儲。如果鏈表大小超過樹形轉換的閾值（TREEIFY_THRESHOLD= 8），鏈表就會被改造為樹形結構。

hashMap的結構示意圖如下：

查詢時間復雜度：HashMap的本質可以認為是一個數組，數組的每個索引被稱為桶，每個桶里放著一個單鏈表，一個節點連著一個節點。很明顯通過下標來檢索數組元素時間復雜度為O(1)，而且遍歷鏈表的時間復雜度是O(n)，所以在鏈表長度盡可能短的前提下，HashMap的查詢復雜度接近O(1)

數組：存儲區間連續，占用內存嚴重，尋址容易，插入刪除困難；
鏈表：存儲區間離散，占用內存比較寬松，尋址困難，插入刪除容易；
Hashmap綜合應用了這兩種數據結構，實現了尋址容易，插入刪除也容易。

HashMap的工作原理

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

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取值的方法，過程如下:

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

②.調用內部方法 getNode()，得到桶號(一般為hash值對桶數求模)
int index =hash%Entry[].length;
jdk1.6版本后使用位運算替代模運算，int index=hash&( Entry[].length - 1）;

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

④.如果得到 key 所在的桶的頭結點恰好是紅黑樹節點，就調用紅黑樹節點的 getTreeNode() 方法，否則就遍歷鏈表節點。getTreeNode 方法使通過調用樹形節點的 find()方法進行查找。由于之前添加時已經保證這個樹是有序的，因此查找時基本就是折半查找，效率很高。

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

如何重新調整HashMap的大小

“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？”
HashMap的擴容閾值（threshold = capacity* loadFactor 容量范圍是16~2的30次方），就是通過它和size進行比較來判斷是否需要擴容。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket數組（jdk1.6，但不超過最大容量），來重新調整map的大小，并將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。

解決 hash 沖突的常見方法

針對哈希表直接定址可能存在hash沖突，舉一個簡單的例子，例如：
第一個鍵值對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這個屬性鏈接在一起。 對于不同的元素，可能計算出了相同的函數值，這樣就產生了hash 沖突，那要解決沖突，又有哪些方法呢？具體如下：

a. 鏈地址法：將哈希表的每個單元作為鏈表的頭結點，所有哈希地址為 i 的元素構成一個同義詞鏈表。即發生沖突時就把該關鍵字鏈在以該單元為頭結點的鏈表的尾部。

b. 開放定址法：即發生沖突時，去尋找下一個空的哈希地址。只要哈希表足夠大，總能找到空的哈希地址。

c. 再哈希法：即發生沖突時，由其他的函數再計算一次哈希值。

d. 建立公共溢出區：將哈希表分為基本表和溢出表，發生沖突時，將沖突的元素放入溢出表。

HashMap采用哪種方法解決沖突的呢？

HashMap 就是使用鏈地址法來解決沖突的（jdk8中采用平衡樹來替代鏈表存儲沖突的元素，但hash() 方法原理相同）。當兩個對象的hashcode相同時，它們的bucket位置相同，碰撞就會發生。此時，可以將 put 進來的 K- V 對象插入到鏈表的尾部。對于儲存在同一個bucket位置的鏈表對象，可通過鍵對象的equals()方法用來找到鍵值對
————————————————
版權聲明：本文為CSDN博主「visant」的原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/visant/article/details/80045154

總結

以上是生活随笔為你收集整理的HashMap的存储原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。