我正在尝试对这些值进行散列
10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0
我需要一个函数,它将它们映射到一个大小为13的数组中,而不会导致任何冲突。
我花了几个小时反复思考和搜索,但还是想不通。我还没有接近一个可行的解决方案。
我该如何找到这种散列函数呢?我用过gperf,但我并不是真的理解它,我也无法得到我想要的结果。
发布于 2010-11-09 14:17:43
找到了一个
我尝试了一些方法,找到了一个半手动的方法:
(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
发布于 2010-11-09 14:10:05
如果你知道确切的密钥,那么产生一个完美的散列函数是很容易的-
int hash (int n) {
switch (n) {
case 10: return 0;
case 100: return 1;
case 32: return 2;
// ...
default: return -1;
}
}
发布于 2011-08-08 08:16:35
在某些平台上(例如嵌入式),模运算代价很高,因此最好避免使用% 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()
https://stackoverflow.com/questions/4130936
复制相似问题