定義

hash 是一種把任意長度輸入變換成固定長度輸出的一種算法。

假設我們已經定義了一個 hash 函數名為 H，輸入內容為 message，輸出內容為 x，那么就有如下公式。

H(message) = x

這是一個壓縮的過程，通常情況下，我們會把輸出值稱之為 hash 值。

接下來通過一個具體的案例來了解 hash 的過程。

我們定義這樣一個場景，約定任意正整數，要存放在長度為 6 的數組中，那么此時，我們可以利用 hash 的思想設計什么樣的方案來做到這個事情呢？

數組的具體位置我們可以用下標來表示 0, 1, 2, 3, 4, 5。想要將任意正整數放入到數組中，那么我們只需要設計一個函數，輸入值為任意正整數，輸出值為該數組下標中的任意一個即可，得到了輸出值，我們就相當于知道應該把輸入值放到數組中的某個位置了。

我們可以使用求余法來定義這個 hash 函數。

function suplus(number) {
  return number % 6
}

于是，隨便取幾個數，得到 hash 值之后就能存入數組對應的位置。

// 輸入值：61
suplus(61) = 1

// 輸入值：101
suplus(101) = 5

此時的哈希值表示的是數組的下標，因此在很多應用場景，輸出結果哈希值也被稱為哈希地址。

哈希碰撞

在上面的例子中，輸入值的范圍一定大于輸出值的范圍，這是 hash 的重要特性之一。因此在某些情況下，不同的輸入會得到相同的輸出結果。

// 不同的輸入，得到了相同的輸出，哈希地址相同
suplus(7)  = 1
suplus(61) = 1

此時哈希地址相同，按照規則，我們不得不把不同的值，存入相同的位置，這種情況就被稱之為哈希碰撞（collision）。

解決哈希碰撞的方法很多，這里介紹一個比較常見的方法：以數組的每個地址為根節點，構建一個新的鏈表。

例如當輸入數字分別為 7, 61 時。

但是當數據量龐大時，鏈表的查詢速度比較低效，因此我們在實踐中，會將鏈表替換成紅黑樹等操作效率更高的數據結構。

當然，最理想的情況是輸出范圍足夠廣，不出現 hash 碰撞。因此我們實踐中使用的 hash 函數，輸出值的范圍都非常龐大，例如早期用得比較多的 md5，現在使用比較多的sha256：比特幣中使用的哈希算法。但是由于輸入值范圍一定大輸出值范圍，因此理論上哈希碰撞一定會存在。

現在 md5 已經可以人為制造 hash 碰撞，因此實用性大大降低。

本文轉載自微信公眾號「這波能反殺」，可以通過以下二維碼關注。轉載本文請聯系這波能反殺公眾號。