具有已知最大项数和固定密钥大小的高效固定大小“有损”哈希表

鉴于我将始终有一个128位整数作为关键字和最大数量的元素，是否有可能做一个完美的哈希函数？具有已知最大项数和固定密钥大小的高效固定大小“有损”哈希表

我想存储GUID作为键，我想要一个固定大小的无链表解决方案。那就是如果有碰撞，我会失去第二个元素。

有人可以推荐一个哈希函数来做到这一点吗？

这些GUID是在本地生成的吗？在这种情况下，实际上每个GUID只有一小部分会有所不同 - 我忘记了详细信息，但您可能需要查看由哪些GUID组成的部分，并且只使用最可能不同的部分。 –

事实证明，已经讨论过GUID上的散列[这里]（http://stackoverflow.com/questions/7326593/guid-gethashcode-uniqueness）。 –

@ 500-InternalServerError实际上，大多数现代GUID算法几乎都是随机位，而不是旧的机制，其中大约一半是基于硬件密钥，一半是时间戳。 – Servy

鉴于我将始终有一个128位整数作为一个关键和最大数量的元素，是否有可能做出完美的散列函数？

如果熵关键的（预期的信息包含在变量值）是比散列的结果可以容纳更大的 - 答案是否定的。如果密钥的熵等于或低于散列结果可以容纳的值 - 答案是肯定的。

意思是说，如果你的散列函数例如产生了一个16位的结果（65536个可能的值），而你的128个关键变量可以假设至多有65536个或更少的不同值（所以128位密钥的熵最多10位）比存在这种散列函数。另一方面，如果您的密钥可以承担超过65535个不同值，那么您无法将其散列到65535或更少的存储桶中。

有人可以推荐一个哈希函数来做到这一点吗？

不知道什么样的可能的值可以假设没有人可以给你一个哈希函数，即使你知道关键熵太低以至于它可以完成，也可以做到这一点。

2013-01-23 10:38:43 RoBiK

回答