這篇文章主要講解了“HashCode使用31作為乘數(shù)的原因是什么”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“HashCode使用31作為乘數(shù)的原因是什么”吧！
創(chuàng)新互聯(lián)公司是一家專業(yè)提供措美企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、成都網(wǎng)站建設(shè)、H5場(chǎng)景定制、小程序制作等業(yè)務(wù)。10年已為措美眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)絡(luò)公司優(yōu)惠進(jìn)行中。
重慶分公司
重慶分公司
// 獲取hashCode "abc".hashCode();
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;
} 在獲取hashCode的源碼中可以看到，有一個(gè)固定值31，在for循環(huán)每次執(zhí)行時(shí)進(jìn)行乘積計(jì)算，循環(huán)后的公式如下；s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
「那么這里為什么選擇31作為乘積值呢？」
在stackoverflow關(guān)于為什么選擇31作為固定乘積值，有一篇討論文章，Why does Java's hashCode() in String use 31 as a multiplier? 這是一個(gè)時(shí)間比較久的問(wèn)題了，摘取兩個(gè)回答點(diǎn)贊最多的；
「413個(gè)贊????的回答」
最多的這個(gè)回答是來(lái)自《Effective Java》的內(nèi)容；
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.
這段內(nèi)容主要闡述的觀點(diǎn)包括；
31 * i == (i << 5) - i。這主要是說(shuō)乘積運(yùn)算可以使用位移提升性能，同時(shí)目前的JVM虛擬機(jī)也會(huì)自動(dòng)支持此類(lèi)的優(yōu)化。「80個(gè)贊????的回答」
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.
接下來(lái)要做的事情并不難，只是根據(jù)stackoverflow的回答，統(tǒng)計(jì)出不同的乘積數(shù)對(duì)10萬(wàn)個(gè)單詞的hash計(jì)算結(jié)果。10個(gè)單詞表已提供，可以通過(guò)關(guān)注公眾號(hào)：bugstack蟲(chóng)洞棧進(jìn)行下載
1 a "n.(A)As 或 A's 安(ampere(a) art.一;n.字母A /[軍] Analog.Digital,模擬/數(shù)字 /(=account of) 帳上"
2 aaal American Academy of Arts and Letters 美國(guó)藝術(shù)和文學(xué)學(xué)會(huì)
3 aachen 亞琛[德意志聯(lián)邦共和國(guó)西部城市]
4 aacs Airways and Air Communications Service (美國(guó))航路與航空通訊聯(lián)絡(luò)處
5 aah " [軍]Armored Artillery Howitzer,裝甲榴彈炮;[軍]Advanced Attack Helicopter,先進(jìn)攻擊直升機(jī)"
6 aal "ATM Adaptation Layer,ATM適應(yīng)層"
7 aapamoor "n.[生]丘澤,高低位鑲嵌沼澤" 資源下載進(jìn)行獲取 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ì)算碰撞很簡(jiǎn)單，也就是計(jì)算那些出現(xiàn)相同哈希值的數(shù)量，計(jì)算出碰撞總量即可。這里的實(shí)現(xiàn)方式有很多，可以使用set、map也可以使用java8的stream流統(tǒng)計(jì)distinct。
private static RateInfo hashCollisionRate(Integer multiplier, List hashCodeList) {
int maxHash = hashCodeList.stream().max(Integer::compareTo).get();
int minHash = hashCodeList.stream().min(Integer::compareTo).get();
int collisionCount = (int) (hashCodeList.size() - hashCodeList.stream().distinct().count());
double collisionRate = (collisionCount * 1.0) / hashCodeList.size();
return new RateInfo(maxHash, minHash, multiplier, collisionCount, collisionRate);
}
@Before
public void before() {
"abc".hashCode();
// 讀取文件，103976個(gè)英語(yǔ)單詞庫(kù).txt
words = FileUtil.readWordList("E:/itstack/git/github.com/interview/interview-01/103976個(gè)英語(yǔ)單詞庫(kù).txt");
}
@Test
public void test_collisionRate() {
List rateInfoList = HashCode.collisionRateList(words, 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199);
for (RateInfo rate : rateInfoList) {
System.out.println(String.format("乘數(shù) = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞數(shù)量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
}
} 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199，最終返回一個(gè)list結(jié)果并輸出。「測(cè)試結(jié)果」
單詞數(shù)量：103976
乘數(shù) = 2, 最小Hash = 97, 最大Hash = 1842581979, 碰撞數(shù)量 = 60382, 碰撞概率 = 58.0730%
乘數(shù) = 3, 最小Hash = -2147308825, 最大Hash = 2146995420, 碰撞數(shù)量 = 24300, 碰撞概率 = 23.3708%
乘數(shù) = 5, 最小Hash = -2147091606, 最大Hash = 2147227581, 碰撞數(shù)量 = 7994, 碰撞概率 = 7.6883%
乘數(shù) = 7, 最小Hash = -2147431389, 最大Hash = 2147226363, 碰撞數(shù)量 = 3826, 碰撞概率 = 3.6797%
乘數(shù) = 17, 最小Hash = -2147238638, 最大Hash = 2147101452, 碰撞數(shù)量 = 576, 碰撞概率 = 0.5540%
乘數(shù) = 31, 最小Hash = -2147461248, 最大Hash = 2147444544, 碰撞數(shù)量 = 2, 碰撞概率 = 0.0019%
乘數(shù) = 32, 最小Hash = -2007883634, 最大Hash = 2074238226, 碰撞數(shù)量 = 34947, 碰撞概率 = 33.6106%
乘數(shù) = 33, 最小Hash = -2147469046, 最大Hash = 2147378587, 碰撞數(shù)量 = 1, 碰撞概率 = 0.0010%
乘數(shù) = 39, 最小Hash = -2147463635, 最大Hash = 2147443239, 碰撞數(shù)量 = 0, 碰撞概率 = 0.0000%
乘數(shù) = 41, 最小Hash = -2147423916, 最大Hash = 2147441721, 碰撞數(shù)量 = 1, 碰撞概率 = 0.0010%
乘數(shù) = 199, 最小Hash = -2147459902, 最大Hash = 2147480320, 碰撞數(shù)量 = 0, 碰撞概率 = 0.0000%
Process finished with exit code 0
以上就是不同的乘數(shù)下的hash碰撞結(jié)果圖標(biāo)展示，從這里可以看出如下信息；
除了以上看到哈希值在不同乘數(shù)的一個(gè)碰撞概率后，關(guān)于散列表也就是hash，還有一個(gè)非常重要的點(diǎn)，那就是要盡可能的讓數(shù)據(jù)散列分布。只有這樣才能減少hash碰撞次數(shù)，也就是后面章節(jié)要講到的hashMap源碼。
那么怎么看散列分布呢？如果我們能把10萬(wàn)個(gè)hash值鋪到圖表上，形成的一張圖，就可以看出整個(gè)散列分布。但是這樣的圖會(huì)比較大，當(dāng)我們縮小看后，就成一個(gè)了大黑點(diǎn)。所以這里我們采取分段統(tǒng)計(jì)，把2 ^ 32方分64個(gè)格子進(jìn)行存放，每個(gè)格子都會(huì)有對(duì)應(yīng)的數(shù)量的hash值，最終把這些數(shù)據(jù)展示在圖表上。
public static Map hashArea(List hashCodeList) {
Map statistics = new LinkedHashMap<>();
int start = 0;
for (long i = 0x80000000; i <= 0x7fffffff; i += 67108864) {
long min = i;
long max = min + 67108864;
// 篩選出每個(gè)格子里的哈希值數(shù)量，java8流統(tǒng)計(jì)；https://bugstack.cn/itstack-demo-any/2019/12/10/%E6%9C%89%E7%82%B9%E5%B9%B2%E8%B4%A7-Jdk1.8%E6%96%B0%E7%89%B9%E6%80%A7%E5%AE%9E%E6%88%98%E7%AF%87(41%E4%B8%AA%E6%A1%88%E4%BE%8B).html
int num = (int) hashCodeList.parallelStream().filter(x -> x >= min && x < max).count();
statistics.put(start++, num);
}
return statistics; int取值范圍內(nèi)，每個(gè)哈希值存放到不同格子里的數(shù)量。@Test
public void test_hashArea() {
System.out.println(HashCode.hashArea(words, 2).values());
System.out.println(HashCode.hashArea(words, 7).values());
System.out.println(HashCode.hashArea(words, 31).values());
System.out.println(HashCode.hashArea(words, 32).values());
System.out.println(HashCode.hashArea(words, 199).values());
} 「統(tǒng)計(jì)圖表」
感謝各位的閱讀，以上就是“HashCode使用31作為乘數(shù)的原因是什么”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)HashCode使用31作為乘數(shù)的原因是什么這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
