3

我想写可扩展的散列。在wiki上，我在 python 中找到了很好的实现。但是这段代码使用了最低有效位，所以当我有value is和 for 1101value is的哈希值时。我想使用最高有效位。例如： hash , value is , value is 。有什么简单的方法可以做到这一点吗？我试过了，但我做不到。d = 11d = 2011101d = 11d = 211

你明白为什么它使用最低有效位吗？

或多或少。当我们使用数组时，它会变得高效。好的，所以对于哈希函数，我想使用 4 字节整数中的四个最小位，但从左到右。

h = hash(k) 
h = h & 0xf #use mask to get four least bits
p = self.pp[ h >> ( 4 - GD)]

它不起作用，我不知道为什么。

4

1 回答 1

2

使用最低有效位计算散列是计算散列的最快方法，因为它只需要 AND 位运算。这使它非常受欢迎。

这是使用最高有效位的哈希的实现（在 C 中）。由于没有直接的方法可以知道最高有效位，因此它反复测试剩余值是否只有指定数量的位。

int significantHash(int value, int bits) {
    int mask = (1 << bits) - 1;
    while (value > mask) {
        value >>= 1;
    }
    return value;
}

我推荐使用数字的所有位的重叠哈希。从本质上讲，它减少了相同位数的部分数量并对它们进行异或。它比最不重要的散列运行得慢，但比重要的散列快。最重要的是，它提供了比其他两种方法更好的分散性，当必须散列的数字具有某种与位相关的模式时，它成为更好的候选者。

int overlappingHash(int value, int bits) {
    int mask = (1 << bits) - 1;
    int answer = 0;
    do {
        answer ^= (value & mask);
        value >>= bits;
    } while (value > 0);
    return answer;
}
于 2013-02-01T18:38:37.403 回答