注：本文如涉及到代碼，均經(jīng)過Python 3.7實(shí)際運(yùn)行檢驗(yàn)，保證其嚴(yán)謹(jǐn)性。

本文閱讀時(shí)間約為5分鐘。

在解決散列表的沖突問題之前，我們先介紹完美散列函數(shù)。

什么是完美散列函數(shù)

給定一組數(shù)據(jù)項(xiàng)，如果一個(gè)散列函數(shù)能把每個(gè)數(shù)據(jù)項(xiàng)映射到不同的槽中，那么這個(gè)散列函數(shù)就可以稱為完美散列函數(shù)。

對于固定的一組數(shù)據(jù)，總是能想辦法設(shè)計(jì)出完美散列函數(shù)。但是，如果數(shù)據(jù)項(xiàng)經(jīng)常性地變動(dòng)，很難有一個(gè)系統(tǒng)性的方法來設(shè)計(jì)對應(yīng)的完美散列函數(shù)。此時(shí)就會(huì)出現(xiàn)沖突（collision）。

當(dāng)然，沖突也不是致命性的錯(cuò)誤，同樣有辦法處理。

獲得完美散列函數(shù)的一種方法是，擴(kuò)大散列表的容量，大到所有可能出現(xiàn)的數(shù)據(jù)項(xiàng)都能夠占據(jù)不同的槽。但是，很顯然，這種方法在數(shù)據(jù)項(xiàng)范圍過大的情況下不太實(shí)用，會(huì)浪費(fèi)太多存儲(chǔ)空間，這種代價(jià)太大。

所以，我們采用折中的方案。好的散列函數(shù)需要具備特性：

• 沖突最少（近似完美）。
• 計(jì)算難度低（額外開銷小）。
• 充分分散數(shù)據(jù)項(xiàng)（節(jié)約空間）。

完美散列函數(shù)的更多用途

除了用于在散列表中安排數(shù)據(jù)項(xiàng)的存儲(chǔ)位置，散列技術(shù)還用在信息處理的很多領(lǐng)域。

由于完美散列函數(shù)能夠?qū)θ魏尾煌臄?shù)據(jù)生成不同的散列值，如果把散列值當(dāng)作數(shù)據(jù)的“指紋”或者“摘要”，這種特性被廣泛應(yīng)用在數(shù)據(jù)的一致性校驗(yàn)上。

由任意長度的數(shù)據(jù)生成固定長度的“指紋”，并要求具備唯一性，這在數(shù)學(xué)上是無法做到的。但是，設(shè)計(jì)巧妙的“準(zhǔn)完美”散列函數(shù)卻能在實(shí)用范圍內(nèi)做到這一點(diǎn)。

作為一致性校驗(yàn)的數(shù)據(jù)“指紋”函數(shù)需要具備以下特性：

• 壓縮性——任意長度的數(shù)據(jù)，得到的“指紋”長度是固定的。
• 易計(jì)算性——叢原數(shù)據(jù)計(jì)算“指紋”很容易；從指紋計(jì)算原數(shù)據(jù)是不可能的。
• 抗修改性——對原數(shù)據(jù)的微小改動(dòng)，都會(huì)引起“指紋”的大改變。
• 抗沖突性——已知原數(shù)據(jù)和“指紋”，要找到相同指紋的數(shù)據(jù)（偽造）是非常困難的。

散列函數(shù)MD5/SHA

最著名的近似完美散列函數(shù)是MD5和SHA系列函數(shù)。

MD5（Message Digest）將任何長度的數(shù)據(jù)變換為固定長度為128位（16字節(jié)）的“摘要”。

128位二進(jìn)制已經(jīng)是一個(gè)極為巨大的數(shù)字空間：據(jù)說是地球沙粒的數(shù)量級別。

SHA（Secure Hash Algorithm）是另一組散列函數(shù)。

SHA-0/SHA-1輸出散列值160位（20字節(jié)）。

SHA-256/SHA-224分別輸出256位、224位。

SHA-512/SHA-384分別輸出512位和384位。

160位，相當(dāng)于10的48次方，地球水分子數(shù)量估計(jì)是10的47方。

256位二進(jìn)制相當(dāng)于10的77次方，已知宇宙所有基本粒子大約是10的72次方到87次方之間。

雖然近年來發(fā)現(xiàn)MD5/SHA-0/SHA-1三種散列函數(shù)能以極其特殊的情況來構(gòu)造個(gè)別碰撞（散列沖突），但在實(shí)際應(yīng)用中從未有過實(shí)際的威脅。

Python的散列函數(shù)庫hashlib

Python自帶MD5和SHA系列的散列函數(shù)庫：hashlib，該庫包括了md5/sha1/sha224/sha256/sha384/sha512等6種散列函數(shù)。

import hashlib

# 128位散列值。
hashlib.md5("Hello, World!".encode('utf-8')).hexdigest()
Out[6]: '65a8e27d8879283831b664bd8b7f0ad4'


# 160位散列值。
hashlib.sha1("Hello, World!".encode('utf-8')).hexdigest()
Out[7]: '0a0a9f2a6772942557ab5355d76af442f8f65e01'

無論多么長的字符串，只要使用同一散列函數(shù)庫，返回的位數(shù)都是固定的。如下所示：

hashlib.md5("Are you OK?".encode('utf-8')).hexdigest()
Out[9]: 'eb48ea947c28cb870b638855e2bdbcca'

hashlib.md5("Don't be a cutie pie!".encode('utf-8')).hexdigest()
Out[10]: 'a14615484f10095a3f1af379f7dc7d50'

hashlib.md5("No one knows the new coronavirus better than me.".encode('utf-8')).hexdigest()
Out[11]: 'e4fe757217d4bda4aedb95790608a632'

hashlib.md5("沒人比我更懂新冠病毒。".encode('utf-8')).hexdigest()
Out[12]: '90dd6c2d5bd6f67ebc42561031742785'

除了對單個(gè)的字符串進(jìn)行計(jì)算之外，hashlib庫還支持用update方法來對任意長的數(shù)據(jù)分部分來計(jì)算。無論多大的數(shù)據(jù)，都不會(huì)有內(nèi)存不足的問題。如下所示：

m = hashlib.md5()

m.update("Hello, World!".encode('utf-8'))

m.update("This is part # 2!".encode('utf-8'))

m.update("This is part # 3!".encode('utf-8'))

m.hexdigest()
Out[20]: 'd9b68147bdb0945676799c26039ac4e8'

完美散列函數(shù)的應(yīng)用

完美散列函數(shù)用于數(shù)據(jù)一致性校驗(yàn)，有以下應(yīng)用：

• 數(shù)據(jù)文件一致性判斷。
• 為每個(gè)文件計(jì)算其散列值，僅對比其散列值即可得知文件內(nèi)容是否相同。
• 用于網(wǎng)絡(luò)文件下載完整性校驗(yàn)。
• 用于文件分享系統(tǒng)：比如網(wǎng)盤中相同的文件可以無需存儲(chǔ)多次。
• 加密形式保存密碼。
• 僅保存密碼的散列值，用戶輸入密碼后，計(jì)算散列值并比對。
• 無需保存密碼的明文即可判斷用戶是否輸入了正確的密碼。
• 防止文件篡改：原理同數(shù)據(jù)文件一致性的判斷。防止篡改是電子商務(wù)的信息技術(shù)基礎(chǔ)。

To be continued.