「The Algorithm Design Manual」一書(shū)中提到，雅虎的 Chief Scientist ，Udi Manber 曾說(shuō)過(guò):

在 yahoo 所應(yīng)用的算法中，最重要的三個(gè)是：Hash，Hash 和 Hash。

例如：git用sha1判斷文件更改，密碼用MD5生成摘要后加鹽等等對(duì)Hash的應(yīng)用可看出，Hash的在計(jì)算機(jī)世界扮演著多么重要的角色。無(wú)論是密碼學(xué)、數(shù)據(jù)結(jié)構(gòu)、現(xiàn)實(shí)生活中的應(yīng)用，到處可以看到Hash的影子

image.png

image.png

image.png

一切皆是映射：

image.png

哈希函數(shù)（Hash Function），也稱(chēng)為散列函數(shù)或雜湊函數(shù)。哈希函數(shù)是一個(gè)公開(kāi)函數(shù)，可以將任意長(zhǎng)度的消息M映射成為一個(gè)長(zhǎng)度較短且長(zhǎng)度固定的值H（M），稱(chēng)H（M）為哈希值、散列值（Hash Value）、雜湊值或者消息摘要（Message Digest）。它是一種單向密碼體制，即一個(gè)從明文到密文的不可逆映射，只有加密過(guò)程，沒(méi)有解密過(guò)程。

它的函數(shù)表達(dá)式為：h=H（m）

無(wú)論輸入是什么數(shù)字格式、文件有多大，輸出都是固定長(zhǎng)度的比特串。以比特幣使用的Sh256算法為例，無(wú)論輸入是什么數(shù)據(jù)文件，輸出就是256bit。

每個(gè)bit就是一位0或者1，256bit就是256個(gè)0或者1二進(jìn)制數(shù)字串，用16進(jìn)制數(shù)字表示的話，就是多少位呢？

16等于2的4次方，所以每一位16進(jìn)制數(shù)字可以代表4位bit。那么，256位bit用16進(jìn)制數(shù)字表示，當(dāng)然是256除以4等于64位。

于是你通常看到的哈希值，就是這樣的了：

00740f40257a13bf03b40f54a9fe398c79a664bb21cfa2870ab07888b21eeba8

二進(jìn)制計(jì)算的一些基礎(chǔ)知識(shí)

<< : 左移運(yùn)算符，num << 1,相當(dāng)于num乘以2  低位補(bǔ)0
>> : 右移運(yùn)算符，num >> 1,相當(dāng)于num除以2  高位補(bǔ)0
>>> : 無(wú)符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊
 % : 模運(yùn)算 取余
^ :   位異或 第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位相反，那么結(jié)果的第n為也為1，否則為0
 & : 與運(yùn)算 第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位如果都是1，那么結(jié)果的第n為也為1，否則為0
 | :  或運(yùn)算 第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位 只要有一個(gè)是1，那么結(jié)果的第n為也為1，否則為0
 ~ : 非運(yùn)算 操作數(shù)的第n位為1，那么結(jié)果的第n位為0，反之，也就是取反運(yùn)算（一元操作符：只操作一個(gè)數(shù)）

為什么使用 hashcode ，hashCode 存在的第一重要的原因就是在 HashMap(HashSet 其實(shí)就是HashMap) 中使用（其實(shí)Object 類(lèi)的 hashCode 方法注釋已經(jīng)說(shuō)明了 ），我知道，HashMap 之所以速度快，因?yàn)樗褂玫氖巧⒘斜?，根?jù) key 的 hashcode 值生成數(shù)組下標(biāo)（通過(guò)內(nèi)存地址直接查找，沒(méi)有任何判斷），時(shí)間復(fù)雜度完美情況下可以達(dá)到 O(1), 和數(shù)組相同，但是比數(shù)組用著爽多了，但是需要多出很多內(nèi)存，相當(dāng)于以空間換時(shí)間。

Horner計(jì)算字符串哈希值的方法，公式為:

image.png

舉個(gè)例子，比如要獲取”call”的哈希值，字符串c對(duì)應(yīng)的unicode為99，a對(duì)應(yīng)的unicode為97，L對(duì)應(yīng)的unicode為108，所以字符串”call”的哈希值為

3045982 = 99·313 + 97·312 + 108·311 + 108·310 = 108 + 31· (108 + 31 · (97 + 31 · (99)))

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 的 char 數(shù)組的數(shù)字每次乘以 31 再疊加最后返回，因此，每個(gè)不同的字符串，返回的 hashCode 肯定不一樣。那么為什么使用 31 呢？

之所以使用 31， 是因?yàn)樗且粋€(gè)奇素?cái)?shù)。如果乘數(shù)是偶數(shù)，并且乘法溢出的話，信息就會(huì)丟失，因?yàn)榕c2相乘等價(jià)于移位運(yùn)算（低位補(bǔ)0）。使用素?cái)?shù)的好處并不很明顯，但是習(xí)慣上使用素?cái)?shù)來(lái)計(jì)算散列結(jié)果。 31 有個(gè)很好的性能，即用移位和減法來(lái)代替乘法，可以得到更好的性能： 31 * i == (i << 5） - i， 現(xiàn)代的 VM 可以自動(dòng)完成這種優(yōu)化。這個(gè)公式可以很簡(jiǎn)單的推導(dǎo)出來(lái)。

哈希表就是一種以 鍵-值(key-indexed) 存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即key，即可查找到其對(duì)應(yīng)的值。

哈希的思路很簡(jiǎn)單，如果所有的鍵都是整數(shù)，那么就可以使用一個(gè)簡(jiǎn)單的無(wú)序數(shù)組來(lái)實(shí)現(xiàn)：將鍵作為索引，值即為其對(duì)應(yīng)的值，這樣就可以快速訪問(wèn)任意鍵的值。這是對(duì)于簡(jiǎn)單的鍵的情況，我們將其擴(kuò)展到可以處理更加復(fù)雜的類(lèi)型的鍵。

使用哈希查找有兩個(gè)步驟:

1.使用哈希函數(shù)將被查找的鍵轉(zhuǎn)換為數(shù)組的索引。在理想的情況下，不同的鍵會(huì)被轉(zhuǎn)換為不同的索引值，但是在有些情況下我們需要處理多個(gè)鍵被哈希到同一個(gè)索引值的情況。所以哈希查找的第二個(gè)步驟就是處理沖突

2.處理哈希碰撞沖突。有很多處理哈希碰撞沖突的方法，本文后面會(huì)介紹拉鏈法和線性探測(cè)法。

哈希表是一個(gè)在時(shí)間和空間上做出權(quán)衡的經(jīng)典例子。如果沒(méi)有內(nèi)存限制，那么可以直接將鍵作為數(shù)組的索引。那么所有的查找時(shí)間復(fù)雜度為O(1)；如果沒(méi)有時(shí)間限制，那么我們可以使用無(wú)序數(shù)組并進(jìn)行順序查找，這樣只需要很少的內(nèi)存。哈希表使用了適度的時(shí)間和空間來(lái)在這兩個(gè)極端之間找到了平衡。只需要調(diào)整哈希函數(shù)算法即可在時(shí)間和空間上做出取舍。

通過(guò)哈希函數(shù)，我們可以將鍵轉(zhuǎn)換為數(shù)組的索引(0-M-1)，但是對(duì)于兩個(gè)或者多個(gè)鍵具有相同索引值的情況，我們需要有一種方法來(lái)處理這種沖突。

一種比較直接的辦法就是，將大小為M 的數(shù)組的每一個(gè)元素指向一個(gè)條鏈表，鏈表中的每一個(gè)節(jié)點(diǎn)都存儲(chǔ)散列值為該索引的鍵值對(duì)，這就是拉鏈法。

image.png

Hash有哪些流行的算法?

目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的，MD 是 Message Digest 的縮寫(xiě)。其輸出為 128 位。MD4 已證明不夠安全。

MD5（RFC 1321）是 Rivest 于1991年對(duì) MD4 的改進(jìn)版本。它對(duì)輸入仍以 512 位分組，其輸出是 128 位。MD5 比 MD4 復(fù)雜，并且計(jì)算速度要慢一點(diǎn)，更安全一些。MD5 已被證明不具備”強(qiáng)抗碰撞性”。

SHA （Secure Hash Algorithm）是一個(gè) Hash 函數(shù)族，由 NIST（National Institute of Standards and Technology）于 1993 年發(fā)布第一個(gè)算法。目前知名的 SHA-1 在 1995 年面世，它的輸出為長(zhǎng)度 160 位的 hash 值，因此抗窮舉性更好。SHA-1 設(shè)計(jì)時(shí)基于和 MD4 相同原理，并且模仿了該算法。SHA-1 已被證明不具”強(qiáng)抗碰撞性”。

為了提高安全性，NIST 還設(shè)計(jì)出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（統(tǒng)稱(chēng)為 SHA-2），跟 SHA-1 算法原理類(lèi)似。SHA-3 相關(guān)算法也已被提出。

可以看出，上面這幾種流行的算法，它們最重要的一點(diǎn)區(qū)別就是”強(qiáng)抗碰撞性”。

HashMap與ArrayList和LinkedList在數(shù)據(jù)復(fù)雜度上有什么區(qū)別?

image.png

HashMap是對(duì)Array與Link的折衷處理，Array與Link可以說(shuō)是兩個(gè)速度方向的極端，Array注重于數(shù)據(jù)的獲取，而處理修改（添加/刪除）的效率非常低；Link由于是每個(gè)對(duì)象都保持著下一個(gè)對(duì)象的指針，查找某個(gè)數(shù)據(jù)需要遍歷之前所有的數(shù)據(jù)，所以效率比較低，而在修改操作中比較快。