首页 文章

为什么使用2的幂作为散列大小会使哈希表比使用素数更糟糕？

提问于
浏览 次
0

我正在实现一个应该存储32位值对的哈希表 . 考虑到我的元素是固定大小，我使用一个非常简单的散列函数：

hash(a,b) = asUint64(a) + (asUint64(b) << 32)

有了它，我得到一个哈希表中的元素索引（即它对应的桶）：

index(a,b) = hash(a,b) % hash_size

其中hash_size是我表上的条目/桶数 . 我已经意识到，如果我用bitwise mod of 2替换"modulus"运算符，将hash_size固定为2的幂，我可以加快这个实现. Except, when I do that, most of my pairs end up on the first bucket! 为什么会发生这种情况？

math hash language-agnostic hashtable bit-manipulation

1 回答

  • 2

    我的猜测是你的数据在 a 中没有均匀分布 . 考虑将 a 和 b 连接为您的哈希码：

    b31b30...b1b0a31a30...a1a0, where ai, bi is the ith bit of a,b

    假设您有一个包含一百万个条目的表，那么您的哈希索引就是

    a9a8...a1a0 (as an integer)

    更糟糕的是，假设 a 的范围从1到100.然后您对 a 的高阶位的依赖性更小 .

    如您所见，如果您的哈希表没有至少40亿个条目，则您的哈希码根本不依赖于b，并且 hash(x, a) 将与所有 x 发生冲突 .

    回复于

相关问题