1. 背景

某天，我在寫(xiě)代碼的時(shí)候，無(wú)意中點(diǎn)開(kāi)了 String hashCode 方法。然后大致看了一下 hashCode 的實(shí)現(xiàn)，發(fā)現(xiàn)并不是很復(fù)雜。但是我從源碼中發(fā)現(xiàn)了一個(gè)奇怪的數(shù)字，也就是本文的主角31。這個(gè)數(shù)字居然不是用常量聲明的，所以沒(méi)法從字面意思上推斷這個(gè)數(shù)字的用途。后來(lái)帶著疑問(wèn)和好奇心，到網(wǎng)上去找資料查詢一下。在看完資料后，默默的感嘆了一句，原來(lái)是這樣啊。那么到底是哪樣呢？在接下來(lái)章節(jié)里，請(qǐng)大家?guī)е闷嫘暮臀医议_(kāi)數(shù)字31的用途之謎。

2. 選擇數(shù)字31的原因

在詳細(xì)說(shuō)明 String hashCode 方法選擇數(shù)字31的作為乘子的原因之前，我們先來(lái)看看 String hashCode 方法是怎樣實(shí)現(xiàn)的，如下：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

上面的代碼就是 String hashCode 方法的實(shí)現(xiàn)，是不是很簡(jiǎn)單。實(shí)際上 hashCode 方法核心的計(jì)算邏輯只有三行，也就是代碼中的 for 循環(huán)。我們可以由上面的 for 循環(huán)推導(dǎo)出一個(gè)計(jì)算公式，hashCode 方法注釋中已經(jīng)給出。如下：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

這里說(shuō)明一下，上面的 s 數(shù)組即源碼中的 val 數(shù)組，是 String 內(nèi)部維護(hù)的一個(gè) char 類型數(shù)組。這里我來(lái)簡(jiǎn)單推導(dǎo)一下這個(gè)公式：

假設(shè) n=3
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
       h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
       h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]

上面的公式包括公式的推導(dǎo)并不是本文的重點(diǎn)，大家了解了解即可。接下來(lái)來(lái)說(shuō)說(shuō)本文的重點(diǎn)，即選擇31的理由。從網(wǎng)上的資料來(lái)看，一般有如下兩個(gè)原因：

第一，31是一個(gè)不大不小的質(zhì)數(shù)，是作為 hashCode 乘子的優(yōu)選質(zhì)數(shù)之一。另外一些相近的質(zhì)數(shù)，比如37、41、43等等，也都是不錯(cuò)的選擇。那么為啥偏偏選中了31呢？請(qǐng)看第二個(gè)原因。

第二、31可以被 JVM 優(yōu)化，31 * i = (i << 5) - i。

上面兩個(gè)原因中，第一個(gè)需要解釋一下，第二個(gè)比較簡(jiǎn)單，就不說(shuō)了。下面我來(lái)解釋第一個(gè)理由。一般在設(shè)計(jì)哈希算法時(shí)，會(huì)選擇一個(gè)特殊的質(zhì)數(shù)。至于為啥選擇質(zhì)數(shù)，我想應(yīng)該是可以降低哈希算法的沖突率。至于原因，這個(gè)就要問(wèn)數(shù)學(xué)家了，我?guī)缀蹩梢院雎缘臄?shù)學(xué)水平解釋不了這個(gè)原因。上面說(shuō)到，31是一個(gè)不大不小的質(zhì)數(shù)，是優(yōu)選乘子。那為啥同是質(zhì)數(shù)的2和101（或者更大的質(zhì)數(shù)）就不是優(yōu)選乘子呢，分析如下。

這里先分析質(zhì)數(shù)2。首先，假設(shè) n = 6，然后把質(zhì)數(shù)2和 n 帶入上面的計(jì)算公式。并僅計(jì)算公式中次數(shù)最高的那一項(xiàng)，結(jié)果是2^5 = 32，是不是很小。所以這里可以斷定，當(dāng)字符串長(zhǎng)度不是很長(zhǎng)時(shí)，用質(zhì)數(shù)2做為乘子算出的哈希值，數(shù)值不會(huì)很大。也就是說(shuō)，哈希值會(huì)分布在一個(gè)較小的數(shù)值區(qū)間內(nèi)，分布性不佳，最終可能會(huì)導(dǎo)致沖突率上升。

上面說(shuō)了，質(zhì)數(shù)2做為乘子會(huì)導(dǎo)致哈希值分布在一個(gè)較小區(qū)間內(nèi)，那么如果用一個(gè)較大的大質(zhì)數(shù)101會(huì)產(chǎn)生什么樣的結(jié)果呢？根據(jù)上面的分析，我想大家應(yīng)該可以猜出結(jié)果了。就是不用再擔(dān)心哈希值會(huì)分布在一個(gè)小的區(qū)間內(nèi)了，因?yàn)?code>101^5 = 10,510,100,501。但是要注意的是，這個(gè)計(jì)算結(jié)果太大了。如果用 int 類型表示哈希值，結(jié)果會(huì)溢出，最終導(dǎo)致數(shù)值信息丟失。盡管數(shù)值信息丟失并不一定會(huì)導(dǎo)致沖突率上升，但是我們暫且先認(rèn)為質(zhì)數(shù)101（或者更大的質(zhì)數(shù)）也不是很好的選擇。最后，我們?cè)賮?lái)看看質(zhì)數(shù)31的計(jì)算結(jié)果： 31^5 = 28629151，結(jié)果值相對(duì)于32和10,510,100,501來(lái)說(shuō)。是不是很nice，不大不小。

上面用了比較簡(jiǎn)陋的數(shù)學(xué)手段證明了數(shù)字31是一個(gè)不大不小的質(zhì)數(shù)，是作為 hashCode 乘子的優(yōu)選質(zhì)數(shù)之一。接下來(lái)我會(huì)用詳細(xì)的實(shí)驗(yàn)來(lái)驗(yàn)證上面的結(jié)論，不過(guò)在驗(yàn)證前，我們先看看 Stack Overflow 上關(guān)于這個(gè)問(wèn)題的討論，Why does Java's hashCode() in String use 31 as a multiplier?。其中排名第一的答案引用了《Effective Java》中的一段話，這里也引用一下：

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: `31 * i == (i << 5) - i``. Modern VMs do this sort of optimization automatically.

簡(jiǎn)單翻譯一下：

選擇數(shù)字31是因?yàn)樗且粋€(gè)奇質(zhì)數(shù)，如果選擇一個(gè)偶數(shù)會(huì)在乘法運(yùn)算中產(chǎn)生溢出，導(dǎo)致數(shù)值信息丟失，因?yàn)槌硕喈?dāng)于移位運(yùn)算。選擇質(zhì)數(shù)的優(yōu)勢(shì)并不是特別的明顯，但這是一個(gè)傳統(tǒng)。同時(shí)，數(shù)字31有一個(gè)很好的特性，即乘法運(yùn)算可以被移位和減法運(yùn)算取代，來(lái)獲取更好的性能：31 * i == (i << 5) - i，現(xiàn)代的 Java 虛擬機(jī)可以自動(dòng)的完成這個(gè)優(yōu)化。

排名第二的答案設(shè)這樣說(shuō)的：

As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.

這段話也翻譯一下：

正如 Goodrich 和 Tamassia 指出的那樣，如果你對(duì)超過(guò) 50,000 個(gè)英文單詞（由兩個(gè)不同版本的 Unix 字典合并而成）進(jìn)行 hash code 運(yùn)算，并使用常數(shù) 31, 33, 37, 39 和 41 作為乘子，每個(gè)常數(shù)算出的哈希值沖突數(shù)都小于7個(gè)，所以在上面幾個(gè)常數(shù)中，常數(shù) 31 被 Java 實(shí)現(xiàn)所選用也就不足為奇了。

上面的兩個(gè)答案完美的解釋了 Java 源碼中選用數(shù)字 31 的原因。接下來(lái)，我將針對(duì)第二個(gè)答案就行驗(yàn)證，請(qǐng)大家繼續(xù)往下看。

3. 實(shí)驗(yàn)及數(shù)據(jù)可視化

本節(jié)，我將使用不同的數(shù)字作為乘子，對(duì)超過(guò)23萬(wàn)個(gè)英文單詞進(jìn)行哈希運(yùn)算，并計(jì)算哈希算法的沖突率。同時(shí)，我也將針對(duì)不同乘子算出的哈希值分布情況進(jìn)行可視化處理，讓大家可以直觀的看到數(shù)據(jù)分布情況。本次實(shí)驗(yàn)所使用的數(shù)據(jù)是 Unix/Linux 平臺(tái)中的英文字典文件，文件路徑為 /usr/share/dict/words。

3.1 哈希值沖突率計(jì)算

計(jì)算哈希算法沖突率并不難，比如可以一次性將所有單詞的 hash code 算出，并放入 Set 中去除重復(fù)值。之后拿單詞數(shù)減去 set.size() 即可得出沖突數(shù)，有了沖突數(shù)，沖突率就可以算出來(lái)了。當(dāng)然，如果使用 JDK8 提供的流式計(jì)算 API，則可更方便算出，代碼片段如下：

public static Integer hashCode(String str, Integer multiplier) {
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = multiplier * hash + str.charAt(i);
    }

    return hash;
}
    
/**
 * 計(jì)算 hash code 沖突率，順便分析一下 hash code 最大值和最小值，并輸出
 * @param multiplier
 * @param hashs
 */
public static void calculateConflictRate(Integer multiplier, List<Integer> hashs) {
    Comparator<Integer> cp = (x, y) -> x > y ? 1 : (x < y ? -1 : 0);
    int maxHash = hashs.stream().max(cp).get();
    int minHash = hashs.stream().min(cp).get();

    // 計(jì)算沖突數(shù)及沖突率
    int uniqueHashNum = (int) hashs.stream().distinct().count();
    int conflictNum = hashs.size() - uniqueHashNum;
    double conflictRate = (conflictNum * 1.0) / hashs.size();

    System.out.println(String.format("multiplier=%4d, minHash=%11d, maxHash=%10d, conflictNum=%6d, conflictRate=%.4f%%",
                multiplier, minHash, maxHash, conflictNum, conflictRate * 100));
}

結(jié)果如下：

從上圖可以看出，使用較小的質(zhì)數(shù)做為乘子時(shí)，沖突率會(huì)很高。尤其是質(zhì)數(shù)2，沖突率達(dá)到了 55.14%。同時(shí)我們注意觀察質(zhì)數(shù)2作為乘子時(shí)，哈希值的分布情況。可以看得出來(lái)，哈希值分布并不是很廣，僅僅分布在了整個(gè)哈希空間的正半軸部分，即 0 ~ 2³¹-1。而負(fù)半軸 -2³¹ ~ -1，則無(wú)分布。這也證明了我們上面斷言，即質(zhì)數(shù)2作為乘子時(shí)，對(duì)于短字符串，生成的哈希值分布性不佳。然后再來(lái)看看我們之前所說(shuō)的 31、37、41 這三個(gè)不大不小的質(zhì)數(shù)，表現(xiàn)都不錯(cuò)，沖突數(shù)都低于7個(gè)。而質(zhì)數(shù) 101 和 199 表現(xiàn)的也很不錯(cuò)，沖突率很低，這也說(shuō)明哈希值溢出并不一定會(huì)導(dǎo)致沖突率上升。但是這兩個(gè)家伙一言不合就溢出，我們認(rèn)為他們不是哈希算法的優(yōu)選乘子。最后我們?cè)賮?lái)看看 32 和 36 這兩個(gè)偶數(shù)的表現(xiàn)，結(jié)果并不好，尤其是 32，沖突率超過(guò)了了50%。盡管 36 表現(xiàn)的要好一點(diǎn)，不過(guò)和 31，37相比，沖突率還是比較高的。當(dāng)然并非所有的偶數(shù)作為乘子時(shí)，沖突率都會(huì)比較高，大家有興趣可以自己驗(yàn)證。

3.2 哈希值分布可視化

上一節(jié)分析了不同數(shù)字作為乘子時(shí)的沖突率情況，這一節(jié)來(lái)分析一下不同數(shù)字作為乘子時(shí)，哈希值的分布情況。在詳細(xì)分析之前，我先說(shuō)說(shuō)哈希值可視化的過(guò)程。我原本是打算將所有的哈希值用一維散點(diǎn)圖進(jìn)行可視化，但是后來(lái)找了一圈，也沒(méi)找到合適的畫(huà)圖工具。加之后來(lái)想了想，一維散點(diǎn)圖可能不合適做哈希值可視化，因?yàn)檫@里有超過(guò)23萬(wàn)個(gè)哈希值。也就意味著會(huì)在圖上顯示超過(guò)23萬(wàn)個(gè)散點(diǎn)，如果不出意外的話，這23萬(wàn)個(gè)散點(diǎn)會(huì)聚集的很密，有可能會(huì)變成一個(gè)大黑塊，就失去了可視化的意義了。所以這里選擇了另一種可視化效果更好的圖表，也就是 excel 中的平滑曲線的二維散點(diǎn)圖（下面簡(jiǎn)稱散點(diǎn)曲線圖）。當(dāng)然這里同樣沒(méi)有把23萬(wàn)散點(diǎn)都顯示在圖表上，太多了。所以在實(shí)際繪圖過(guò)程中，我將哈希空間等分成了64個(gè)子區(qū)間，并統(tǒng)計(jì)每個(gè)區(qū)間內(nèi)的哈希值數(shù)量。最后將分區(qū)編號(hào)做為X軸，哈希值數(shù)量為Y軸，就繪制出了我想要的二維散點(diǎn)曲線圖了。這里舉個(gè)例子說(shuō)明一下吧，以第0分區(qū)為例。第0分區(qū)數(shù)值區(qū)間是[-2147483648, -2080374784)，我們統(tǒng)計(jì)落在該數(shù)值區(qū)間內(nèi)哈希值的數(shù)量，得到 <分區(qū)編號(hào), 哈希值數(shù)量> 數(shù)值對(duì)，這樣就可以繪圖了。分區(qū)代碼如下：

 /**
 * 將整個(gè)哈希空間等分成64份，統(tǒng)計(jì)每個(gè)空間內(nèi)的哈希值數(shù)量
 * @param hashs
 */
public static Map<Integer, Integer> partition(List<Integer> hashs) {
    // step = 2^32 / 64 = 2^26
    final int step = 67108864;
    List<Integer> nums = new ArrayList<>();
    Map<Integer, Integer> statistics = new LinkedHashMap<>();
    int start = 0;
    for (long i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i += step) {
        final long min = i;
        final long max = min + step;
        int num = (int) hashs.parallelStream()
                .filter(x -> x >= min && x < max).count();

        statistics.put(start++, num);
        nums.add(num);
    }

    // 為了防止計(jì)算出錯(cuò)，這里驗(yàn)證一下
    int hashNum = nums.stream().reduce((x, y) -> x + y).get();
    assert hashNum == hashs.size();

    return statistics;
}

本文中的哈希值是用整形表示的，整形的數(shù)值區(qū)間是 [-2147483648, 2147483647]，區(qū)間大小為 2^32。所以這里可以將區(qū)間等分成64個(gè)子區(qū)間，每個(gè)自子區(qū)間大小為 2^26。詳細(xì)的分區(qū)對(duì)照表如下：

接下來(lái)，讓我們對(duì)照上面的分區(qū)表，對(duì)數(shù)字2、3、17、31、101的散點(diǎn)曲線圖進(jìn)行簡(jiǎn)單的分析。先從數(shù)字2開(kāi)始，數(shù)字2對(duì)于的散點(diǎn)曲線圖如下：

上面的圖還是很一幕了然的，乘子2算出的哈希值幾乎全部落在第32分區(qū)，也就是 [0, 67108864)數(shù)值區(qū)間內(nèi)，落在其他區(qū)間內(nèi)的哈希值數(shù)量幾乎可以忽略不計(jì)。這也就不難解釋為什么數(shù)字2作為乘子時(shí)，算出哈希值的沖突率如此之高的原因了。所以這樣的哈希算法要它有何用啊，拖出去斬了吧。接下來(lái)看看數(shù)字3作為乘子時(shí)的表現(xiàn)：

3作為乘子時(shí)，算出的哈希值分布情況和2很像，只不過(guò)稍微好了那么一點(diǎn)點(diǎn)。從圖中可以看出絕大部分的哈希值最終都落在了第32分區(qū)里，哈希值的分布性很差。這個(gè)也沒(méi)啥用，拖出去槍斃5分鐘吧。在看看數(shù)字17的情況怎么樣：

數(shù)字17作為乘子時(shí)的表現(xiàn)，明顯比上面兩個(gè)數(shù)字好點(diǎn)了。雖然哈希值在第32分區(qū)和第34分區(qū)有一定的聚集，但是相比較上面2和3，情況明顯好好了很多。除此之外，17作為乘子算出的哈希值在其他區(qū)也均有分布，且較為均勻，還算是一個(gè)不錯(cuò)的乘子吧。

接下來(lái)來(lái)看看我們本文的主角31了，31作為乘子算出的哈希值在第33分區(qū)有一定的小聚集。不過(guò)相比于數(shù)字17，主角31的表現(xiàn)又好了一些。首先是哈希值的聚集程度沒(méi)有17那么嚴(yán)重，其次哈希值在其他區(qū)分布的情況也要好于17。總之，選31，準(zhǔn)沒(méi)錯(cuò)啊。

最后再來(lái)看看大質(zhì)數(shù)101的表現(xiàn)，不難看出，質(zhì)數(shù)101作為乘子時(shí)，算出的哈希值分布情況要好于主角31，有點(diǎn)喧賓奪主的意思。不過(guò)不可否認(rèn)的是，質(zhì)數(shù)101的作為乘子時(shí)，哈希值的分布性確實(shí)更加均勻。所以如果不在意質(zhì)數(shù)101容易導(dǎo)致數(shù)據(jù)信息丟失問(wèn)題，或許其是一個(gè)更好的選擇。

4.寫(xiě)在最后

經(jīng)過(guò)上面的分析與實(shí)踐，我想大家應(yīng)該明白了 String hashCode 方法中選擇使用數(shù)字31作為乘子的原因了。本文本質(zhì)是一篇簡(jiǎn)單的科普文而已，并沒(méi)有銀彈。如果大家讀完后覺(jué)得又漲知識(shí)了，那這篇文章的目的就達(dá)到了。最后，本篇文章的配圖畫(huà)的還是很辛苦的，所以如果大家覺(jué)得文章不錯(cuò)，不妨就給個(gè)贊吧，就當(dāng)是對(duì)我的鼓勵(lì)了。另外，如果文章中有不妥或者錯(cuò)誤的地方，也歡迎指出來(lái)。如果能不吝賜教，那就更好了。最后祝大家生活愉快，再見(jiàn)。

本文在知識(shí)共享許可協(xié)議 4.0 下發(fā)布，轉(zhuǎn)載需在明顯位置處注明出處
作者：田小波
本文同步發(fā)布在我的個(gè)人博客：http://www.tianxiaobo.com

本作品采用知識(shí)共享署名-非商業(yè)性使用-禁止演繹 4.0 國(guó)際許可協(xié)議進(jìn)行許可。