完美的哈希函数

Question

我正在尝试对值进行哈希处理，

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

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

我花了几个小时思考这个问题并进行谷歌搜索，但无法弄清楚。我还没有找到可行的解决方案。

我将如何找到这种哈希函数？我玩过 gperf，但我不太理解它，也无法得到我想要的结果。

Answer 1

如果您知道确切的密钥，那么生成完美的哈希函数就很简单 -

int hash (int n) {
  switch (n) {
    case 10:   return 0;
    case 100:  return 1;
    case 32:   return 2;
    // ...
    default:   return -1;
  }
}

Answer 2

找到一个

我尝试了一些东西，找到了一个半手动的：

(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

Answer 3

在某些平台（例如嵌入式）上，模运算的成本很高，因此最好避免使用 % 13。但是低位的AND运算很便宜，并且相当于2的幂的模。

我尝试编写一个简单的程序（用 Python）来搜索 11 个数据点的完美哈希，使用简单的形式，例如 ((x << a) ^ (x << b)) & ; 0xF（其中 & 0xF 相当于 % 16，例如给出 0..15 范围内的结果）。我能够找到以下无冲突哈希，它给出了 0..15 范围内的索引（表示为 C 宏）：

#define HASH(x)    ((((x) << 2) ^ ((x) >> 2)) & 0xF)

这是我使用的 Python 程序：

data = [ 10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0 ]

def shift_right(value, shift_value):
    """Shift right that allows for negative values, which shift left
    (Python shift operator doesn't allow negative shift values)"""
    if shift_value == None:
        return 0
    if shift_value < 0:
        return value << (-shift_value)
    else:
        return value >> shift_value

def find_hash():
    def hashf(val, i, j = None, k = None):
        return (shift_right(val, i) ^ shift_right(val, j) ^ shift_right(val, k)) & 0xF

    for i in xrange(-7, 8):
        for j in xrange(i, 8):
            #for k in xrange(j, 8):
                #j = None
                k = None
                outputs = set()
                for val in data:
                    hash_val = hashf(val, i, j, k)
                    if hash_val >= 13:
                        pass
                        #break
                    if hash_val in outputs:
                        break
                    else:
                        outputs.add(hash_val)
                else:
                    print i, j, k, outputs

if __name__ == '__main__':
    find_hash()

Answer 4

Bob Jenkins 也有一个程序：http://burtleburtle.net/bob/hash/perfect。 html

除非你非常幸运，否则对于给定的数据集没有“好的”完美哈希函数。完美的哈希算法通常在键上使用简单的哈希函数（使用足够的位，因此不会发生冲突），然后使用表来完成它。

Answer 5

只是一些准分析的胡言乱语：

在你的一组数字中，总共十一个，其中三个是奇数，八个是偶数。
查看最简单的散列形式 - %13 - 将为您提供以下散列值：
10 - 3,
100 - 9,
32 - 6,
45 - 6,
58 - 6,
126 - 9,
3 - 3,
29 - 3,
200 - 5,
400 - 10,
0 - 0

当然，由于碰撞次数过多，这是不可用的。需要更详细的东西。

为什么要说显而易见的事情呢？
考虑到数字太少，任何复杂的 - 或者更确切地说，“不太简单” - 算法可能会比 switch 语句或（我更喜欢）简单地搜索大小为 11 个位置的无符号短/长向量并使用比赛的索引。

为什么要使用矢量搜索？

1. 您可以通过将最常出现的值放置在向量的开头来对其进行微调。
2. 我认为目的是将散列索引插入到具有良好顺序编号的开关中。从这个角度来看，首先使用一个开关来查找索引，然后将其插入另一个开关似乎很浪费。也许您应该考虑根本不使用散列并直接进入最后的开关？
3. 哈希的 switch 版本无法进行微调，并且由于值差异很大，将导致编译器生成二叉搜索树，这将导致大量比较和条件/其他跳转（尤其昂贵），这需要时间（我假设您已经转向散列（因为它的速度）并且需要空间。
4. 如果您想另外加速向量搜索并且使用 x86 系统，您可以基于汇编器指令 repne scasw（短）/repne scasd（长）实现向量搜索，这会快得多。经过几条指令的设置时间后，您将找到一条指令中的第一个条目和十一条指令中的最后一个条目，然后是一些指令清理。这意味着最好情况下需要 5-10 条指令，最坏情况下需要 15-20 条指令。除了一两种情况外，这应该在所有情况下都击败基于交换机的散列。

Answer 6

当我在 Mathematica 中尝试时，我进行了快速检查并使用 SHA256 哈希函数，然后进行模除以 13 。对于 C++，此函数应该位于 openssl 库中。请参阅此帖子。

如果您进行了大量的散列和查找，则重复执行模除操作是一项相当昂贵的操作。还有另一种将 n 位哈希函数映射到 i 位索引的方法。请参阅此帖子 Michael Mitzenmacher 介绍了如何使用 C 语言进行位移操作。希望有所帮助。

Answer 7

尝试以下将您的 n 值映射到 0 到 12 之间的唯一索引
(1369%(n+1))%13