我正在尝试散列值
10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0
我需要一个函数将它们映射到一个大小为 13 的数组而不会引起任何冲突。
我已经花了几个小时思考这个问题并在谷歌上搜索，但无法弄清楚。我还没有接近可行的解决方案。
我将如何寻找这种散列函数？我玩过 gperf，但我不太了解它，也无法得到我想要的结果。
问问题
12547 次
7 回答
24
如果您知道确切的键，那么生成完美的散列函数就很简单了 -
int hash (int n) {
switch (n) {
case 10: return 0;
case 100: return 1;
case 32: return 2;
// ...
default: return -1;
}
}
于 2010-11-09T06:10:05.493 回答
12
找到一个
我尝试了一些东西，并半手动找到了一个：
(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-09T06:17:42.530 回答
5
在某些平台（例如嵌入式）上，取模操作很昂贵，因此% 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()
于 2011-08-08T00:16:35.260 回答
3
只是一些准分析的杂谈：
在你的一组数字中，总共有 11 个，其中 3 个是奇数，8 个是偶数。查看最简单的散列形式 - %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 个位置的无符号短/长向量并使用比赛的索引。
为什么要使用矢量搜索？
- 您可以通过将最常出现的值放在向量的开头来对其进行微调。
- 我假设目的是将哈希索引插入到具有良好顺序编号的开关中。在这种情况下，首先使用开关查找索引然后将其插入另一个开关似乎很浪费。也许您应该考虑根本不使用散列并直接进入最终切换？
- 散列的切换版本无法微调，并且由于值差异很大，将导致编译器生成二叉搜索树，这将导致大量比较和条件/其他跳转（特别昂贵），这需要时间（我假设您已经转向散列以提高速度）并且需要空间。
- 如果您想另外加快向量搜索并使用 x86 系统，您可以基于汇编指令 repne scasw (short)/repne scasd (long) 实现向量搜索，这将更快。经过几条指令的设置时间后，您会发现一条指令中的第一个条目和十一条中的最后一个条目，然后是一些指令清理。这意味着 5-10 条指令最好，15-20 条最坏。这应该在所有情况下都击败基于开关的散列，但可能在一两种情况下。
于 2010-11-09T09:28:07.503 回答
2
Bob Jenkins 也有一个程序： http: //burtleburtle.net/bob/hash/perfect.html
除非你非常幸运，否则对于给定的数据集没有“很好”的完美哈希函数。完美的散列算法通常在键上使用一个简单的散列函数（使用足够多的位，因此它不会发生冲突），然后使用一个表来完成它。
于 2010-11-09T06:17:57.373 回答
0
尝试以下将您的 n 值映射到 0 到 12 (1369%(n+1))%13 之间的唯一索引
于 2013-09-21T19:43:58.947 回答