哈希函数,可避免在一组固定的输入上发生冲突

Hash functions which avoid collisions on a fixed set of inputs

提问人:cjw 提问时间:11/5/2023 最后编辑:cjw 更新时间:11/6/2023 访问量:41

问:

我有一个大小为 ~238 的空间,我从中抽取一组 ~228 个不同的对象(它们的分布是结构化的,但很难表征)。我需要一个过程来获取一个这样的样本并构造一个将每个对象转换为 32 位整数的函数,这样相对于在整个空间上具有抗冲突性的哈希函数(例如 FNV 或 CRC),这个固定样本上的冲突要少得多。是否有任何一类函数可以实现这种行为,即它们在域的结构化子集上有许多冲突,但分散在其他地方?

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

哈希 Hashmap 哈希表

评论

0赞 Jeremy Friesner 11/5/2023
可能感兴趣的:en.wikipedia.org/wiki/Perfect_hash_function
0赞 cjw 11/6/2023
是的,这很有帮助,非常感谢!
0赞 Gene 11/6/2023
有一个 gnu 工具可以构建完美的哈希值:gperf。我不知道它是如何在这么大的关键空间上工作的。还要考虑最佳二叉搜索树。他们可能在这个问题上具有竞争力。

答: 暂无答案