天天看點

BKDRHash入門

DKDRHash函數介紹

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

BKDRHash入門

舉例介紹

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

a b c d

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

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

BKDRHash入門

)+(b*

BKDRHash入門

)+(c*

BKDRHash入門

)+(d*

BKDRHash入門

) % 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

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