你知道HashMap中hash方法的具體實(shí)現(xiàn)嗎？你知道HashTable、ConcurrentHashMap中hash方法的實(shí)現(xiàn)以及原因嗎？你知道為什么要這么實(shí)現(xiàn)嗎？你知道為什么JDK 7和JDK 8中hash方法實(shí)現(xiàn)的不同以及區(qū)別嗎？如果你不能很好的回答這些問(wèn)題，那么你需要好好看看這篇文章。文中涉及到大量代碼和計(jì)算機(jī)底層原理知識(shí)。絕對(duì)的干貨滿(mǎn)滿(mǎn)。整個(gè)互聯(lián)網(wǎng)，把hash()分析的如此透徹的，別無(wú)二家。

哈希

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長(zhǎng)度的輸入，通過(guò)散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，所以不可能從散列值來(lái)唯一的確定輸入值。簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。

所有散列函數(shù)都有如下一個(gè)基本特性：根據(jù)同一散列函數(shù)計(jì)算出的散列值如果不同，那么輸入值肯定也不同。但是，根據(jù)同一散列函數(shù)計(jì)算出的散列值如果相同，輸入值不一定相同。

兩個(gè)不同的輸入值，根據(jù)同一散列函數(shù)計(jì)算出的散列值相同的現(xiàn)象叫做碰撞。

常見(jiàn)的Hash函數(shù)有以下幾個(gè)：

直接定址法：直接以關(guān)鍵字k或者k加上某個(gè)常數(shù)（k+c）作為哈希地址。

數(shù)字分析法：提取關(guān)鍵字中取值比較均勻的數(shù)字作為哈希地址。

除留余數(shù)法：用關(guān)鍵字k除以某個(gè)不大于哈希表長(zhǎng)度m的數(shù)p，將所得余數(shù)作為哈希表地址。

分段疊加法：按照哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分，其中最后一部分可以比較短。然后將這幾部分相加，舍棄最高進(jìn)位后的結(jié)果就是該關(guān)鍵字的哈希地址。

平方取中法：如果關(guān)鍵字各個(gè)部分分布都不均勻的話，可以先求出它的平方值，然后按照需求取中間的幾位作為哈希地址。

偽隨機(jī)數(shù)法：采用一個(gè)偽隨機(jī)數(shù)當(dāng)作哈希函數(shù)。

上面介紹過(guò)碰撞。衡量一個(gè)哈希函數(shù)的好壞的重要指標(biāo)就是發(fā)生碰撞的概率以及發(fā)生碰撞的解決方案。任何哈希函數(shù)基本都無(wú)法徹底避免碰撞，常見(jiàn)的解決碰撞的方法有以下幾種：

• 開(kāi)放定址法：
  • 開(kāi)放定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。
• 鏈地址法
  • 將哈希表的每個(gè)單元作為鏈表的頭結(jié)點(diǎn)，所有哈希地址為i的元素構(gòu)成一個(gè)同義詞鏈表。即發(fā)生沖突時(shí)就把該關(guān)鍵字鏈在以該單元為頭結(jié)點(diǎn)的鏈表的尾部。
• 再哈希法
  • 當(dāng)哈希地址發(fā)生沖突用其他的函數(shù)計(jì)算另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再產(chǎn)生為止。
• 建立公共溢出區(qū)
  • 將哈希表分為基本表和溢出表兩部分，發(fā)生沖突的元素都放入溢出表中。

HashMap 的數(shù)據(jù)結(jié)構(gòu)

在Java中，保存數(shù)據(jù)有兩種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表。數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。上面我們提到過(guò)，常用的哈希函數(shù)的沖突解決辦法中有一種方法叫做鏈地址法，其實(shí)就是將數(shù)組和鏈表組合在一起，發(fā)揮了兩者的優(yōu)勢(shì)，我們可以將其理解為鏈表的數(shù)組。

我們可以從上圖看到，左邊很明顯是個(gè)數(shù)組，數(shù)組的每個(gè)成員是一個(gè)鏈表。該數(shù)據(jù)結(jié)構(gòu)所容納的所有元素均包含一個(gè)指針，用于元素間的鏈接。我們根據(jù)元素的自身特征把元素分配到不同的鏈表中去，反過(guò)來(lái)我們也正是通過(guò)這些特征找到正確的鏈表，再?gòu)逆湵碇姓页稣_的元素。其中，根據(jù)元素特征計(jì)算元素?cái)?shù)組下標(biāo)的方法就是哈希算法，即本文的主角hash()函數(shù)（當(dāng)然，還包括indexOf()函數(shù)）。

hash方法

我們拿JDK 1.7的HashMap為例，其中定義了一個(gè)final int hash(Object k) 方法，其主要被以下方法引用。

上面的方法主要都是增加和刪除方法，這不難理解，當(dāng)我們要對(duì)一個(gè)鏈表數(shù)組中的某個(gè)元素進(jìn)行增刪的時(shí)候，首先要知道他應(yīng)該保存在這個(gè)鏈表數(shù)組中的哪個(gè)位置，即他在這個(gè)數(shù)組中的下標(biāo)。而hash()方法的功能就是根據(jù)Key來(lái)定位其在HashMap中的位置。HashTable、ConcurrentHashMap同理。

源碼解析

首先，在同一個(gè)版本的Jdk中，HashMap、HashTable以及ConcurrentHashMap里面的hash方法的實(shí)現(xiàn)是不同的。再不同的版本的JDK中（Java7 和 Java8）中也是有區(qū)別的。我會(huì)盡量全部介紹到。相信，看文這篇文章，你會(huì)徹底理解hash方法。

在上代碼之前，我們先來(lái)做個(gè)簡(jiǎn)單分析。我們知道，hash方法的功能是根據(jù)Key來(lái)定位這個(gè)K-V在鏈表數(shù)組中的位置的。也就是hash方法的輸入應(yīng)該是個(gè)Object類(lèi)型的Key，輸出應(yīng)該是個(gè)int類(lèi)型的數(shù)組下標(biāo)。如果讓你設(shè)計(jì)這個(gè)方法，你會(huì)怎么做？

其實(shí)簡(jiǎn)單，我們只要調(diào)用Object對(duì)象的hashCode()方法，該方法會(huì)返回一個(gè)整數(shù)，然后用這個(gè)數(shù)對(duì)HashMap或者HashTable的容量進(jìn)行取模就行了。沒(méi)錯(cuò)，其實(shí)基本原理就是這個(gè)，只不過(guò)，在具體實(shí)現(xiàn)上，由兩個(gè)方法int hash(Object k)和int indexFor(int h, int length)來(lái)實(shí)現(xiàn)。但是考慮到效率等問(wèn)題，HashMap的實(shí)現(xiàn)會(huì)稍微復(fù)雜一點(diǎn)。

hash ：該方法主要是將Object轉(zhuǎn)換成一個(gè)整型。

indexFor ：該方法主要是將hash生成的整型轉(zhuǎn)換成鏈表數(shù)組中的下標(biāo)。

HashMap In Java 7

final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4); }static int indexFor(int h, int length) {return h & (length-1); }

前面我說(shuō)過(guò)，indexFor方法其實(shí)主要是將hash生成的整型轉(zhuǎn)換成鏈表數(shù)組中的下標(biāo)。那么return h & (length-1);是什么意思呢？其實(shí)，他就是取模。Java之所有使用位運(yùn)算(&)來(lái)代替取模運(yùn)算(%)，最主要的考慮就是效率。位運(yùn)算(&)效率要比代替取模運(yùn)算(%)高很多，主要原因是位運(yùn)算直接對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作，不需要轉(zhuǎn)成十進(jìn)制，因此處理速度非常快。

那么，為什么可以使用位運(yùn)算(&)來(lái)實(shí)現(xiàn)取模運(yùn)算(%)呢？這實(shí)現(xiàn)的原理如下：

X % 2^n = X & (2^n – 1)

2^n表示2的n次方，也就是說(shuō)，一個(gè)數(shù)對(duì)2^n取模 == 一個(gè)數(shù)和(2^n – 1)做按位與運(yùn)算 。

假設(shè)n為3，則2^3 = 8，表示成2進(jìn)制就是1000。2^3 -1 = 7 ，即0111。

此時(shí)X & (2^3 – 1) 就相當(dāng)于取X的2進(jìn)制的最后三位數(shù)。

從2進(jìn)制角度來(lái)看，X / 8相當(dāng)于 X >> 3，即把X右移3位，此時(shí)得到了X / 8的商，而被移掉的部分(后三位)，則是X % 8，也就是余數(shù)。

上面的解釋不知道你有沒(méi)有看懂，沒(méi)看懂的話其實(shí)也沒(méi)關(guān)系，你只需要記住這個(gè)技巧就可以了。或者你可以找?guī)讉€(gè)例子試一下。

6 % 8 = 6 ，6 & 7 = 6

10 & 8 = 2 ，10 & 7 = 2

所以，return h & (length-1);只要保證length的長(zhǎng)度是2^n的話，就可以實(shí)現(xiàn)取模運(yùn)算了。而HashMap中的length也確實(shí)是2的倍數(shù)，初始值是16，之后每次擴(kuò)充為原來(lái)的2倍。

分析完indexFor方法后，我們接下來(lái)準(zhǔn)備分析hash方法的具體原理和實(shí)現(xiàn)。在深入分析之前，至此，先做個(gè)總結(jié)。

HashMap的數(shù)據(jù)是存儲(chǔ)在鏈表數(shù)組里面的。在對(duì)HashMap進(jìn)行插入/刪除等操作時(shí)，都需要根據(jù)K-V對(duì)的鍵值定位到他應(yīng)該保存在數(shù)組的哪個(gè)下標(biāo)中。而這個(gè)通過(guò)鍵值求取下標(biāo)的操作就叫做哈希。HashMap的數(shù)組是有長(zhǎng)度的，Java中規(guī)定這個(gè)長(zhǎng)度只能是2的倍數(shù)，初始值為16。簡(jiǎn)單的做法是先求取出鍵值的hashcode，然后在將hashcode得到的int值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模。為了考慮性能，Java總采用按位與操作實(shí)現(xiàn)取模操作。

接下來(lái)我們會(huì)發(fā)現(xiàn)，無(wú)論是用取模運(yùn)算還是位運(yùn)算都無(wú)法直接解決沖突較大的問(wèn)題。比如：CA11 0000和0001 0000在對(duì)0000 1111進(jìn)行按位與運(yùn)算后的值是相等的。

兩個(gè)不同的鍵值，在對(duì)數(shù)組長(zhǎng)度進(jìn)行按位與運(yùn)算后得到的結(jié)果相同，這不就發(fā)生了沖突嗎。那么如何解決這種沖突呢，來(lái)看下Java是如何做的。

其中的主要代碼部分如下：

h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);

這段代碼是為了對(duì)key的hashCode進(jìn)行擾動(dòng)計(jì)算，防止不同hashCode的高位不同但低位相同導(dǎo)致的hash沖突。簡(jiǎn)單點(diǎn)說(shuō)，就是為了把高位的特征和低位的特征組合起來(lái)，降低哈希沖突的概率，也就是說(shuō)，盡量做到任何一位的變化都能對(duì)最終得到的結(jié)果產(chǎn)生影響。

舉個(gè)例子來(lái)說(shuō)，我們現(xiàn)在想向一個(gè)HashMap中put一個(gè)K-V對(duì)，Key的值為“hollischuang”，經(jīng)過(guò)簡(jiǎn)單的獲取hashcode后，得到的值為“1011000110101110011111010011011”，如果當(dāng)前HashTable的大小為16，即在不進(jìn)行擾動(dòng)計(jì)算的情況下，他最終得到的index結(jié)果值為11。由于15的二進(jìn)制擴(kuò)展到32位為“00000000000000000000000000001111”，所以，一個(gè)數(shù)字在和他進(jìn)行按位與操作的時(shí)候，前28位無(wú)論是什么，計(jì)算結(jié)果都一樣（因?yàn)?和任何數(shù)做與，結(jié)果都為0）。如下圖所示。

可以看到，后面的兩個(gè)hashcode經(jīng)過(guò)位運(yùn)算之后得到的值也是11 ，雖然我們不知道哪個(gè)key的hashcode是上面例子中的那兩個(gè)，但是肯定存在這樣的key，這就產(chǎn)生了沖突。

那么，接下來(lái)，我看看一下經(jīng)過(guò)擾動(dòng)的算法最終的計(jì)算結(jié)果會(huì)如何。

從上面圖中可以看到，之前會(huì)產(chǎn)生沖突的兩個(gè)hashcode，經(jīng)過(guò)擾動(dòng)計(jì)算之后，最終得到的index的值不一樣了，這就很好的避免了沖突。

其實(shí)，使用位運(yùn)算代替取模運(yùn)算，除了性能之外，還有一個(gè)好處就是可以很好的解決負(fù)數(shù)的問(wèn)題。因?yàn)槲覀冎?#xff0c;hashcode的結(jié)果是int類(lèi)型，而int的取值范圍是-2^31 ~ 2^31 – 1，即[ -2147483648, 2147483647]；這里面是包含負(fù)數(shù)的，我們知道，對(duì)于一個(gè)負(fù)數(shù)取模還是有些麻煩的。如果使用二進(jìn)制的位運(yùn)算的話就可以很好的避免這個(gè)問(wèn)題。首先，不管hashcode的值是正數(shù)還是負(fù)數(shù)。length-1這個(gè)值一定是個(gè)正數(shù)。那么，他的二進(jìn)制的第一位一定是0（有符號(hào)數(shù)用最高位作為符號(hào)位，“0”代表“+”，“1”代表“-”），這樣里兩個(gè)數(shù)做按位與運(yùn)算之后，第一位一定是個(gè)0，也就是，得到的結(jié)果一定是個(gè)正數(shù)。

HashTable In Java 7

上面是Java 7中HashMap的hash方法以及indexOf方法的實(shí)現(xiàn)，那么接下來(lái)我們要看下，線程安全的HashTable是如何實(shí)現(xiàn)的，和HashMap有何不同，并試著分析下不同的原因。以下是Java 7中HashTable的hash方法的實(shí)現(xiàn)。

private int hash(Object k) {// hashSeed will be zero if alternative hashing is disabled.return hashSeed ^ k.hashCode(); }

我們可以發(fā)現(xiàn)，很簡(jiǎn)單，相當(dāng)于只是對(duì)k做了個(gè)簡(jiǎn)單的hash，取了一下其hashCode。而HashTable中也沒(méi)有indexOf方法，取而代之的是這段代碼：int index = (hash & 0x7FFFFFFF) % tab.length;。也就是說(shuō)，HashMap和HashTable對(duì)于計(jì)算數(shù)組下標(biāo)這件事，采用了兩種方法。HashMap采用的是位運(yùn)算，而HashTable采用的是直接取模。

為啥要把hash值和0x7FFFFFFF做一次按位與操作呢，主要是為了保證得到的index的第一位為0，也就是為了得到一個(gè)正數(shù)。因?yàn)橛蟹?hào)數(shù)第一位0代表正數(shù)，1代表負(fù)數(shù)。

我們前面說(shuō)過(guò)，HashMap之所以不用取模的原因是為了提高效率。有人認(rèn)為，因?yàn)镠ashTable是個(gè)線程安全的類(lèi)，本來(lái)就慢，所以Java并沒(méi)有考慮效率問(wèn)題，就直接使用取模算法了呢？但是其實(shí)并不完全是，Java這樣設(shè)計(jì)還是有一定的考慮在的，雖然這樣效率確實(shí)是會(huì)比HashMap慢一些。

其實(shí)，HashTable采用簡(jiǎn)單的取模是有一定的考慮在的。這就要涉及到HashTable的構(gòu)造函數(shù)和擴(kuò)容函數(shù)了。由于篇幅有限，這里就不貼代碼了，直接給出結(jié)論：

HashTable默認(rèn)的初始大小為11，之后每次擴(kuò)充為原來(lái)的2n+1。

也就是說(shuō)，HashTable的鏈表數(shù)組的默認(rèn)大小是一個(gè)素?cái)?shù)、奇數(shù)。之后的每次擴(kuò)充結(jié)果也都是奇數(shù)。

由于HashTable會(huì)盡量使用素?cái)?shù)、奇數(shù)作為容量的大小。當(dāng)哈希表的大小為素?cái)?shù)時(shí)，簡(jiǎn)單的取模哈希的結(jié)果會(huì)更加均勻。（這個(gè)是可以證明出來(lái)的，由于不是本文重點(diǎn)，暫不詳細(xì)介紹，可參考：http://zhaox.github.io/algorithm/2015/06/29/hash）

至此，我們看完了Java 7中HashMap和HashTable中對(duì)于hash的實(shí)現(xiàn)，我們來(lái)做個(gè)簡(jiǎn)單的總結(jié)。

• HashMap默認(rèn)的初始化大小為16，之后每次擴(kuò)充為原來(lái)的2倍。
• HashTable默認(rèn)的初始大小為11，之后每次擴(kuò)充為原來(lái)的2n+1。
• 當(dāng)哈希表的大小為素?cái)?shù)時(shí)，簡(jiǎn)單的取模哈希的結(jié)果會(huì)更加均勻，所以單從這一點(diǎn)上看，HashTable的哈希表大小選擇，似乎更高明些。因?yàn)閔ash結(jié)果越分散效果越好。
• 在取模計(jì)算時(shí)，如果模數(shù)是2的冪，那么我們可以直接使用位運(yùn)算來(lái)得到結(jié)果，效率要大大高于做除法。所以從hash計(jì)算的效率上，又是HashMap更勝一籌。
• 但是，HashMap為了提高效率使用位運(yùn)算代替哈希，這又引入了哈希分布不均勻的問(wèn)題，所以HashMap為解決這問(wèn)題，又對(duì)hash算法做了一些改進(jìn)，進(jìn)行了擾動(dòng)計(jì)算。

ConcurrentHashMap In Java 7

private int hash(Object k) {int h = hashSeed;if ((0 != h) && (k instanceof String)) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// Spread bits to regularize both segment and index locations,// using variant of single-word Wang/Jenkins hash.h += (h << 15) ^ 0xffffcd7d;h ^= (h >>> 10);h += (h << 3);h ^= (h >>> 6);h += (h << 2) + (h << 14);return h ^ (h >>> 16); }int j = (hash >>> segmentShift) & segmentMask;

上面這段關(guān)于ConcurrentHashMap的hash實(shí)現(xiàn)其實(shí)和HashMap如出一轍。都是通過(guò)位運(yùn)算代替取模，然后再對(duì)hashcode進(jìn)行擾動(dòng)。區(qū)別在于，ConcurrentHashMap 使用了一種變種的Wang/Jenkins 哈希算法，其主要母的也是為了把高位和低位組合在一起，避免發(fā)生沖突。至于為啥不和HashMap采用同樣的算法進(jìn)行擾動(dòng)，我猜這只是程序員自由意志的選擇吧。至少我目前沒(méi)有辦法證明哪個(gè)更優(yōu)。

HashMap In Java 8

在Java 8 之前，HashMap和其他基于map的類(lèi)都是通過(guò)鏈地址法解決沖突，它們使用單向鏈表來(lái)存儲(chǔ)相同索引值的元素。在最壞的情況下，這種方式會(huì)將HashMap的get方法的性能從O(1)降低到O(n)。為了解決在頻繁沖突時(shí)hashmap性能降低的問(wèn)題，Java 8中使用平衡樹(shù)來(lái)替代鏈表存儲(chǔ)沖突的元素。這意味著我們可以將最壞情況下的性能從O(n)提高到O(logn)。關(guān)于HashMap在Java 8中的優(yōu)化，我后面會(huì)有文章繼續(xù)深入介紹。

如果惡意程序知道我們用的是Hash算法，則在純鏈表情況下，它能夠發(fā)送大量請(qǐng)求導(dǎo)致哈希碰撞，然后不停訪問(wèn)這些key導(dǎo)致HashMap忙于進(jìn)行線性查找，最終陷入癱瘓，即形成了拒絕服務(wù)攻擊（DoS）。

關(guān)于Java 8中的hash函數(shù)，原理和Java 7中基本類(lèi)似。Java 8中這一步做了優(yōu)化，只做一次16位右位移異或混合，而不是四次，但原理是不變的。

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

在JDK1.8的實(shí)現(xiàn)中，優(yōu)化了高位運(yùn)算的算法，通過(guò)hashCode()的高16位異或低16位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質(zhì)量來(lái)考慮的。以上方法得到的int的hash值，然后再通過(guò)h & (table.length -1)來(lái)得到該對(duì)象在數(shù)據(jù)中保存的位置。

HashTable In Java 8

在Java 8的HashTable中，已經(jīng)不在有hash方法了。但是哈希的操作還是在的，比如在put方法中就有如下實(shí)現(xiàn)：

int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;

這其實(shí)和Java 7中的實(shí)現(xiàn)幾乎無(wú)差別，就不做過(guò)多的介紹了。

ConcurrentHashMap In Java 8

Java 8 里面的求hash的方法從hash改為了spread。實(shí)現(xiàn)方式如下：

static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS; }

Java 8的ConcurrentHashMap同樣是通過(guò)Key的哈希值與數(shù)組長(zhǎng)度取模確定該Key在數(shù)組中的索引。同樣為了避免不太好的Key的hashCode設(shè)計(jì)，它通過(guò)如下方法計(jì)算得到Key的最終哈希值。不同的是，Java 8的ConcurrentHashMap作者認(rèn)為引入紅黑樹(shù)后，即使哈希沖突比較嚴(yán)重，尋址效率也足夠高，所以作者并未在哈希值的計(jì)算上做過(guò)多設(shè)計(jì)，只是將Key的hashCode值與其高16位作異或并保證最高位為0（從而保證最終結(jié)果為正整數(shù)）。

總結(jié)

至此，我們已經(jīng)分析完了HashMap、HashTable以及ConcurrentHashMap分別在Jdk 1.7 和 Jdk 1.8中的實(shí)現(xiàn)。我們可以發(fā)現(xiàn)，為了保證哈希的結(jié)果可以分散、為了提高哈希的效率，JDK在一個(gè)小小的hash方法上就有很多考慮，做了很多事情。當(dāng)然，我希望我們不僅可以深入了解背后的原理，還要學(xué)會(huì)這種對(duì)代碼精益求精的態(tài)度。

總結(jié)

以上是生活随笔為你收集整理的Java中hash算法细述的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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