c - 哈希函数中的冲突太多

Question

我试图将大约 6400 万个 64 位唯一无符号整数散列到 1.28 亿个桶（27 位宽地址）。我尝试了 Bob Jenkin 的HashLittle和Murmur哈希（这两个哈希函数都提供了 32 位哈希，我将其屏蔽以获得 27 位地址）。在这两种情况下，它导致了大约 22% 的碰撞，最终只占用了 37% 的存储桶。这是预期的还是我做错了什么？我期待更少的碰撞和更好的水桶占用。

Answer 1

它看起来比我随机预期的要差一些，使用基于http://en.wikipedia.org/wiki/Poisson_distribution的近似值。如果桶中条目的预期数量是 1/2，我预计 0 个条目的概率约为 exp(-0.5) = 0.607，而桶中有 1 个条目的概率大约是这个的一半，即 0.303。这使得一个桶有两个或更多条目的概率为 0.09。

你的整数都是唯一的吗？如果不是，您是否将重复值视为导致哈希冲突？

在有利的情况下，您可以选择一个散列函数，以便随机提供更少的冲突。有时 hash(x) = x % p，其中 p 是素数，会实现这一点。

Answer 2

如果您想获得“随机但可重复”的结果 - 即使对于故意困难的输入，它也具有最佳的最坏情况碰撞率* - 您可以简单地创建一个表格，如：

uint32_t r[8][256];

使用 8kb 的随机数据填充它 - 您可以使用 google 搜索具有随机数据的网站以下载并重新格式化它以包含在您的源中或在运行时从文件加载。

(*) - 只要输入不是由也知道您的随机数据的恶意人员创建的。

然后像这样散列：

uint32_t hash(uint64_t n)
{
    unsigned char* p = (unsigned char*)&n;
    return r[0][p[0]] ^ r[1][p[1]] ^ r[2][p[2]] ^ r[3][p[3]] ^
           r[4][p[4]] ^ r[5][p[5]] ^ r[6][p[6]] ^ r[7][p[7]];
}

当然，更好的最坏情况碰撞通常与更好的现实世界性能完全不同——很大程度上取决于你的数据集和硬件——所以如果你真的在乎，它只是作为基准测试的东西。也可以对简单的传递进行基准测试。使用质数的桶是非常好的做法，但根据您的哈希表可能会很棘手 - 例如，某些实现可能会将任何调整大小请求四舍五入到 2 的幂。