目錄
一，什么是哈希函數(shù)？
二，哈希表（hash table）原理
三，為什么不是所有的 hash 函數(shù)都可以被用來(lái)加密？
四，哈希碰撞（hash collision）的解決方式
五，什么是好的哈希函數(shù)？
六，哈希函數(shù)的構(gòu)造方法
七，為什么不能對(duì)可變的對(duì)象進(jìn)行 hash 處理？
八，大型網(wǎng)站如何利用 hash 函數(shù)保護(hù)用戶密碼？
九，Python3.x 增加的隨機(jī)性
十，其他 hash 算法
? ?
背景
哈希（hash）算法，原先是一種被用在資料編碼中的技術(shù)，可以被用來(lái)加密要隱藏的資料，還可以被用來(lái)，比較不同文本的相似度。哈希算法屬于信息摘要（Message Digest）算法。
區(qū)塊鏈技術(shù)背后的底層原理之一，即為哈希算法。理解了哈希函數(shù)，自然就會(huì)理解區(qū)塊鏈的挖礦模式。
全面的 hash 算法列表網(wǎng)址： ( http://burtleburtle.net/bob/hash/ )
一，什么是哈希函數(shù)？
哈希函數(shù)（hash function）: 也稱為「散列函數(shù)」或「雜湊函數(shù)」。
h = H(M)
哈希函數(shù)將任意長(zhǎng)度的消息 M，映射成為一個(gè)長(zhǎng)度較短且長(zhǎng)度固定的值 H（M）。H(M)即為散列值或哈希值（hash value）。
哈希算法是一種信息摘要（Message Digest）算法。對(duì)象的 hash 值比原對(duì)象擁有更低的內(nèi)存復(fù)雜度。是一種壓縮映射。
根據(jù)哈希函數(shù)所建立的表為哈希表。
2
二，哈希表（hash table）原理
哈希表（hash table）|散列表，是根據(jù)關(guān)鍵碼值進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。屬于鍵和值之間的一 一對(duì)應(yīng)關(guān)系。
通常提供查找（search），插入（insert），刪除（delete）等操作。跟數(shù)組一樣都是一種數(shù)據(jù)結(jié)構(gòu)。與字典類(lèi)似，通過(guò)鍵值對(duì)（key-indexed）來(lái)保存數(shù)據(jù)。
目前大部分動(dòng)態(tài)語(yǔ)言的實(shí)現(xiàn)中都使用了哈希表。有些語(yǔ)音將哈希表乘坐字典，但是哈希表跟字典并不完全相同。哈希表是弱類(lèi)型的，而字典是強(qiáng)類(lèi)型的。
哈希表查找一個(gè)元素的時(shí)間復(fù)雜度為0（1），效率極高，這也是它的一個(gè)重要優(yōu)點(diǎn)。
鍵（key）：操作數(shù)據(jù)的標(biāo)識(shí)。
槽（bucket）：用于存放數(shù)據(jù)的單元。
創(chuàng)建自己的哈希表
三，大型網(wǎng)站如何利用 hash 函數(shù)保護(hù)用戶密碼？
即使大型網(wǎng)站的數(shù)據(jù)庫(kù)被攻破，也不會(huì)造成太大損失。為什么呢？這涉及到了哈希函數(shù)的兩個(gè)主要特性：不可逆性與抗碰撞性。
利用哈希函數(shù)對(duì)用戶密碼進(jìn)行加密：用戶設(shè)置完密碼后，會(huì)被轉(zhuǎn)換成 hash 值，并保存到數(shù)據(jù)庫(kù)中。如下圖。
pip3?installsimhash
?被保存的只是轉(zhuǎn)換后的哈希值，而不是原密碼。
由于哈希（hash）函數(shù)是不可逆的，只能由輸入產(chǎn)生輸出，不能由輸出產(chǎn)生輸入。系統(tǒng)服務(wù)器無(wú)法根據(jù)每個(gè) hash 值逆過(guò)來(lái)推算出原密碼。因此即使是后臺(tái)工作人員，也無(wú)法得知用戶的原密碼。
用戶登錄的時(shí)候，輸入密碼，經(jīng)過(guò) hash 操作后轉(zhuǎn)換成 hash 值，再與數(shù)據(jù)庫(kù)中被保存的 hash 值進(jìn)行對(duì)比。hash 值完全一樣，則密碼正確。
? ?
四，為什么不是所有的 hash 函數(shù)都可以被用來(lái)加密？
不是所有的 hash 函數(shù)都可以被用來(lái)加密，這就涉及到了哈希碰撞（hash collision）。
對(duì)于 hash 算法，一般情況下，不同的數(shù)據(jù)會(huì)生成不同的哈希值。但是如果兩個(gè)不同的數(shù)據(jù)，經(jīng)過(guò) Hash 函數(shù)計(jì)算后，得到的 Hash 值一樣，則為哈希碰撞（collision）。
即 f (key1) = f(key2)
哈希碰撞無(wú)法被完全避免。只能降低其發(fā)生概率。
碰撞攻擊則是找到另一個(gè)跟原密碼具有相同 hash 值的字符串。
為了提高安全性，只有加密哈希函數(shù)（cryptgraphic hash functions）可以被用來(lái)加密。如 SHA256, SHA512, Ripemd， WHIRLPOOL 等 。這類(lèi)函數(shù)的 hash 破解異常困難，幾乎不太可能出現(xiàn) hash 碰撞。
? ?
五，哈希碰撞（hash collision）的解決方式
一，開(kāi)放尋址法（open addressing)
二，拉鏈法
開(kāi)放尋址法的總體設(shè)計(jì)原理為：出現(xiàn)哈希碰撞時(shí)，重新檢測(cè)一個(gè)空閑位置，并插入。
但是這樣會(huì)產(chǎn)生一個(gè)問(wèn)題，即占用其他槽位的空間，以致于后續(xù)的插入操作更容易出現(xiàn)沖突。因此在利用開(kāi)放尋址法的時(shí)候，裝載因子最好保持在0.5以下。
裝載因子 = 保存的元素?cái)?shù)量/容量
[1]開(kāi)放尋址法有：
線性探測(cè)器（Linear Probing）
二次探測(cè)法（Quadratic Probing）
隨機(jī)探測(cè)法
雙散列（Double hashing）
再哈希法
建立一個(gè)公共溢出區(qū)
線性探測(cè)法介紹：
線性探測(cè)法為開(kāi)放尋址法最簡(jiǎn)單的一種實(shí)現(xiàn)。
線性探測(cè)法用來(lái)解決哈希碰撞的原理是：當(dāng)某個(gè)被給定鍵在散列表中的對(duì)應(yīng)單元已被占用時(shí)（即我們向當(dāng)前哈希表寫(xiě)入數(shù)據(jù)時(shí)發(fā)生了沖突），會(huì)檢測(cè)散列表中離沖突單元最近的空閑單元。并把該鍵值對(duì)寫(xiě)入到下一個(gè)不為空的位置。
只要哈希表未被填滿，總能找到一個(gè)不發(fā)生沖突的單元。
再哈希法：
再哈希法用來(lái)解決哈希碰撞的原理是：兩個(gè)值產(chǎn)生沖突時(shí)，通過(guò)下面算式，計(jì)算另一地址，直到不再?zèng)_突。
Hi = R * Hi(key) [i = 1,2,...k]
同樣的關(guān)鍵字，同樣的哈希函數(shù)，用不同的處理哈希碰撞的方法，得到的哈希函數(shù)值也不同。
? ?
六，什么是好的哈希函數(shù)？
哈希表的關(guān)鍵點(diǎn)就在于哈希函數(shù)的選擇。
若對(duì)于關(guān)鍵字集合中的，任意一個(gè)關(guān)鍵字，經(jīng)過(guò)哈希函數(shù)，映像到地址集合中，任何一個(gè)地址的概率是相等的，則為均勻散列函數(shù)（uniform hash function）。也即好的哈希函數(shù)。
這種方法通過(guò)將關(guān)鍵字映射到“均勻分布的隨機(jī)地址”來(lái)減少?zèng)_突。
目前的哈希算法都能良好的將key進(jìn)行比較均勻的分布。
? ?
七，哈希函數(shù)的構(gòu)造方法：
直接定址法
除留余數(shù)法
數(shù)字分析法
折疊法
平方取中法
直接定址法：取關(guān)鍵字，或關(guān)鍵字的某個(gè)線性函數(shù)值，為哈希地址。
即：H（key） = key 或 H (key) = a * key + b
鏈地址法：將所有相似關(guān)鍵詞的記錄存儲(chǔ)在同一線性鏈表中。
? ?
八，為什么不能對(duì)可變的對(duì)象進(jìn)行 hash 處理？
首先要了解兩個(gè)概念，可哈希性（hashable）與不可哈希性（unhashable）。
可哈希性（hashable）：可哈希的數(shù)據(jù)類(lèi)型為不可變的數(shù)據(jù)結(jié)構(gòu)（如字符串 srt，元組 tuple，對(duì)象集 objects 等）。這種數(shù)據(jù)被稱為可哈希性。
不可哈希性：不可哈希的數(shù)據(jù)類(lèi)型，為可變的數(shù)據(jù)結(jié)構(gòu)（如字典 dict，列表 list 和集合 set 等）。
如果對(duì)可變的對(duì)象進(jìn)行哈希處理，則每次對(duì)象更新時(shí)，都需要更新哈希表。這樣我們則需要將對(duì)象移至不同的數(shù)據(jù)集，這種操作會(huì)使花費(fèi)過(guò)大。
因此設(shè)定不能對(duì)可變的對(duì)象進(jìn)行 hash 處理。
? ?
九，Python3.x 增加的隨機(jī)性
Python3.x添加了 hash 算法的隨機(jī)性，以提高安全性，因此對(duì)于每個(gè)新的 python 調(diào)用，同樣的數(shù)據(jù)源生成的結(jié)果都將不同。 下面為算法實(shí)例。
?
?
哈希方法有（MD5, SHA1, SHA256 與 SHA512 等）。常用的有 SH256 與 SHA512，即上文提到的加密哈希函數(shù)（cryptgraphic hash functions）。MD5 與 SHA1 不再常用。
MDH5 (不常用)
SHA1 (不常用)
SHA256 (常用)
SHA512 (常用)
? ?
十，其他 hash 算法**
1. simhash 算法:
這是一種局部敏感的 hash 算法，它產(chǎn)生的簽名在一定程度上可以表征原內(nèi)容的相似度。
可以被用來(lái)比較文本的相似度。
如下代碼安裝 simhash 模塊。
pip3?installsimhash
2. Imagehash 算法:
Imagehash 算法為感知哈希算法（perceptual Hash Algorithm）。
常被用來(lái)檢測(cè)圖像和視頻的差異。
如下代碼安裝 Imagehash 模塊。
pip3 install simhash
例如：可以通過(guò)比較兩張圖片的 hash 值來(lái)判斷相似度。下面為比較兩張相似圖片的代碼示例。
?
??
?
輸出為：
hash(image1) =00fd43c3**f**fffffff
hash(image2) =00fd43c3f**e**ffffff
從輸出結(jié)果可以看到兩張圖片的 hash 值非常相似。相似的圖片可以生成相似的哈希值是 Imagehash 的特點(diǎn)。
后續(xù)再詳細(xì)更新哈希碰撞的解決方式
?
?
?
