字符串hash算法的一个问题
《The C Programming Language》的BKDRHash是一种简单快捷的hash算法
template<class T>
size_t BKDRHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..
}
return hash;
}
我的问题是,这个简单的式子hash=hash*131+ch,在数学原理上为什么能区分所有的字符串?
而且,累乘因子为什么只能是31,131,1313这样的数字,别的数字不行么?
[解决办法]
以前我也想过,由于时间问题一直没深入想,现在关注一下
[解决办法]
这个得去问数学专业的。
[解决办法]
乘以31、131、1313、13131、131313.. 产生相同的哈希值的概率更小