1. Hash是什么，它的作用
先舉個(gè)例子。我們每個(gè)活在世上的人贡避，為了能夠參與各種社會(huì)活動(dòng)，都需要一個(gè)用于識(shí)別自己的標(biāo)志予弧。也許你覺(jué)得名字或是身份證就足以代表你這個(gè)人刮吧，但是這種代表性非常脆弱，因?yàn)橹孛娜撕芏嘁锤颍矸葑C也可以偽造杀捻。最可靠的辦法是把一個(gè)人的所有基因序列記錄下來(lái)用來(lái)代表這個(gè)人，但顯然蚓庭，這樣做并不實(shí)際致讥。而指紋看上去是一種不錯(cuò)的選擇，雖然一些專業(yè)組織仍然可以模擬某個(gè)人的指紋器赞，但這種代價(jià)實(shí)在太高了垢袱。
而對(duì)于在互聯(lián)網(wǎng)世界里傳送的文件來(lái)說(shuō)，如何標(biāo)志一個(gè)文件的身份同樣重要港柜。比如說(shuō)我們下載一個(gè)文件请契，文件的下載過(guò)程中會(huì)經(jīng)過(guò)很多網(wǎng)絡(luò)服務(wù)器、路由器的中轉(zhuǎn)夏醉，如何保證這個(gè)文件就是我們所需要的呢爽锥？我們不可能去一一檢測(cè)這個(gè)文件的每個(gè)字節(jié)，也不能簡(jiǎn)單地利用文件名授舟、文件大小這些極容易偽裝的信息救恨，這時(shí)候，我們就需要一種指紋一樣的標(biāo)志來(lái)檢查文件的可靠性释树，這種指紋就是我們現(xiàn)在所用的Hash算法(也叫散列算法)肠槽。
散列算法（Hash Algorithm）擎淤，又稱哈希算法，雜湊算法秸仙，是一種從任意文件中創(chuàng)造小的數(shù)字「指紋」的方法嘴拢。與指紋一樣，散列算法就是一種以較短的信息來(lái)保證文件唯一性的標(biāo)志寂纪，這種標(biāo)志與文件的每一個(gè)字節(jié)都相關(guān)席吴，而且難以找到逆向規(guī)律。因此捞蛋，當(dāng)原有文件發(fā)生改變時(shí)孝冒，其標(biāo)志值也會(huì)發(fā)生改變，從而告訴文件使用者當(dāng)前的文件已經(jīng)不是你所需求的文件拟杉。
這種標(biāo)志有何意義呢庄涡？之前文件下載過(guò)程就是一個(gè)很好的例子，事實(shí)上搬设，現(xiàn)在大部分的網(wǎng)絡(luò)部署和版本控制工具都在使用散列算法來(lái)保證文件可靠性穴店。而另一方面，我們?cè)谶M(jìn)行文件系統(tǒng)同步拿穴、備份等工具時(shí)泣洞，使用散列算法來(lái)標(biāo)志文件唯一性能幫助我們減少系統(tǒng)開(kāi)銷，這一點(diǎn)在很多云存儲(chǔ)服務(wù)器中都有應(yīng)用默色。
當(dāng)然球凰，作為一種指紋，散列算法最重要的用途在于給證書该窗、文檔弟蚀、密碼等高安全系數(shù)的內(nèi)容添加加密保護(hù)。這一方面的用途主要是得益于散列算法的不可逆性酗失，這種不可逆性體現(xiàn)在，你不僅不可能根據(jù)一段通過(guò)散列算法得到的指紋來(lái)獲得原有的文件昧绣，也不可能簡(jiǎn)單地創(chuàng)造一個(gè)文件并讓它的指紋與一段目標(biāo)指紋相一致规肴。散列算法的這種不可逆性維持著很多安全框架的運(yùn)營(yíng)，而這也將是本文討論的重點(diǎn)夜畴。
2. Hash算法有什么特點(diǎn)
一個(gè)優(yōu)秀的 hash 算法拖刃，將能實(shí)現(xiàn)：
- 正向快速：給定明文和 hash 算法，在有限時(shí)間和有限資源內(nèi)能計(jì)算出 hash 值贪绘。
- 逆向困難：給定（若干） hash 值兑牡，在有限時(shí)間內(nèi)很難（基本不可能）逆推出明文。
- 輸入敏感：原始輸入信息修改一點(diǎn)信息税灌，產(chǎn)生的 hash 值看起來(lái)應(yīng)該都有很大不同均函。
- 沖突避免：很難找到兩段內(nèi)容不同的明文亿虽，使得它們的 hash 值一致（發(fā)生沖突）。即對(duì)于任意兩個(gè)不同的數(shù)據(jù)塊苞也，其hash值相同的可能性極新迕恪；對(duì)于一個(gè)給定的數(shù)據(jù)塊如迟，找到和它hash值相同的數(shù)據(jù)塊極為困難收毫。
但在不同的使用場(chǎng)景中，如數(shù)據(jù)結(jié)構(gòu)和安全領(lǐng)域里殷勘，其中對(duì)某一些特點(diǎn)會(huì)有所側(cè)重此再。
2.1 Hash在管理數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用
在用到hash進(jìn)行管理的數(shù)據(jù)結(jié)構(gòu)中，就對(duì)速度比較重視玲销，對(duì)抗碰撞不太看中引润，只要保證hash均勻分布就可以。比如hashmap痒玩，hash值（key）存在的目的是加速鍵值對(duì)的查找淳附，key的作用是為了將元素適當(dāng)?shù)胤旁诟鱾€(gè)桶里，對(duì)于抗碰撞的要求沒(méi)有那么高蠢古。換句話說(shuō)奴曙，hash出來(lái)的key，只要保證value大致均勻的放在不同的桶里就可以了草讶。但整個(gè)算法的set性能洽糟，直接與hash值產(chǎn)生的速度有關(guān)，所以這時(shí)候的hash值的產(chǎn)生速度就尤為重要堕战，以JDK中的String.hashCode()方法為例：
public int hashCode() {
int h = hash;
//hash default value : 0
if (h == 0 && value.length > 0) {
//value : char storage
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
很簡(jiǎn)潔的一個(gè)乘加迭代運(yùn)算坤溃，在不少的hash算法中，使用的是異或+加法進(jìn)行迭代嘱丢，速度和前者差不多薪介。
2.1 Hash在在密碼學(xué)中的應(yīng)用
在密碼學(xué)中，hash算法的作用主要是用于消息摘要和簽名越驻，換句話說(shuō)汁政，它主要用于對(duì)整個(gè)消息的完整性進(jìn)行校驗(yàn)。舉個(gè)例子缀旁，我們登陸知乎的時(shí)候都需要輸入密碼记劈，那么知乎如果明文保存這個(gè)密碼，那么黑客就很容易竊取大家的密碼來(lái)登陸并巍，特別不安全目木。那么知乎就想到了一個(gè)方法，使用hash算法生成一個(gè)密碼的簽名懊渡，知乎后臺(tái)只保存這個(gè)簽名值刽射。由于hash算法是不可逆的军拟，那么黑客即便得到這個(gè)簽名，也絲毫沒(méi)有用處柄冲；而如果你在網(wǎng)站登陸界面上輸入你的密碼吻谋，那么知乎后臺(tái)就會(huì)重新計(jì)算一下這個(gè)hash值，與網(wǎng)站中儲(chǔ)存的原h(huán)ash值進(jìn)行比對(duì)现横，如果相同漓拾，證明你擁有這個(gè)賬戶的密碼，那么就會(huì)允許你登陸戒祠。銀行也是如此骇两，銀行是萬(wàn)萬(wàn)不敢保存用戶密碼的原文的，只會(huì)保存密碼的hash值而而已姜盈。在這些應(yīng)用場(chǎng)景里低千，對(duì)于抗碰撞和抗篡改能力要求極高，對(duì)速度的要求在其次馏颂。一個(gè)設(shè)計(jì)良好的hash算法示血，其抗碰撞能力是很高的。以MD5為例救拉，其輸出長(zhǎng)度為128位难审，設(shè)計(jì)預(yù)期碰撞概率為2^128焚志，這是一個(gè)極小極小的數(shù)字——而即便是在MD5被王小云教授破解之后毁嗦，其碰撞概率上限也高達(dá)，也就是說(shuō)惜索，至少需要找次才能有1/2的概率來(lái)找到一個(gè)與目標(biāo)文件相同的hash值派昧。而對(duì)于兩個(gè)相似的字符串黔姜，MD5加密結(jié)果如下：
MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8";
可以看到僅僅一個(gè)比特位的改變，二者的MD5值就天差地別了
ps : 其實(shí)把hash算法當(dāng)成是一種加密算法蒂萎，這是不準(zhǔn)確的秆吵，我們知道加密總是相對(duì)于解密而言的，沒(méi)有解密何談加密呢岖是，HASH的設(shè)計(jì)以無(wú)法解為目的的帮毁。并且如果我們不附加一個(gè)隨機(jī)的salt值，HASH口令是很容易被字典攻擊入侵的豺撑。
3. Hash算法是如何實(shí)現(xiàn)的？
密碼學(xué)和信息安全發(fā)展到現(xiàn)在黔牵，各種加密算法和散列算法已經(jīng)不是只言片語(yǔ)所能解釋得了的聪轿。在這里我們僅提供幾個(gè)簡(jiǎn)單的概念供大家參考。
作為散列算法猾浦，首要的功能就是要使用一種算法把原有的體積很大的文件信息用若干個(gè)字符來(lái)記錄陆错，還要保證每一個(gè)字節(jié)都會(huì)對(duì)最終結(jié)果產(chǎn)生影響灯抛。那么大家也許已經(jīng)想到了，求模這種算法就能滿足我們的需要音瓷。
事實(shí)上对嚼，求模算法作為一種不可逆的計(jì)算方法，已經(jīng)成為了整個(gè)現(xiàn)代密碼學(xué)的根基绳慎。只要是涉及到計(jì)算機(jī)安全和加密的領(lǐng)域纵竖，都會(huì)有模計(jì)算的身影。散列算法也并不例外杏愤，一種最原始的散列算法就是單純地選擇一個(gè)數(shù)進(jìn)行模運(yùn)算靡砌，比如以下程序。
# 構(gòu)造散列函數(shù)
def hash(a):
return a % 8
# 測(cè)試散列函數(shù)功能
print(hash(233))
print(hash(234))
print(hash(235))
# 輸出結(jié)果
- 1
- 2
- 3
很顯然珊楼，上述的程序完成了一個(gè)散列算法所應(yīng)當(dāng)實(shí)現(xiàn)的初級(jí)目標(biāo)：用較少的文本量代表很長(zhǎng)的內(nèi)容（求模之后的數(shù)字肯定小于8）通殃。但也許你已經(jīng)注意到了，單純使用求模算法計(jì)算之后的結(jié)果帶有明顯的規(guī)律性厕宗，這種規(guī)律將導(dǎo)致算法將能難保證不可逆性画舌。所以我們將使用另外一種手段，那就是異或已慢。
再來(lái)看下面一段程序曲聂，我們?cè)谏⒘泻瘮?shù)中加入一個(gè)異或過(guò)程。
# 構(gòu)造散列函數(shù)
def hash(a):
return (a % 8) ^ 5
# 測(cè)試散列函數(shù)功能
print(hash(233))
print(hash(234))
print(hash(235))
# 輸出結(jié)果
- 4
- 7
- 6
很明顯的蛇受，加入一層異或過(guò)程之后句葵，計(jì)算之后的結(jié)果規(guī)律性就不是那么明顯了。
當(dāng)然兢仰，大家也許會(huì)覺(jué)得這樣的算法依舊很不安全乍丈，如果用戶使用連續(xù)變化的一系列文本與計(jì)算結(jié)果相比對(duì)，就很有可能找到算法所包含的規(guī)律把将。但是我們還有其他的辦法轻专。比如在進(jìn)行計(jì)算之前對(duì)原始文本進(jìn)行修改，或是加入額外的運(yùn)算過(guò)程（如移位）察蹲，比如以下程序请垛。
# 構(gòu)造散列函數(shù)
def hash(a):
return (a + 2 + (a << 1)) % 8 ^ 5
# 測(cè)試散列函數(shù)功能
print(hash(233))
print(hash(234))
print(hash(235))
# 輸出結(jié)果
- 0
- 5
- 6
這樣處理得到的散列算法就很難發(fā)現(xiàn)其內(nèi)部規(guī)律，也就是說(shuō)洽议，我們并不能很輕易地給出一個(gè)數(shù)宗收，讓它經(jīng)過(guò)上述散列函數(shù)運(yùn)算之后的結(jié)果等于4——除非我們?nèi)ジF舉測(cè)試。
上面的算法是不是很簡(jiǎn)單亚兄？事實(shí)上混稽，下面我們即將介紹的常用算法MD5和SHA1，其本質(zhì)算法就是這么簡(jiǎn)單，只不過(guò)會(huì)加入更多的循環(huán)和計(jì)算匈勋，來(lái)加強(qiáng)散列函數(shù)的可靠性礼旅。
4. Hash有哪些流行的算法
目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2洽洁。
MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的痘系，MD 是 Message Digest 的縮寫。其輸出為 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)稱為 SHA-2）飘言，跟 SHA-1 算法原理類似衣形。SHA-3 相關(guān)算法也已被提出。
可以看出姿鸿，上面這幾種流行的算法谆吴，它們最重要的一點(diǎn)區(qū)別就是"強(qiáng)抗碰撞性"。
5. 那么苛预，何謂Hash算法的「碰撞」句狼？
你可能已經(jīng)發(fā)現(xiàn)了，在實(shí)現(xiàn)算法章節(jié)的第一個(gè)例子热某，我們嘗試的散列算法得到的值一定是一個(gè)不大于8的自然數(shù)鲜锚，因此突诬，如果我們隨便拿9個(gè)數(shù)去計(jì)算苫拍，肯定至少會(huì)得到兩個(gè)相同的值芜繁，我們把這種情況就叫做散列算法的「碰撞」（Collision）。
這很容易理解绒极，因?yàn)樽鳛橐环N可用的散列算法骏令，其位數(shù)一定是有限的，也就是說(shuō)它能記錄的文件是有限的——而文件數(shù)量是無(wú)限的垄提，兩個(gè)文件指紋發(fā)生碰撞的概率永遠(yuǎn)不會(huì)是零榔袋。
但這并不意味著散列算法就不能用了，因?yàn)榉彩露家紤]代價(jià)铡俐，買光所有彩票去中一次頭獎(jiǎng)是毫無(wú)意義的』硕遥現(xiàn)代散列算法所存在的理由就是，它的不可逆性能在較大概率上得到實(shí)現(xiàn)审丘，也就是說(shuō)吏够，發(fā)現(xiàn)碰撞的概率很小，這種碰撞能被利用的概率更小滩报。
隨意找到一組碰撞是有可能的锅知，只要窮舉就可以。散列算法得到的指紋位數(shù)是有限的脓钾，比如MD5算法指紋字長(zhǎng)為128位售睹，意味著只要我們窮舉2^128次，就肯定能得到一組碰撞——當(dāng)然可训，這個(gè)時(shí)間代價(jià)是難以想象的昌妹，而更重要的是，僅僅找到一組碰撞并沒(méi)有什么實(shí)際意義握截。更有意義的是飞崖，如果我們已經(jīng)有了一組指紋，能否找到一個(gè)原始文件川蒙，讓它的散列計(jì)算結(jié)果等于這組指紋蚜厉。如果這一點(diǎn)被實(shí)現(xiàn)，我們就可以很容易地篡改和偽造網(wǎng)絡(luò)證書畜眨、密碼等關(guān)鍵信息昼牛。
你也許已經(jīng)聽(tīng)過(guò)MD5已經(jīng)被破解的新聞——但事實(shí)上，即便是MD5這種已經(jīng)過(guò)時(shí)的散列算法康聂，也很難實(shí)現(xiàn)逆向運(yùn)算贰健。我們現(xiàn)在更多的還是依賴于海量字典來(lái)進(jìn)行嘗試，也就是通過(guò)已經(jīng)知道的大量的文件——指紋對(duì)應(yīng)關(guān)系恬汁，搜索某個(gè)指紋所對(duì)應(yīng)的文件是否在數(shù)據(jù)庫(kù)里存在伶椿。
5.1 MD5的實(shí)際碰撞案例
下面讓我們來(lái)看看一個(gè)真實(shí)的碰撞案例。我們之所以說(shuō)MD5過(guò)時(shí)，是因?yàn)樗谀承r(shí)候已經(jīng)很難表現(xiàn)出散列算法的某些優(yōu)勢(shì)——比如在應(yīng)對(duì)文件的微小修改時(shí)脊另，散列算法得到的指紋結(jié)果應(yīng)當(dāng)有顯著的不同导狡，而下面的程序說(shuō)明了MD5并不能實(shí)現(xiàn)這一點(diǎn)。
import hashlib
# 兩段HEX字節(jié)串偎痛，注意它們有細(xì)微差別
a = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef")
b = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef")
# 輸出MD5旱捧，它們的結(jié)果一致
print(hashlib.md5(a).hexdigest())
print(hashlib.md5(b).hexdigest())
### a和b輸出結(jié)果都為：
cee9a457e790cf20d4bdaa6d69f01e41
cee9a457e790cf20d4bdaa6d69f01e41
而諸如此類的碰撞案例還有很多，上面只是原始文件相對(duì)較小的一個(gè)例子踩麦。事實(shí)上現(xiàn)在我們用智能手機(jī)只要數(shù)秒就能找到MD5的一個(gè)碰撞案例枚赡，因此，MD5在數(shù)年前就已經(jīng)不被推薦作為應(yīng)用中的散列算法方案谓谦，取代它的是SHA家族算法贫橙，也就是安全散列算法（Secure Hash Algorithm，縮寫為SHA）反粥。
5.2 SHA家族算法以及SHA1碰撞
安全散列算法與MD5算法本質(zhì)上的算法是類似的卢肃，但安全性要領(lǐng)先很多——這種領(lǐng)先型更多的表現(xiàn)在碰撞攻擊的時(shí)間開(kāi)銷更大，當(dāng)然相對(duì)應(yīng)的計(jì)算時(shí)間也會(huì)慢一點(diǎn)星压。
SHA家族算法的種類很多践剂，有SHA0、SHA1娜膘、SHA256逊脯、SHA384等等，它們的計(jì)算方式和計(jì)算速度都有差別竣贪。其中SHA1是現(xiàn)在用途最廣泛的一種算法军洼。包括GitHub在內(nèi)的眾多版本控制工具以及各種云同步服務(wù)都是用SHA1來(lái)區(qū)別文件，很多安全證書或是簽名也使用SHA1來(lái)保證唯一性演怎。長(zhǎng)期以來(lái)匕争，人們都認(rèn)為SHA1是十分安全的，至少大家還沒(méi)有找到一次碰撞案例爷耀。
但這一事實(shí)在2017年2月破滅了甘桑。CWI和Google的研究人員們成功找到了一例SHA1碰撞，而且很厲害的是歹叮，發(fā)生碰撞的是兩個(gè)真實(shí)的跑杭、可閱讀的PDF文件。這兩個(gè)PDF文件內(nèi)容不相同咆耿，但SHA1值完全一樣德谅。(對(duì)于這件事的影響范圍及討論，可參考知乎上的討論:如何評(píng)價(jià) 2 月 23 日谷歌宣布實(shí)現(xiàn)了 SHA-1 碰撞萨螺？)
所以窄做，對(duì)于一些大的商業(yè)機(jī)構(gòu)來(lái)說(shuō)愧驱， MD5 和 SHA1 已經(jīng)不夠安全，推薦至少使用 SHA2-256 算法椭盏。
6. Hash在Java中的應(yīng)用
6.1 HashMap的復(fù)雜度
在介紹HashMap的實(shí)現(xiàn)之前组砚，先考慮一下，HashMap與ArrayList和LinkedList在數(shù)據(jù)復(fù)雜度上有什么區(qū)別庸汗。下圖是他們的性能對(duì)比圖：
| 獲取 | 查找 | 添加/刪除 | 空間 | |
|---|---|---|---|---|
| ArrayList | O(1) | O(1) | O(N) | O(N) |
| LinkedList | O(N) | O(N) | O(1) | O(N) |
| HashMap | O(N/Bucket_size) | O(N/Bucket_size) | O(N/Bucket_size) | O(N) |
可以看出HashMap整體上性能都非常不錯(cuò)惫确，但是不穩(wěn)定，為O(N/Buckets)蚯舱，N就是以數(shù)組中沒(méi)有發(fā)生碰撞的元素，Buckets是因碰撞產(chǎn)生的鏈表掩蛤。
注：發(fā)生碰撞實(shí)際上是非常稀少的枉昏，所以N/Bucket_size約等于1
HashMap是對(duì)Array與Link的折衷處理，Array與Link可以說(shuō)是兩個(gè)速度方向的極端揍鸟，Array注重于數(shù)據(jù)的獲取兄裂，而處理修改（添加/刪除）的效率非常低；Link由于是每個(gè)對(duì)象都保持著下一個(gè)對(duì)象的指針阳藻，查找某個(gè)數(shù)據(jù)需要遍歷之前所有的數(shù)據(jù)晰奖，所以效率比較低，而在修改操作中比較快腥泥。
6.2 HashMap的實(shí)現(xiàn)
本文以JDK8的API實(shí)現(xiàn)進(jìn)行分析
6.2.1 對(duì)key進(jìn)行Hash計(jì)算
在JDK8中匾南，由于使用了紅黑樹(shù)來(lái)處理大的鏈表開(kāi)銷，所以hash這邊可以更加省力了蛔外，只用計(jì)算hashCode并移動(dòng)到低位就可以了蛆楞。
static final int hash(Object key) {
int h;
//計(jì)算hashCode，并無(wú)符號(hào)移動(dòng)到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
舉個(gè)例子: 363771819^(363771819 >>> 16)
0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)
這樣做可以實(shí)現(xiàn)了高地位更加均勻地混到一起夹厌。
下面給出在Java中幾個(gè)常用的哈希碼(hashCode)的算法豹爹。
Object類的hashCode. 返回對(duì)象的經(jīng)過(guò)處理后的內(nèi)存地址，由于每個(gè)對(duì)象的內(nèi)存地址都不一樣矛纹，所以哈希碼也不一樣臂聋。這個(gè)是native方法，取決于JVM的內(nèi)部設(shè)計(jì)或南，一般是某種C地址的偏移孩等。
String類的hashCode. 根據(jù)String類包含的字符串的內(nèi)容，根據(jù)一種特殊算法返回哈希碼迎献，只要字符串的內(nèi)容相同瞎访，返回的哈希碼也相同。
Integer等包裝類吁恍，返回的哈希碼就是Integer對(duì)象里所包含的那個(gè)整數(shù)的數(shù)值扒秸，例如Integer i1=new Integer(100), i1.hashCode的值就是100 播演。由此可見(jiàn)，2個(gè)一樣大小的Integer對(duì)象伴奥，返回的哈希碼也一樣写烤。
int，char這樣的基礎(chǔ)類拾徙，它們不需要hashCode洲炊，如果需要存儲(chǔ)時(shí)，將進(jìn)行自動(dòng)裝箱操作尼啡，計(jì)算方法同上暂衡。
6.2.2 獲取到數(shù)組的index的位置
計(jì)算了Hash，我們現(xiàn)在要把它插入數(shù)組中了
i = (tab.length - 1) & hash崖瞭；
通過(guò)位運(yùn)算狂巢，確定了當(dāng)前的位置，因?yàn)镠ashMap數(shù)組的大小總是2^n书聚，所以實(shí)際的運(yùn)算就是 (0xfff...ff) & hash 唧领，這里的tab.length-1相當(dāng)于一個(gè)mask，濾掉了大于當(dāng)前長(zhǎng)度位的hash雌续，使每個(gè)i都能插入到數(shù)組中斩个。
6.2.3 生成包裝類
這個(gè)對(duì)象是一個(gè)包裝類，Node<K,V>驯杜，內(nèi)部有key,value,hash還有next受啥，可以看出來(lái)它是一個(gè)鏈表。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//getter and setter .etc.
}
6.2.4 插入包裝類到數(shù)組
(1). 如果輸入當(dāng)前的位置是空的艇肴，就插進(jìn)去腔呜，如圖，左為插入前再悼，右為插入后
0 0
| |
1 -> null 1 - > null
| |
2 -> null 2 - > null
| |
..-> null ..- > null
| |
i -> null i - > new node
| |
n -> null n - > null
(2). 如果當(dāng)前位置已經(jīng)有了node核畴，且它們發(fā)生了碰撞，則新的放到前面冲九，舊的放到后面谤草，這叫做鏈地址法處理沖突。
0 0
| |
1 -> null 1 - > null
| |
2 -> null 2 - > null
| |
..-> null ..- > null
| |
i -> old i - > new - > old
| |
n -> null n - > null
我們可以發(fā)現(xiàn)莺奸，失敗的hashCode算法會(huì)導(dǎo)致HashMap的性能由數(shù)組下降為鏈表丑孩，所以想要避免發(fā)生碰撞，就要提高h(yuǎn)ashCode結(jié)果的均勻性灭贷。
6.3 擴(kuò)容
如果當(dāng)表中的75%已經(jīng)被占用温学，即視為需要擴(kuò)容了
(threshold = capacity * load factor ) < size
它主要有兩個(gè)步驟：
6.3.1 容量加倍
左移1位，就是擴(kuò)大到兩倍甚疟，用位運(yùn)算取代了乘法運(yùn)算
newCap = oldCap << 1;
newThr = oldThr << 1;
6.3.2 遍歷計(jì)算Hash
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果發(fā)現(xiàn)當(dāng)前有Bucket
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果這里沒(méi)有碰撞
if (e.next == null)
//重新計(jì)算Hash仗岖，分配位置
newTab[e.hash & (newCap - 1)] = e;
//這個(gè)見(jiàn)下面的新特性介紹逃延，如果是樹(shù)，就填入樹(shù)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果是鏈表轧拄，就保留順序....目前就看懂這點(diǎn)
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
由此可以看出擴(kuò)容需要遍歷并重新賦值揽祥，成本非常高，所以選擇一個(gè)好的初始容量非常重要檩电。
6.4 擴(kuò)容如何提升性能拄丰？
解決擴(kuò)容損失：如果知道大致需要的容量，把初始容量設(shè)置好以解決擴(kuò)容損失俐末；
比如我現(xiàn)在有1000個(gè)數(shù)據(jù)料按，需要 1000/0.75 = 1333 個(gè)坑位，又 1024 < 1333 < 2048鹅搪，所以最好使用2048作為初始容量站绪。解決碰撞損失：使用高效的HashCode與loadFactor，這個(gè)...由于JDK8的高性能出現(xiàn)丽柿，這兒?jiǎn)栴}也不大了。
6.5 HashMap與HashTable的主要區(qū)別
在很多的Java基礎(chǔ)書上都已經(jīng)說(shuō)過(guò)了魂挂，他們的主要區(qū)別其實(shí)就是Table全局加了線程同步保護(hù)
- HashTable線程更加安全甫题，代價(jià)就是因?yàn)樗直┑奶砑恿送芥i，所以會(huì)有性能損失涂召。
- 其實(shí)有更好的concurrentHashMap可以替代HashTable坠非，一個(gè)是方法級(jí)，一個(gè)是Class級(jí)果正。
6.6 在Android中使用SparseArray代替HashMap
官方推薦使用SparseArray([spɑ:s][?'re?],稀疏的數(shù)組)或者LongSparseArray代替HashMap炎码。官方總結(jié)有一下幾點(diǎn)好處：
SparseArray使用基本類型(Primitive)中的int作為Key，不需要Pair<K,V>或者Entry<K,V>這樣的包裝類秋泳，節(jié)約了內(nèi)存;
SpareArray維護(hù)的是一個(gè)排序好的數(shù)組潦闲，使用二分查找數(shù)據(jù)，即O(log(N))迫皱，每次插入數(shù)據(jù)都要進(jìn)行排序歉闰，同樣耗時(shí)O(N)；而HashMap使用hashCode來(lái)加入/查找/刪除數(shù)據(jù)卓起，即O(N/buckets_size)和敬；
總的來(lái)說(shuō)，就是SparseArray針對(duì)Android嵌入式設(shè)備進(jìn)行了優(yōu)化戏阅，犧牲了微小的時(shí)間性能昼弟，換取了更大的內(nèi)存優(yōu)化;同時(shí)它還有別的優(yōu)化，比如對(duì)刪除操作做了優(yōu)化奕筐；
如果你的數(shù)據(jù)非常少(實(shí)際上也是如此)舱痘，那么使用SpareArray也是不錯(cuò)的变骡；
總結(jié)
「The Algorithm Design Manual」一書中提到，雅虎的 Chief Scientist 衰粹，Udi Manber 曾說(shuō)過(guò)锣光，在 yahoo 所應(yīng)用的算法中，最重要的三個(gè)是：Hash铝耻，Hash 和 Hash誊爹。其實(shí)從上文中所舉的git用sha1判斷文件更改，密碼用MD5生成摘要后加鹽等等對(duì)Hash的應(yīng)用可看出瓢捉，Hash的在計(jì)算機(jī)世界扮演著多么重要的角色频丘。另書中還舉了一個(gè)很有趣的顯示中例子：
一場(chǎng)拍賣會(huì)中，物品是價(jià)高者得泡态，如果每個(gè)人只有一次出價(jià)機(jī)會(huì)搂漠，同時(shí)提交自己的價(jià)格后，最后一起公布某弦，出價(jià)最高則勝出桐汤。這種形式存在作弊的可能，如果有出價(jià)者能 hack 進(jìn)后臺(tái)靶壮，然后將自己的價(jià)格改為最高價(jià) +1怔毛，則能以最低的代價(jià)獲得勝利。如何杜絕這種作弊呢腾降？
答案很簡(jiǎn)單拣度，參與者都提交自身出價(jià)的 hash 值就可以了，即使有人能黑進(jìn)后臺(tái)也無(wú)法得知明文價(jià)格螃壤，等到公布之時(shí)抗果，再對(duì)比原出價(jià)與 hash 值是否對(duì)應(yīng)即可。是不是很巧妙奸晴？
是的冤馏，上面的做法，與上文提到的網(wǎng)站上儲(chǔ)存密碼用MD5 值而非明文蚁滋，是同一種思想宿接，殊途同歸。
可以看到無(wú)論是密碼學(xué)辕录、數(shù)據(jù)結(jié)構(gòu)睦霎、現(xiàn)實(shí)生活中的應(yīng)用，到處可以看到Hash的影子走诞，通過(guò)這篇文章的介紹副女，相信你不僅知其名，也能懂其意蚣旱。
Reference
- https://jizhi.im/blog/post/sha1decrypt
- http://www.reibang.com/p/e54047b2b563
- https://www.zhihu.com/question/26762707
- http://mp.weixin.qq.com/s?__biz=MzA5ODUzOTA0OQ==&mid=2651688220&idx=1&sn=a3f9cb1e186ffe22d9825bca00e85c76&chksm=8b692e5abc1ea74ce61a819f5666dd7d73ee45d6145c92b993de271a315d4f3d3fb3874f9be3&mpshare=1&scene=23&srcid=0414EOLCuLSu17uo8Aw8refB#rd
- http://mp.weixin.qq.com/s/oRLkR7jplqO2qhHtUeTMIA
