作为散列表的散列函数是否足够好作为散列表C

对于使用探测（开放寻址）进行冲突解决的散列表（实际上是散列集），我需要一个尽可能高效的散列函数。存储在表中的条目都是4个字节的整数，它们在该范围内具有随机值。作为散列表的散列函数是否足够好作为散列表C

我正在考虑的东西甚至快于djb2，像

value mod LARGE_PRIME

然后用我的桶大小再次国防部它。我想这个素数必然大于我的桶大小，这意味着我也有一些理智限制我的桌子有多大（它可能永远不会超过256个条目）。

我不需要散列函数的任何密码学方面 - 只要它不是非常容易碰撞，它应该可以正常工作。

这是否会构成一个很好的散列函数？每次调整大小以改进散列表容量时，我可以为散列表容量定义特定算法吗？

“LARGE_PRIME”是什么意思？对于小于'LARGE_PRIME'的所有值，'value mod LARGE_PRIME'是'value'。 –

好问题。我估计我的表不会超过256个条目，所以我认为一些总数在1000左右。编辑的问题。 –

“采用随机值” - “随机”意味着您不需要散列或素数，而且“尽可能高效”可能或可能不够严格，以至于无法照顾，但是可以使用简单的按位“与”一个更大的随机值进入2次幂的桶的计数比mod操作更有效（当桶计数直到运行时才知道）。 –

正确的散列函数归结为您正在散列的数据：您的值的随机程度如何？如果你的价值观是在范围内均匀分布，且范围比散列桶的数量大得多，然后只用

value MOD number_of_buckets

将是一个合理的哈希函数 - 在MOD <prime>增加实际上不会给你很很多，事实上很可能会使哈希更糟糕（因为有些桶会比其他桶已经不足或过度使用）。它们有时可以用来“平滑”由于常见因素造成的相关效应，但如果你没有这些相关性，那么没有它们，你可能会更好 - 尤其是速度至关重要！

2015-05-13 09:27:37 psmears

嗯好点！我想我有点担心如何使用2^n个桶可能会使它更容易碰撞。我发现现在并不重要，如果我的输入是真正随机的！ –

回答