哈希（Hash）

哈希函數（英語：Hash function）又稱哈希算法、散列函數，是一種從任何一種數據中創建小的數字「指紋」的方法。哈希函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函數將數據打亂混合，重新創建一個叫做哈希值（又叫散列值）（hash values，hash codes，hash sums，或hashes）的指紋。哈希值通常用一個短的隨機字母和數字組成的字符串來代表。好的哈希函數在輸入域中很少出現哈希衝突。如果在哈希表和數據處理中，不抑制衝突來區別數據，會使得數據庫記錄更難找到。

如今，哈希函數也被用來加密存在數據庫中的密碼（password）字符串，由於哈希算法所計算出來的哈希值（Hash Value）具有不可逆（無法逆向演算回原本的數值）的性質，因此可有效的保護密碼。

哈希函數與校驗和、校驗位、指紋、失真壓縮、隨機化函數、糾錯碼和密碼學有所關聯並常被混淆。儘管這些概念在某些方面有所重疊，但每個概念都有其特定的用途和要求，並且在設計和優化上有所不同。哈希函數與這些概念的主要區別在於數據完整性。哈希表可能使用非加密哈希函數，而加密哈希函數則用於網絡安全領域，以保護敏感數據，例如密碼。

哈希函數的性質

所有哈希函數都有如下一個基本特性：如果兩個哈希值是不相同的（根據同一函數），那麼這兩個哈希值的原始輸入也是不相同的。這個特性是哈希函數具有確定性的結果，具有這種性質的哈希函數稱為單向哈希函數。但另一方面，哈希函數的輸入和輸出不是唯一對應關係的，如果兩個哈希值相同，兩個輸入值很可能是相同的，但也可能不同，這種情況稱為「哈希碰撞（collision）」，這通常是兩個不同長度的輸入值，刻意計算出相同的輸出值。輸入一些數據計算出哈希值，然後部分改變輸入值，一個具有強混淆特性的哈希函數會產生一個完全不同的哈希值。

典型的哈希函數都有非常大的定義域，比如SHA-2最高接受(2⁶⁴-1)/8長度的字節字符串。同時哈希函數一定有着有限的值域，比如固定長度的比特串。在某些情況下，哈希函數可以設計成具有相同大小的定義域和值域間的單射。在密碼學中，哈希函數必須具有不可逆性。

在哈希表中，哈希函數將一個鍵作為輸入。鍵與數據或記錄相關聯，用於在數據存儲和檢索應用中標識它們。鍵可以是固定長度的（如整數）或可變長度的（如名字）。在某些情況下，鍵本身就是數據。哈希函數的輸出是一個哈希碼，用於索引存放數據或記錄（或指向它們的指針）的哈希表。

哈希函數可以視為執行以下三個功能：

1. 將可變長度的鍵轉換為固定長度的值（通常是機器字長或更小），通過使用諸如加法（ADD）或異或（XOR）等保持奇偶性的操作符進行分組處理；
2. 對鍵的位進行擾亂，使生成的值在鍵空間中均勻分佈；
3. 將鍵值映射到小於或等於哈希表大小的值。

一個好的哈希函數需要滿足兩個基本屬性：計算速度非常快，並且儘量減少輸出值的重複（碰撞）。哈希函數通過生成理想的概率分佈來提高其效率，使訪問時間接近於恆定。然而，高的表負載因子、不利的鍵集和設計不良的哈希函數可能會導致訪問時間接近於與表中項目數量成線性關係。

哈希函數可以設計成在最壞情況下也能提供最佳性能，在高表負載因子下保持良好性能，並在特殊情況下實現鍵到哈希碼的完美（無碰撞）映射。其實現基於奇偶保持位操作（如XOR和ADD）、乘法或除法。

與哈希函數配套的必要機制是碰撞解決方法，通常使用輔助數據結構（如鍊表）或系統地探測哈希表中的空槽來解決碰撞問題。

哈希函數的應用

由於哈希函數的應用的多樣性，它們經常是專為某一應用而設計的。例如，加密哈希函數假設存在一個要找到具有相同哈希值的原始輸入的敵人。一個設計優秀的加密哈希函數是一個「單向」操作：對於給定的哈希值，沒有實用的方法可以計算出一個原始輸入，也就是說很難偽造。為加密哈希為目的設計的函數，如SHA-2，被廣泛的用作檢驗哈希函數。這樣軟件下載的時候，就會對照驗證代碼之後才下載正確的文件部分。此代碼不會因為環境因素的變化，如機器配置或者IP位址的改變而有變動。以保證源文件的安全性。

錯誤監測和修複函數主要用於辨別數據被隨機的過程所擾亂的事例。當哈希函數被用於校驗和的時候，可以用相對較短(但不能短於某個安全參數, 通常不能短於160位)的哈希值來驗證任意長度的數據是否被更改過。

保護資料

哈希值可用於唯一地識別機密信息。這需要哈希函數是抗碰撞(collision-resistant)的，意味着很難找到產生相同哈希值的資料。哈希函數分類為密碼哈希函數和可證明的安全哈希函數。第二類中的函數最安全，但對於大多數實際目的而言也太慢。透過生成非常大的哈希值來部分地實現抗碰撞。例如，SHA-256是最廣泛使用的密碼哈希函數之一，它生成256比特值的哈希值。

確保傳遞真實的信息

消息或數據的接受者確認消息是否被篡改的性質叫數據的真實性，也稱為完整性。發信人通過將原消息和哈希值一起發送，可以保證真實性。

哈希表

哈希表是哈希函數的一個主要應用，使用哈希表能夠快速的按照關鍵字查找數據記錄。（注意：關鍵字不是像在加密中所使用的那樣是秘密的，但它們都是用來「解鎖」或者訪問數據的。）例如，在英語字典中的關鍵字是英文單詞，和它們相關的記錄包含這些單詞的定義。在這種情況下，哈希函數必須把按照字母順序排列的字符串映射到為哈希表的內部數組所建立的索引上。

哈希表哈希函數的幾乎不可能/不切實際的理想是把每個關鍵字映射到唯一的索引上（參考完美哈希），因為這樣能夠保證直接訪問表中的每一個數據。

一個好的哈希函數（包括大多數加密哈希函數）具有均勻的真正隨機輸出，因而平均只需要一兩次探測（依賴於裝填因子）就能找到目標。同樣重要的是，隨機哈希函數不太會出現非常高的衝突率。但是，少量的可以估計的衝突在實際狀況下是不可避免的（參考生日悖論或鴿洞原理）。

• 鏈式哈希：每個槽是一個鍊表或鏈的頭部，碰撞的項會被添加到鏈中。鍊表可以保持隨機順序併線性搜索，或按順序排列，或者按訪問頻率自排序以加速訪問。
• 開放地址哈希：從已佔用的槽開始以指定方式探測表，通常採用線性探測、二次探測或雙重哈希，直到找到一個空槽或探測完整個表（溢出）。搜索數據項時遵循相同的程序，直到找到目標項、找到空槽或探測完整個表（數據項不在表中）。

在很多情況下，heuristic哈希函數所產生的衝突比隨機哈希函數少的多。Heuristic函數利用了相似關鍵字的相似性。例如，可以設計一個heuristic函數使得像FILE0000.CHK, FILE0001.CHK, FILE0002.CHK，等等這樣的文件名映射到表的連續指針上，也就是說這樣的序列不會發生衝突。相比之下，對於一組好的關鍵字性能出色的隨機哈希函數，對於一組壞的關鍵字經常性能很差，這種壞的關鍵字會自然產生而不僅僅在攻擊中才出現。性能不佳的哈希函數表意味着查找操作會退化為費時的線性搜索。

錯誤校正

使用一個哈希函數可以很直觀的檢測出數據在傳輸時發生的錯誤。在數據的發送方，對將要發送的數據應用哈希函數，並將計算的結果同原始數據一同發送。在數據的接收方，同樣的哈希函數被再一次應用到接收到的數據上，如果兩次哈希函數計算出來的結果不一致，那麼就說明數據在傳輸的過程中某些地方有錯誤了。這就叫做冗餘校驗。

校正錯誤時，至少會對可能出現的擾動大致假定一個分佈模式。對於一個信息串的微擾可以被分為兩類，大的（不可能的）錯誤和小的（可能的）錯誤。我們對於第二類錯誤重新定義如下，假如給定H（x）和x+s，那麼只要s足夠小，我們就能有效的計算出x。那樣的哈希函數被稱作錯誤校正編碼。這些錯誤校正編碼有兩個重要的分類：循環冗餘校驗和里德-所羅門碼。

語音識別

對於像從一個已知列表中匹配一個MP3文件這樣的應用，一種可能的方案是使用傳統的哈希函數——例如MD5，但是這種方案會對時間平移、CD讀取錯誤、不同的音頻壓縮算法或者音量調整的實現機制等情況非常敏感。使用一些類似於MD5的方法有利於迅速找到那些嚴格相同（從音頻文件的二進制數據來看）的音頻文件，但是要找到全部相同（從音頻文件的內容來看）的音頻文件就需要使用其他更高級的算法了。

那些並不緊隨IT工業潮流的人往往能反其道而行之，對於那些微小差異足夠健壯的哈希函數確實存在。現存的絕大多數哈希算法都是不夠健壯的，但是有少數哈希算法能夠達到辨別從嘈雜房間裏的揚聲器里播放出來的音樂的健壯性。有一個實際的例子是Shazam[1] （頁面存檔備份，存於互聯網檔案館） 服務。用戶可以用手機打開其app，並將話筒靠近用於播放音樂的揚聲器。該項服務會分析正在播放的音樂，並將它於存儲在數據庫中的已知的哈希值進行比較。用戶就能夠收到被識別的音樂的曲名。

專門用途

• 緩存：哈希函數還用於為存儲在慢速介質上的大型數據集構建緩存。緩存通常比哈希搜索表更簡單，因為任何碰撞都可以通過丟棄或回寫較舊的衝突項來解決。
• 布隆過濾器：哈希函數是布隆過濾器的核心組成部分，布隆過濾器是一種空間高效的概率數據結構，用於測試某個元素是否是集合的成員。
• 幾何哈希（或網格方法）：這是哈希的一種特殊情況。在這些應用中，所有輸入組成一個度量空間，而哈希函數可被解釋為將該空間劃分為一個網格單元。哈希表通常是一個具有兩個或多個索引的數組（稱為網格文件、網格索引、桶網格等），哈希函數返回一個索引元組。這一原理廣泛用於計算機圖形學、計算幾何學以及許多其他學科，用於解決平面或三維空間中的鄰近問題，例如在點集間查找最近點對、在形狀列表中尋找相似形狀、在圖像數據庫中查找相似圖像等。
• 關聯數組與動態集合：哈希表還用於實現關聯數組和動態集合。

目前常見的哈希算法

算法名稱	輸出大小(bits)	內部大小	區塊大小	長度大小	字符尺寸	碰撞情形
HAVAL	256/224/192/160/128	256	1024	64	32	是
MD2	128	384	128	No	8	大多數
MD4	128	128	512	64	32	是
MD5	128	128	512	64	32	是
PANAMA	256	8736	256	否	32	是
RadioGatún	任意長度	58字	3字	否	1-64	否
RIPEMD	128	128	512	64	32	是
RIPEMD-128/256	128/256	128/256	512	64	32	否
RIPEMD-160/320	160/320	160/320	512	64	32	否
SHA-0	160	160	512	64	32	是
SHA-1	160	160	512	64	32	有缺陷
SHA-256/224	256/224	256	512	64	32	否
SHA-512/384	512/384	512	1024	128	64	否
Tiger（2）-192/160/128	192/160/128	192	512	64	64	否
WHIRLPOOL	512	512	512	256	8	否

Rabin-Karp字符串搜索算法

Rabin-Karp字符串搜索算法是一個相對快速的字符串搜索算法，它所需要的平均搜索時間是O(n)。這個算法是建立在使用哈希來比較字符串的基礎上的。