作者：阿進(jìn)的寫字臺(tái) 來(lái)源：https://www.cnblogs.com/homejim/p/10029796.html

1、HashMap在JAVA中的怎么工作的？

基于Hash的原理。

2、什么是哈希？

最簡(jiǎn)單形式的 hash，是一種在對(duì)任何變量/對(duì)象的屬性應(yīng)用任何公式/算法后， 為其分配唯一代碼的方法。

一個(gè)真正的hash方法必須遵循下面的原則。

哈希函數(shù)每次在相同或相等的對(duì)象上應(yīng)用哈希函數(shù)時(shí), 應(yīng)每次返回相同的哈希碼。換句話說(shuō), 兩個(gè)相等的對(duì)象必須一致地生成相同的哈希碼。

Java 中所有的對(duì)象都有 Hash 方法。

Java中的所有對(duì)象都繼承 Object 類中定義的 hashCode() 函數(shù)的默認(rèn)實(shí)現(xiàn)。 此函數(shù)通常通過(guò)將對(duì)象的內(nèi)部地址轉(zhuǎn)換為整數(shù)來(lái)生成哈希碼，從而為所有不同的對(duì)象生成不同的哈希碼。

3、你清楚HashMap 中的 Node 類的結(jié)構(gòu)嗎？

Map的定義是： 將鍵映射到值的對(duì)象。

因此，HashMap 中必須有一些機(jī)制來(lái)存儲(chǔ)這個(gè)鍵值對(duì)。 答案是肯的。 HashMap 有一個(gè)內(nèi)部類 Node，如下所示。

當(dāng)然，Node 類具有存儲(chǔ)為屬性的鍵和值的映射。 key 已被標(biāo)記為 final，另外還有兩個(gè)字段：next 和 hash。

在下面中， 我們將會(huì)理解這些屬性的必須性。

4、鍵值對(duì)在 HashMap中是如何存儲(chǔ)的？

鍵值對(duì)在 HashMap 中是以 Node 內(nèi)部類的數(shù)組存放的，如下所示。

transient Node[] table;

哈希碼計(jì)算出來(lái)之后， 會(huì)轉(zhuǎn)換成該數(shù)組的下標(biāo)， 在該下標(biāo)中存儲(chǔ)對(duì)應(yīng)哈希碼的鍵值對(duì)， 在此先不詳細(xì)講解hash碰撞的情況。

該數(shù)組的長(zhǎng)度始終是2的次冪， 通過(guò)以下的函數(shù)實(shí)現(xiàn)該過(guò)程。

其原理是將傳入?yún)?shù) (cap) 的低二進(jìn)制全部變?yōu)?，最后加1即可獲得對(duì)應(yīng)的大于 cap 的 2 的次冪作為數(shù)組長(zhǎng)度。

為什么要使用2的次冪作為數(shù)組的容量呢？

在此有涉及到 HashMap 的 hash 函數(shù)及數(shù)組下標(biāo)的計(jì)算， 鍵(key)所計(jì)算出來(lái)的哈希碼有可能是大于數(shù)組的容量的，那怎么辦？ 可以通過(guò)簡(jiǎn)單的求余運(yùn)算來(lái)獲得，但此方法效率太低。HashMap中通過(guò)以下的方法保證 hash 的值計(jì)算后都小于數(shù)組的容量。

(n - 1) & hash

這也正好解釋了為什么需要2的次冪作為數(shù)組的容量。由于n是2的次冪，因此，n-1類似于一個(gè)低位掩碼。通過(guò)與操作，高位的hash值全部歸零，保證低位才有效 從而保證獲得的值都小于n。

同時(shí)，在下一次 resize() 操作時(shí)， 重新計(jì)算每個(gè) Node 的數(shù)組下標(biāo)將會(huì)因此變得很簡(jiǎn)單，具體的后文講解。以默認(rèn)的初始值16為例。

01010011 00100101 01010100 00100101& 00000000 00000000 00000000 00001111---------------------------------- 00000000 00000000 00000000 00000101 //高位全部歸零，只保留末四位 // 保證了計(jì)算出的值小于數(shù)組的長(zhǎng)度 n

但是，使用了該功能之后，由于只取了低位，因此 hash 碰撞會(huì)也會(huì)相應(yīng)的變得很嚴(yán)重。這時(shí)候就需要使用「擾動(dòng)函數(shù)」。

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

該函數(shù)通過(guò)將哈希碼的高16位的右移后與原哈希碼進(jìn)行異或而得到，以上面的例子為例。

此方法保證了高16位不變， 低16位根據(jù)異或后的結(jié)果改變。計(jì)算后的數(shù)組下標(biāo)將會(huì)從原先的5變?yōu)?。

使用了 「擾動(dòng)函數(shù)」 之后， hash 碰撞的概率將會(huì)下降。 有人專門做過(guò)類似的測(cè)試， 雖然使用該 「擾動(dòng)函數(shù)」 并沒(méi)有獲得最大概率的避免 hash 碰撞，但考慮其計(jì)算性能和碰撞的概率， JDK 中使用了該方法，且只hash一次。

5、哈希碰撞是如何處理的？

在理想的情況下， 哈希函數(shù)將每一個(gè) key 都映射到一個(gè)唯一的 bucket， 然而， 這是不可能的。哪怕是設(shè)計(jì)在良好的哈希函數(shù)，也會(huì)產(chǎn)生哈希沖突。

前人研究了很多哈希沖突的解決方法，在維基百科中，總結(jié)出了四大類。

在 Java 的 HashMap 中， 采用了第一種 Separate chaining 方法(大多數(shù)翻譯為拉鏈法)+鏈表和紅黑樹(shù)來(lái)解決沖突。

在 HashMap 中， 哈希碰撞之后會(huì)通過(guò) Node 類內(nèi)部的成員變量 Node next; 來(lái)形成一個(gè)鏈表(節(jié)點(diǎn)小于8)或紅黑樹(shù)(節(jié)點(diǎn)大于8， 在小于6時(shí)會(huì)從新轉(zhuǎn)換為鏈表)， 從而達(dá)到解決沖突的目的。

static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;

6、HashMap 是如何初始化的？

public HashMap(); public HashMap(int initialCapacity); public HashMap(Map extends K, ? extends V> m); public HashMap(int initialCapacity, float loadFactor);

HashMap 中有四個(gè)構(gòu)造函數(shù)， 大多是初始化容量和負(fù)載因子的操作。以 public HashMap(int initialCapacity, float loadFactor) 為例。

通過(guò)該函數(shù)進(jìn)行了容量和負(fù)載因子的初始化，如果是調(diào)用的其他的構(gòu)造函數(shù)， 則相應(yīng)的負(fù)載因子和容量會(huì)使用默認(rèn)值(默認(rèn)負(fù)載因子=0.75， 默認(rèn)容量=16)。在此時(shí)， 還沒(méi)有進(jìn)行存儲(chǔ)容器 table 的初始化， 該初始化要延遲到第一次使用時(shí)進(jìn)行。

7、HashMap 中哈希表是如何動(dòng)態(tài)擴(kuò)容的？

所謂的哈希表， 指的就是下面這個(gè)類型為內(nèi)部類Node的 table 變量。

transient Node[] table;

作為數(shù)組， 其在初始化時(shí)就需要指定長(zhǎng)度。在實(shí)際使用過(guò)程中， 我們存儲(chǔ)的數(shù)量可能會(huì)大于該長(zhǎng)度，因此 HashMap 中定義了一個(gè)閾值參數(shù)(threshold)， 在存儲(chǔ)的容量達(dá)到指定的閾值時(shí)， 需要進(jìn)行擴(kuò)容。

我個(gè)人認(rèn)為初始化也是動(dòng)態(tài)擴(kuò)容的一種， 只不過(guò)其擴(kuò)容是容量從 0 擴(kuò)展到構(gòu)造函數(shù)中的數(shù)值(默認(rèn)16)。 而且不需要進(jìn)行元素的重hash.

7.1 擴(kuò)容發(fā)生的條件

初始化的話只要數(shù)值為空或者數(shù)組長(zhǎng)度為 0 就會(huì)進(jìn)行。 而擴(kuò)容是在元素的數(shù)量大于閾值(threshold)時(shí)就會(huì)觸發(fā)。

threshold = loadFactor * capacity

比如 HashMap 中默認(rèn)的 loadFactor=0.75, capacity=16, 則。

threshold = loadFactor * capacity = 0.75 * 16 = 12

那么在元素?cái)?shù)量大于 12 時(shí)， 就會(huì)進(jìn)行擴(kuò)容。 擴(kuò)容后的 capacity 和 threshold 也會(huì)隨之而改變。

負(fù)載因子影響觸發(fā)的閾值，因此，它的值較小的時(shí)候，HashMap 中的 hash 碰撞就很少， 此時(shí)存取的性能都很高，對(duì)應(yīng)的缺點(diǎn)是需要較多的內(nèi)存；而它的值較大時(shí)，HashMap 中的 hash 碰撞就很多，此時(shí)存取的性能相對(duì)較低，對(duì)應(yīng)優(yōu)點(diǎn)是需要較少的內(nèi)存；不建議更改該默認(rèn)值，如果要更改，建議進(jìn)行相應(yīng)的測(cè)試之后確定。

7.2 再談容量為2的整數(shù)次冪和數(shù)組索引計(jì)算

前面說(shuō)過(guò)了數(shù)組的容量為 2 的整次冪， 同時(shí)， 數(shù)組的下標(biāo)通過(guò)下面的代碼進(jìn)行計(jì)算。

index = (table.length - 1) & hash

該方法除了可以很快的計(jì)算出數(shù)組的索引之外， 在擴(kuò)容之后， 進(jìn)行重 hash 時(shí)也會(huì)很巧妙的就可以算出新的 hash 值。 由于數(shù)組擴(kuò)容之后， 容量是現(xiàn)在的 2 倍， 擴(kuò)容之后 n-1 的有效位會(huì)比原來(lái)多一位， 而多的這一位與原容量二進(jìn)制在同一個(gè)位置。 示例。

這樣就可以很快的計(jì)算出新的索引啦。

7.3 步驟

• 先判斷是初始化還是擴(kuò)容， 兩者在計(jì)算newCap和newThr時(shí)會(huì)不一樣
• 計(jì)算擴(kuò)容后的容量，臨界值。
• 將hashMap的臨界值修改為擴(kuò)容后的臨界值
• 根據(jù)擴(kuò)容后的容量新建數(shù)組，然后將hashMap的table的引用指向新數(shù)組。
• 將舊數(shù)組的元素復(fù)制到table中。在該過(guò)程中， 涉及到幾種情況， 需要分開(kāi)進(jìn)行處理(只存有一個(gè)元素， 一般鏈表， 紅黑樹(shù))

具體的看代碼吧。

7.4 注意事項(xiàng)

雖然 HashMap 設(shè)計(jì)的非常優(yōu)秀， 但是應(yīng)該盡可能少的避免 resize(), 該過(guò)程會(huì)很耗費(fèi)時(shí)間。

同時(shí)， 由于 hashmap 不能自動(dòng)的縮小容量 因此，如果你的 hashmap 容量很大，但執(zhí)行了很多 remove操作時(shí)，容量并不會(huì)減少。如果你覺(jué)得需要減少容量，請(qǐng)重新創(chuàng)建一個(gè) hashmap。

8、HashMap.put() 函數(shù)內(nèi)部是如何工作的？

在使用多次 HashMap 之后， 大體也能說(shuō)出其添加元素的原理：計(jì)算每一個(gè)key的哈希值， 通過(guò)一定的計(jì)算之后算出其在哈希表中的位置，將鍵值對(duì)放入該位置，如果有哈希碰撞則進(jìn)行哈希碰撞處理。

而其工作時(shí)的原理如下。

源碼如下。

在此過(guò)程中， 會(huì)涉及到哈希碰撞的解決。

9、HashMap.get() 方法內(nèi)部是如何工作的？

其最終是調(diào)用了 getNode 函數(shù)。 其邏輯如下。

源碼如下。

總結(jié)

以上是生活随笔為你收集整理的hashmap remove 没释放内存_面试题：来，问你几个关于HashMap的问题？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。