hash演算法的數學原理是什麼，如何保證儘可能少的碰撞？

01-06

我把問題具體一點，首先理論上針對某類數據存在對應的hash函數使得完美的無碰撞，我們先以最平凡的字元串為例，目前業界幾個常用的字元串hash函數
這些函數中我們選擇BKDRHash函數作為例子，他是KR提出的hash函數。
/* BKDR Hash Function */ unsigned int BKDR_hash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash 0x7FFFFFFF); }

注釋中可以把種子定義為131、31、1313類似的，他的碰撞率都非常低，我非常想明白其中的數學原理，或者如何按照這個hash函數推演隨即情況下字元串碰撞的概率，謝謝。

原表達式實際上是

$hash = (sum_n a[n] s^n) mod 2^{31}$

a是str，s是seed。

這個哈希函數的好壞首先取決於 $s^n mod 2^{31}$ 這個序列的循環周期，如果周期很短的話，周期之後的字元就會乘以和前面的某個對應字元相同的係數，這樣很容易產生碰撞。當s是奇數的時候，s與 $2^{31}$ 互質，考慮序列 $s, 3s, 5s, 7s, ..., (2^{31} - 1)s$ ，這其中任意兩個數的差都至多是 $2^{31} - 2$ 倍的s，而s與 $2^{31}$ 互質，因此序列中任意兩個數對 $2^{31}$ 取模後不相等。一共有 $2^{30}$ 個不同的結果，而這些結果都是奇數，因此必然與 $1,3,5,...,2^{31} - 1$ 一一對應。我們把所有的數相乘，由於係數都是奇數，因此係數的乘積與 $2^{31}$ 互質，消去係數就得到：

$s^{2^{30}} equiv 1 pmod {2^{31}}$

說明周期至多是 $2^{30}$ 然而還沒有這麼簡單，考慮 $s^{2k}$ 形式的數，它是 $s^k$ 的平方。由於

$(2^{30} + m)^2 = 2^{60} + 2^{31}m + m^2 equiv m^2 pmod {2^{31}}$

$(2^{30} - m)^2 = 2^{60} - 2^{31}m + m^2 equiv m^2 pmod {2^{31}}$

因此

$s^2, s^4 , s^6, ..., s^{2^{30}}$

最多只有 $2^{28}$ 個不同的可能結果，因此其中至少有兩個數是同餘的，說明周期小於 $2^{30}$ ，而且是它的因子，所以周期最多是 $2^{29}$

$s^{2^{29}} equiv 1 pmod {2^{31}}$

所以我們可以認為這個hash函數足夠好的條件是：

s是奇數
$s^{2^{28}} e 1 pmod {2^{31}}$

不是所有的奇數都滿足第二條，但是131是滿足的。至於後面備選的那些，我也不明白為什麼跟1和3過不去，實際上1313並不滿足第二條，而滿足的也不一定跟13有多大關係，比如說267也是滿足的。其中是不是有什麼深刻的道理在我就不是很清楚了。

我來解釋一下為什麼s一般取值為131，使用為前面的字元串數組a[n]中，取得的字元的為ascii碼，數值&<=127，為了儘可能保證獲取的hash值的唯一性，因此需要讓s為一個大於127的質數，而為了提高散列密度，又要使s儘可能小，因此，大於127的最小質數，就是131。這個值具有最佳的散列質量和散列密度。知乎首次認真回答，望多多給贊

hash相當與把值映射到另外一個空間。

第一個答案這一句話很對，說到了要點。

再詳細一點，hash函數相當於，把原空間的一個數據集映射到另外一個空間。

所以說理論上的完美無碰撞需要映射到的空間不小於原空間。但實踐中是不會這麼去做。

因為用hash函數的目的就是把原空間的數據映射到一個更小的空間，以方便處理。

如何減少碰撞概率，我覺得應該可以從三個方面考慮的：

1、增大映射空間/原空間的大小

這個很明顯，映射空間/原空間 的比值大，碰撞的概率就可能小了。前面我們也提到過，當這個比值大於等於1時，就可以實現無碰撞。

2、儘可能把原數據集均勻映射到較小空間

簡單舉個例子說明。比如有10個數，映射到5個位置。

如果每個位置均勻對應2個數，那麼任意選2個數，碰撞概率為0.2.

如果1個位置對應6個數，其餘4個位置各對應1個數，那麼任意選兩個數，碰撞概率為0.36.

3、結合原空間數據的數據特徵

我們在處理原空間的數據集時，數據集一般都會有特徵，而且不會是原空間的全集。換句話說，我們要處理的數據一般只會是原空間所有數據的一部分，而且數據集有一定特徵（數據元素出現的概率的不同）。

一般哈希函數用質數取模這就是為了使得有特徵的數據集也能均勻映射到映射空間。

在這種情況下，有時hash函數還要結合數據特徵，讓出現概率較大的數據集有較小的碰撞概率，出現概率較小的數據集有較大的碰撞概率。這樣，就可以減少整體數據集的碰撞概率。

hash函數的設計應該主要考慮了後面兩點。

hash相當與把值映射到另外一個空間（函數的本質也即映射），因為可以選擇比較好的hash函數，使得這種映射具備良好的隨機性，使得碰撞概率得以控制得很好。

在一個隨機性良好的hash函數的情況下，hash模型基本和以下問題一致：

把k個球隨機放入n個盒子，碰撞次數定義為有球的總數k減去有球的盒的個數（當然，不同存儲結構有所不同）。

碰撞的概率還跟當前空間中已經被映射的點的數量有關，存入hash的元素越多，碰撞概率就越大。給定k個球，隨機放入n個盒子，在相同盒子裡面的球的期望個數也會增大。

PS：以上說的隨機性，指的是它可以把有序的值完全打亂，就混亂程度來說，看起來和隨機無異。但是映射本身是確定的（都說了是映射了，還能不確定么），但是一般情況下映射是不可逆的。

簡單對BKDR做一個補充，我們不妨遞歸的看待這個hash函數，h = (h" * s + c) % m。

我們著重分析這個hash函數的值空間大小（畢竟在均勻的條件下，值空間越大，碰撞就越難）。考慮到c是一個隨機的加項，它並不改變h的空間大小，我們主要考慮的就是h" * s % m的空間大小，如果s和m互質，那麼可以知道h至少可以和h"一樣大，之多覆蓋整個m大小的空間（因為s不包含任何除1以外的m的因子，h * s % m的循環節只能是m）。也就是說，只要s和m互質，映射空間的大小就不會隨著字元串長度的增加而減小。

當然，s和m互素只是保證了如果h能夠覆蓋完整的空間m，那麼字元的增多，不會導致空間的退化。h能否覆蓋整個空間，還取決於c。c的分布對h的影響是很大的，試想一下，如果ascii字符集裡面，所有可列印字元都是偶數，那h的空間必然至多是m/2了，平白少了一半。

單個字元的空間大小是|c|，我們可以把這個空間不斷的作用s，看看他能不能很好的覆蓋。

而很多人提到s的高次冪，我並不覺得這是一個很重要的因素。最最重要的因素是|c|在s的作用下的對h的覆蓋，這個覆蓋越均勻越好（即便c的分布不是均勻的），並不需要2^30次這麼高的冪。最好的辦法，就是用程序蠻力跑一個s出來，使得它在常用的文本上碰撞率最小。

均勻性以外還要有不可預測性，不然就直接取末n位就行了

在@靈劍大蝦的答案基礎上做一些補充和說明，方便像我一樣的同餘苦手理解（之前花了一個上午都沒有看懂 $S^{2^{30}}equiv1[mod 2^{31}]$ 是怎麼來的。。。）