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
感謝大佬分享!如有錯誤還請多多指正!