c++ - 使用异或和移位的字符串哈希算法

Question

我得到了这个算法来编写一个哈希函数:

BEGIN Hash (string)
UNSIGNED INTEGER key = 0;
FOR_EACH character IN string
key = ((key << 5) + key) ^ character;
END FOR_EACH
RETURN key;
END Hash

<<运算符指的是向左移动位。 ^指的是异或运算，字符指的是字符的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 到 n−1 的范围内，只需使用 % 对 n 取模即可。运算符(operator):

unsigned int hash = key % n;

(很明显，您编写的代码不能返回“从 0 到 n 的哈希值”，因为 n 没有出现在您的代码中的任何位置。)

事实上，有一个很好的理由不过早地减少散列值模n:如果你需要增加你的散列，存储未减少的散列码当 n 发生变化时，您的字符串可以让您省去重新计算它们的工作。

最后，关于您的哈希函数的一些一般说明:

• 正如 Joachim Pileborg 上面评论的那样，明确的 (int) Actor 是不必要的。如果为了清楚起见，你想保留它，它真的应该说 (unsigned int)匹配 key 的类型，因为这就是实际转换成的值。

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

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

• 正在初始化 key为零意味着您的哈希值不受字符串中任何前导零字节的影响。 original version由于 Dan Bernstein，您的哈希函数使用(或多或少随机的)初始值 5381 代替。