algorithm - 在固定长度的输入上证明完美的哈希函数

Question

我已经在这里看到了使用 gperf 的答案，但是，我更愿意根据我为strings具有固定长度的域创建的证明来推出自己的证明。<= 200 基于我从 wolfram 获得的计算，我得到了~7.9 x 10^374总排列。因此，我的思路是，如果我有2048一点哈希函数 ( 3.2 x 10^616)，我应该能够处理我需要处理的整个字符串世界。我的问题是，在所有长度为 200 或更短的字符串的宇宙的约束下，我如何证明我最终生成的哈希实现将是完美的？

Answer 1

长度为 200 个字符的字符串只有 200 * 8 = 1600 位。如果 2048 位散列适合您的目的，您可以只使用字符串位作为完美散列。身份哈希函数是完美的，因为它将每个输入映射到不同的哈希值（显然，因为没有映射）。