可扩展哈希 - 最高有效位

Question

我想编写可扩展哈希。在wiki上，我找到了一个很好的Python实现。但是这段代码使用了最低有效位，因此当我对d = 1进行哈希1101时，值为1，而对于d = 2，值为01。我想使用最高有效位。例如：哈希1101，d = 1值为1，d = 2值为11。有没有简单的方法可以做到这一点？我尝试过，但无法做到。

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

多多少少懂一些。这使我们在使用数组时更加高效。好的，所以对于哈希函数，我想从左到右使用4字节整数中的四个最低位。

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

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

- user1941524

---

你说你已经尝试过了 - 发布代码，这样我们就可以看到你哪里出错了。 - Gareth Latty

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

当你说你想要最重要的位时，你是想将其限制在特定大小的整数上，还是顶部非零位上？例如，8位数字15（又名00001111）的最重要的四位是0000还是1111？前者很容易计算，后者则不太容易（可能需要一个log）。 - Blckknght

“but from left to right”和“least bits”是什么意思？什么是GD？为什么你关心使用某些四位比其他四位更多？如果你的哈希函数很好，它实际上就是一个随机数，无论你选择哪四位，它仍然是一个随机数。 - Phil Frost

Answer 1

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

这是使用最高有效位计算哈希的实现（用C编写）。由于没有直接方法可以知道最高有效位，因此需要重复测试剩余值是否仅具有指定数量的位。

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

我建议使用重叠哈希(overlapping hash)，它利用数字的所有位。基本上，它将数字分成相等位数的部分并对它们进行异或(XOR)运算。它比最低有效哈希慢，但比重要哈希快。最重要的是，它比其他两种方法提供更好的离散度，使其成为一个更好的选择，当必须哈希的数字具有某种与位相关的模式时。

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;
}

- Spatarel