哈希函數(shù)的本質(zhì)及生成方式課件

課時(shí)1哈希函數(shù)的本質(zhì)及生成方式1 哈希表與哈希函數(shù)2 hashCode

函數(shù)中的“魔數(shù)"(MagicNumber)3 區(qū)塊鏈挖礦的本質(zhì)課時(shí) 05互聯(lián)網(wǎng)人實(shí)戰(zhàn)大學(xué)哈希表與哈希函數(shù)哈希表本質(zhì)上是一個(gè)數(shù)組，要訪問(wèn)一個(gè)數(shù)組中某個(gè)特定的元素，那么需要知道這個(gè)元素的索引哈希函數(shù)的定義是將任意長(zhǎng)度的一個(gè)對(duì)象映射到一個(gè)固定長(zhǎng)度的值上而這個(gè)值可以稱作是哈希值(Hash

Value)哈希表與哈希函數(shù)2

兩個(gè)相同的對(duì)象作為哈希函數(shù)的輸入，它們總會(huì)得到一樣的哈希值3

兩個(gè)不同的對(duì)象作為哈希函數(shù)的輸入，它們不一定會(huì)得到不同的哈希值1

任何對(duì)象作為哈希函數(shù)的輸入都可以得到一個(gè)相應(yīng)的哈希值哈希表與哈希函數(shù)按照

Java

String

類里的哈希函數(shù)公式來(lái)計(jì)算出不同字符串的哈希值下面所有字符的數(shù)值都是按照

ASCII

表獲得，具體的數(shù)值可以在https://www

ascii-code

com/當(dāng)輸入“ABC"字符串時(shí)，其哈希值為：哈希表與哈希函數(shù)計(jì)算字符串

"Aa"

和

"BB"

的哈希值"Aa"='A'*31+'a'=65*31+

97

=2112"BB"='B'*31+'B'=66*31+

66

=2112可以看到不同的兩個(gè)字符串其實(shí)是會(huì)輸出相同的哈希值出來(lái)的這時(shí)候就會(huì)造成哈希碰撞哈希表與哈希函數(shù)在計(jì)算機(jī)里一個(gè)

32

位

int

類型的整數(shù)里最高位如果是

0

則表示這個(gè)數(shù)是非負(fù)數(shù)，如果是

1

則表示是負(fù)數(shù)如果當(dāng)字符串通過(guò)計(jì)算算出的哈希值大千

2

的

32

次方減

1

時(shí)，也就是大千

32

位整數(shù)所能表達(dá)的最大正整數(shù)了，則會(huì)造成溢出，此時(shí)哈希值就變?yōu)樨?fù)數(shù)了hashCode 函數(shù)中的“魔數(shù)"(Magic Number)Java

String

類里的

hashCode

函數(shù)，一直在使用一個(gè)

31

這樣的正整數(shù)來(lái)進(jìn)行計(jì)算，這是為什么呢？Java

Openjdk-jdk11中

Stringjava的源碼：publicinthashCode()

{inth=

hash;if(h==0&&value

length>0)

{hash=h=islatin1()?Stringlatin1

hashCode(value):StringUTF16

hashCode(value);ireturn

h;ihashCode 函數(shù)中的“魔數(shù)"(Magic Number)Stringlatin1

類中的

hashCode

函數(shù)：publicstatic

int

hashCode(byte[]value)

{inth=

0;for(bytev:value){h=31*h+(v

&0xff);ireturn

h;ihashCode 函數(shù)中的“魔數(shù)"(Magic Number)StringUTF16類中的hashCode函數(shù)如下面所示：publicstaticinthashCode(byte[]

value){inth=

0;intlength=value

length>>1;for(inti=0;i<length;i++)

{h=31*h+getChar(value,

i);ireturn

h;ihashCode 函數(shù)中的“魔數(shù)"(Magic Number)Java

String類里的hashCode函數(shù)，一直在使用一個(gè)

31，為什么？Goodrich

和

Tamassia

兩位計(jì)算機(jī)科學(xué)家對(duì)超過(guò)

50000

個(gè)英文單詞進(jìn)行了哈希值運(yùn)算，使用常數(shù)31、33、37、39

和

41

作為乘數(shù)因子，每個(gè)常數(shù)算出的哈希值碰撞的次數(shù)都小千

7

個(gè)數(shù)學(xué)的角度，選擇一個(gè)質(zhì)數(shù)作為乘數(shù)因子可以讓哈希碰撞減少其次，上面那兩個(gè)

hashCode

源碼，都各有一條

31

*

h

的語(yǔ)句，可被自動(dòng)優(yōu)化成“(h

<<

5)

-

h"這樣一條位運(yùn)算加上一個(gè)減法指令，而不必執(zhí)行乘法指令，可大大提高運(yùn)算哈希函數(shù)的效率區(qū)塊鏈挖礦的本質(zhì)如果已知一個(gè)哈希值，即便給出了哈希函數(shù)的公式也很難算出原來(lái)的輸入到底是什么?根據(jù)這個(gè)公式，已知哈希值是

123456789，那輸入的字符串是什么呢？只能采用暴力破解法，也就是一個(gè)一個(gè)的字符串去嘗試，直到嘗試出這個(gè)哈希值為止區(qū)塊鏈挖礦的本質(zhì)對(duì)千區(qū)塊鏈挖礦來(lái)說(shuō)，這個(gè)“礦"其實(shí)就是一個(gè)字符串“礦工"，也就是進(jìn)行運(yùn)算的計(jì)算機(jī)，必須在規(guī)定的時(shí)間內(nèi)找到一個(gè)字符串，使得在進(jìn)行了哈希函數(shù)運(yùn)算之后得到一個(gè)滿足要求的值區(qū)塊鏈挖礦的本質(zhì)以比特幣為例，它采用了

SHA256

的哈希函數(shù)來(lái)進(jìn)行運(yùn)算，無(wú)論輸入的是什么，SHA256

哈希