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

感谢大佬分享！如有错误还请多多指正！