完美散列函数
完美散列函数
提问于 2010-11-09 14:04:26
我正在尝试对这些值进行散列
10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0我需要一个函数，它将它们映射到一个大小为13的数组中，而不会导致任何冲突。
我花了几个小时反复思考和搜索，但还是想不通。我还没有接近一个可行的解决方案。
我该如何找到这种散列函数呢？我用过gperf，但我并不是真的理解它，我也无法得到我想要的结果。
回答 6
Stack Overflow用户
回答已采纳
发布于 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
endStack Overflow用户
发布于 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;
}
}Stack Overflow用户
发布于 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()页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4130936
复制相关文章
相似问题
腾讯云开发者
