哈希函数可以避免固定输入集上的冲突

Question

我有一个大小为 ~2³⁸ 的空间，我从中采样了一组 ~2³⁰ 不同的对象（它们的分布是结构化的，但很难表征）。我的目标是构建一个将这些对象转换为 32 位整数的函数，这样相对于在整个空间上具有抗冲突性的哈希函数（例如 FNV 或 CRC），该固定集上的冲突要少得多。是否有任何一类函数可以实现这种行为，即它们在域的结构化子集上有许多冲突，但分散在其他地方？

在这种情况下，最常见的方法似乎是使用进化/强化学习算法，将输入视为数据集并优化哈希函数。但对于我的应用程序，如果有一种原则性的方法可以提出一系列有前途的此类函数，我宁愿简单地检查大量候选函数。

Answer 1

这可能不是您想要做的，但如果是的话，我想我会分享这个想法。

静态数据的模拟完美哈希表。

如果你的数据永远不会改变，那么你所需要的只是一个单射函数。

让 D_i 代表你的第 i 个对象，其中 i >= 0

选择一个哈希函数 H：D -> Z1, H(D_i) = H_i 其中 0 <= H_i < 2^32.

对于任意哈希函数，如果 imax 大约为 10,000 到 100,000 次冲突，则可能会发生 10,000 到 100,000 次冲突。 = 2^30.

选择一个值，例如COLLISION_VALUE = 2^32 - 1，表示碰撞。

选择另一个哈希函数 J：D -> Z2, J(D_i) = J_i 其中 0 <= J_i < 2^32 such that there does not exist a single collision with H(). This means that

对于所有0<=i<=imax, J(D_i) != H(D_i).

这应该很容易实现，因为碰撞的概率约为 (2^15)^2/(2^32) = 1/4。 Z1和Z2当然是不同的数组。 （是的，Z2 非常稀疏）。

那么你只需要使用，...

Z1[H(D_i)] 如果 H(D_i) != COLLISION_VALUE

Z2[J(D_i)] 否则。