c# - 具有已知最大项目数和固定键大小的高效固定大小“有损”哈希表

Question

考虑到我总是有一个 128 位整数作为键和最大数量的元素，是否有可能制作一个完美的散列函数？

我想将 guid 存储为键，并且我想要一个固定大小的无链表解决方案。也就是说，如果发生碰撞，我会失去第二个元素。

有人可以推荐一个可以做到这一点的散列函数吗？

Answer 1

考虑到我总是有一个 128 位整数作为键和最大数量的元素，是否有可能制作一个完美的散列函数？

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

这意味着，如果您的散列函数例如生成 16 位结果（65536 个可能值）并且您的 128 个键变量可以假设最多 65536 个或更少的不同值（因此 128 位键的熵最多为 10 -bits) 比存在这样的散列函数。另一方面，如果您的密钥可以假设超过 65535 个不同的值，则无法将其散列到 65535 个或更少的存储桶中。

有人可以推荐一个可以做到这一点的散列函数吗？

在不知道密钥的可能值的情况下，即使您知道密钥熵如此之低以至于可以完成这一事实，也没有人可以为您提供可以做到这一点的散列函数。