c - 哈希表的数字折叠算法

Question

我正在看一本关于数据结构的书。
我正在阅读哈希表章节，在数字折叠部分，它显示了哈希算法。

int Hash(char* key, int keyLength, int tableSize)
{
     int i = 0;
     int hashValue= 0;

     for(i=0; i<keyLenth; i++)
        hashValue += key[i];

     return hashValue % tableSize;
}

将字符串的每个元素替换为 ASCII 代码(0-127)，并分别添加这些值。

enter image description here

但是有一个问题。如果哈希表的大小为12289，字符串的最大长度为10位，则哈希函数返回10X127 = 1270，它只返回0到1270之间的地址，因此根本不使用1271到12288之间的地址。

哈希表的大小 12289，二进制表示为 11000000000001。总共 14 位。另一方面，1270 的最大地址值为 10011110110，因此只使用了 11 位。这一事实表明这三位从未被使用过。所以每次迭代Hash函数的循环时，我们将hashValue向左移动3位并添加下一个ASCII码。理论上这将能够散列所有地址。

我的问题是为什么要左移 3 位？我有什么理由不应该把它移到右边吗？

Answer 1

1. 我不确定你的代码是复制的还是只是乱写的，但目前你的代码不是哈希码，而只是最后一个ascii码的传递函数。我猜您的意思是对这些值进行异或？
2. 目前还不太清楚您建议的函数是什么，因此您应该澄清一下，但是，如果您只是对基于文本的数据进行异或，那么您就没有做一个非常好的哈希函数。假设你的数据只是偶数？ ASCII 还存在其他退化。 我假设 hashValue ^= key [i]
3. 您不应该向右移动(或向左移动)，因为您会丢失位。假设您对 hashValue 的右 7 位进行异或并向右移位。您的哈希值仅保存您刚刚添加的值的 4 个正确位!如果向左移动则需要更长的时间，但同样成立。您在散列值的一端丢弃了一些位。您应该检查是否有良好的哈希函数。 维基百科是你的 friend ( https://en.wikipedia.org/wiki/Hash_function )
4. 就简并值而言，加法稍好一些，但它仍然会创建不均匀的哈希(在大多数数据下，中间的填充量会比末端的填充量更多)。