python - 可扩展散列 - 最高有效位

Question

我想编写可扩展哈希。在 wiki我在 python 中找到了很好的实现。但是这段代码使用了最低有效位，所以当我有散列 1101 时 d = 1 值是 1 而 d = 2 值为 01。我想使用最高有效位。例如:哈希 1101，d = 1 值为 1，d = 2 值为 11 。有没有简单的方法可以做到这一点？我试过了，但我做不到。

Do you understand why it uses the least significant bits?

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

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

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

Answer 1

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

这是使用最高有效位的散列的实现(在 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;
}