BKDRHash入門

DKDRHash函數介紹

DKBRHash函數非常簡單，我們隻需要清楚基本原理就可以解決很多問題，當然不能避免所有的沖突，下圖有大佬做的性能測試可知BKDDRHash函數的性能可見一斑。下面通過最簡單的例子說明問題。

舉例介紹

假設有如下字元串“abcd”，我們所做的就是尋找一個整數 i ，通過i可以直接通路到字元串，就好比數組一樣，但是要保證這個 i 盡可能沒有沖突，就是其他的字元串轉換的 下标 盡可能不等于 i 。BDKDRHash 就能保證這個盡可能，具體推到可以參考最後面的連結。

a

b

c

d

首先我們定一個 素數 seed (常見 31,313,3131,3131313 等等) ，則 hash值就等于 每一個字元的Ascll碼乘以seed的n次方 累加 之後再對哈希數組大小取餘得到餘數就是hash值，n就是位數。

例如上面字元hash值為   key=(a*

)+（b*

）+(c*

)+(d*

) % size  把 abcd分别換成對應的Ascll碼（97,98,99,100），size 就是hash數組的大小。

貼一段打比賽用的到的代碼：

unsigned int BKDRHash(char* str)
{	
	unsigned int seed = 31;    // 31 131 1313 13131 131313 etc.. 37

	unsigned int key = 0;

	while (*str)
	{
		key = key * seed + (*str++);
	}

	return ( key & 0x7fffffff ) % Size;
}
           

好了因為有前人種樹，就直接偷懶給連結了。詳細推導與介紹參考：

https://blog.csdn.net/wanglx_/article/details/40400693

感謝大佬分享！如有錯誤還請多多指正！