哈希的数字折叠算法 Table

Question

我正在学习有关数据结构的书。
我正在阅读哈希 table 章节，在数字折叠部分，它显示了哈希算法。

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

但是有一个问题。如果散列的大小table是12289，字符串的最大长度是10位，散列函数returns10X127=1270，它returns只是0到1270之间的地址，所以 1271 和 12288 之间的地址根本没有被使用。

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

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

Answer 1

我不确定你的代码是复制的还是乱写的，但目前你的代码不是哈希码，而只是最后一个 ascii 码的传递函数。我猜你是想对这些值进行异或运算？
不太清楚你建议的函数是什么，所以你应该澄清一下，但是，如果你只是对基于文本的数据进行异或运算，那么你的哈希函数就不是很好。假设您的数据结果只是偶数位？ ASCII 中还有其他退化。我假设 hashValue ^= key [i]
你不应该向右（或向左）移动，因为你丢失了位。假设您对 hashValue 的右 7 位进行异或并向右移动。您的哈希值只包含您刚刚添加的值的右 4 位！如果您向左移动会花费更长的时间，但同样如此。您在散列值的一端丢弃了一些位。您应该检查一个好的散列函数。维基百科是你的朋友 (https://en.wikipedia.org/wiki/Hash_function)
就退化值而言，加法稍微好一些，但它仍然会创建一个不统一的散列（在大多数数据下，中间部分比末端填充更多）。

哈希的数字折叠算法 Table

Digit Folding Algorithm for Hash Table

c

hashtable

data-structures