hash - 完美的哈希函数

Question

我正在尝试哈希值

10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0

我需要一个函数，将它们映射到大小为13的数组而不会引起任何冲突。

我花了好几个小时仔细考虑一下，然后谷歌搜索，无法解决。我还没有一个可行的解决方案。

我将如何寻找这种哈希函数？我玩过gperf，但是我不太了解它，因此无法获得想要的结果。

Answer 1

找到一个

我尝试了几件事，然后半手动找到了一件:

(n ^ 28) % 13

半手动部分是以下我用来测试带有一系列参数的候选函数的ruby脚本:

t = [10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0]
(1..200).each do |i|
  t2 = t.map { |e| (e ^ i) % 13 }
  puts i if t2.uniq.length == t.length
end