使用XOR和位移的字符串的哈希算法

Question

我被赋予这个算法来编写一个哈希函数:

BEGIN Hash(string)
UNSIGNED INTEGER key = 0;
FOR_EACH字符IN字符串
键=((键<< 5)+键)^字符;
END FOR_EACH
RETURN键;
结束哈希

的<<操作者参照位左移.在^指异或运算和性质是指该字符的ASCII值.看起来非常简单.

以下是我的代码

unsigned int key = 0;
for (int i = 0; i < data.length(); i++) {
    key = ((key<<5) + key) ^ (int)data[i];
}
return key;

但是,当我实际上从0开始得到一个哈希值时,我一直变得荒谬的正面和负面的巨大数字n.n是用户事先设定的值.我不确定哪里出了问题,但我认为这可能是XOR操作.

任何建议或意见将不胜感激.谢谢!

Answer 1

此代码的输出是32位(或64位或宽unsigned int)无符号整数.将其限制到范围从0到Ñ -1,简单地减小它模Ñ,使用%运算符:

unsigned int hash = key % n;

(显而易见的是,您编写的代码无法返回"0 - 的哈希值n",因为n代码中的任何位置都不会出现.)

事实上,有一个很好的理由不降低哈希值模ñ太快:如果你需要增加你的哈希值,存储你的字符串的未还原的散列码为您节省重新计算,只要他们的努力ñ变化.

最后,关于哈希函数的一些一般注意事项:

• 正如Joachim Pileborg上面所述,明确的(int)演员阵容是不必要的.如果你想保持它的清晰度,它应该说(unsigned int)匹配的类型key,因为这是实际转换成的值.

• 对于无符号整数类型,((key<<5) + key)等于33 * key(因为左移5位与乘以2 ⁵ = 32相同).在现代CPU上,使用乘法几乎肯定更快; 在具有慢速乘法的旧或非常低端的处理器上,任何体面的编译器都可能会将乘法乘以常数优化为移位和加法的组合.因此,无论哪种方式,将操作表示为乘法都是IMO更可取的.

• 您不希望调用data.length()循环的每次迭代.在循环之前调用它一次并将结果存储在变量中.

• 初始化key为零意味着您的哈希值不受字符串中任何前导零字节的影响.由于Dan Bernstein,哈希函数的原始版本使用(或多或少随机)初始值5381.