完美的哈希函数

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()