定義

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

假設(shè)我們已經(jīng)定義了一個(gè) hash 函數(shù)名為 H，輸入內(nèi)容為 message，輸出內(nèi)容為 x，那么就有如下公式。

H(message) = x

這是一個(gè)壓縮的過(guò)程，通常情況下，我們會(huì)把輸出值稱之為 hash 值。

接下來(lái)通過(guò)一個(gè)具體的案例來(lái)了解 hash 的過(guò)程。

我們定義這樣一個(gè)場(chǎng)景，約定任意正整數(shù)，要存放在長(zhǎng)度為 6 的數(shù)組中，那么此時(shí)，我們可以利用 hash 的思想設(shè)計(jì)什么樣的方案來(lái)做到這個(gè)事情呢？

數(shù)組的具體位置我們可以用下標(biāo)來(lái)表示 0, 1, 2, 3, 4, 5。想要將任意正整數(shù)放入到數(shù)組中，那么我們只需要設(shè)計(jì)一個(gè)函數(shù)，輸入值為任意正整數(shù)，輸出值為該數(shù)組下標(biāo)中的任意一個(gè)即可，得到了輸出值，我們就相當(dāng)于知道應(yīng)該把輸入值放到數(shù)組中的某個(gè)位置了。

我們可以使用求余法來(lái)定義這個(gè) hash 函數(shù)。

function suplus(number) {
  return number % 6
}

于是，隨便取幾個(gè)數(shù)，得到 hash 值之后就能存入數(shù)組對(duì)應(yīng)的位置。

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

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

此時(shí)的哈希值表示的是數(shù)組的下標(biāo)，因此在很多應(yīng)用場(chǎng)景，輸出結(jié)果哈希值也被稱為哈希地址。

哈希碰撞

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

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

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

解決哈希碰撞的方法很多，這里介紹一個(gè)比較常見(jiàn)的方法：以數(shù)組的每個(gè)地址為根節(jié)點(diǎn)，構(gòu)建一個(gè)新的鏈表。

例如當(dāng)輸入數(shù)字分別為 7, 61 時(shí)。

但是當(dāng)數(shù)據(jù)量龐大時(shí)，鏈表的查詢速度比較低效，因此我們?cè)趯?shí)踐中，會(huì)將鏈表替換成紅黑樹等操作效率更高的數(shù)據(jù)結(jié)構(gòu)。

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

現(xiàn)在 md5 已經(jīng)可以人為制造 hash 碰撞，因此實(shí)用性大大降低。

本文轉(zhuǎn)載自微信公眾號(hào)「這波能反殺」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系這波能反殺公眾號(hào)。