我正在尝试对这些值进行哈希处理
10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0
我花了几个小时思考并搜索，但无法解决。我还没有接近可行的解决方案。
我该如何找到这种类型的哈希函数？我尝试使用gperf进行测试，但我不太理解它，也无法获得我要找的结果。
完美哈希函数
21
我花了几个小时思考并搜索，但无法解决。我还没有接近可行的解决方案。
我该如何找到这种类型的哈希函数？我尝试使用gperf进行测试，但我不太理解它，也无法获得我要找的结果。
- gregghz
4
4这听起来像是一份作业……无论如何，编写一个程序来完成它吧！:-) 想出一个通用的公式，可能使用pow或位运算和模数（嘿，已经有一个例子在答案中了！），然后让计算机遍历值，直到找到“完美哈希函数匹配”。我几年前为我的计算机科学作业做过这个，效果很棒;-) - user166390
1你似乎正在尝试寻找一种最小的完美哈希函数。 - Craig McQueen
3再想一想...你有11个数据点，为什么要映射到大小为13的数组上？数字13有什么特别的意义吗？ - Craig McQueen
1我将你的数字输入到了“gperf”中，它生成了一个完美的哈希函数。看一下你得到的输出，你会看到里面有一个叫做“hash”的函数。 - David Schwartz
7个回答
24
如果您知道确切的键，那么生成完美的哈希函数是微不足道的 -
int hash (int n) {
switch (n) {
case 10: return 0;
case 100: return 1;
case 32: return 2;
// ...
default: return -1;
}
}
- tobyodavies
8
1抱歉，我将其编辑为C++，然后C++标签被从问题中删除了。如果您愿意，可以恢复。 - GManNickG
6这实际上是一次表格搜索。哈希函数的一个好处应该是：它允许比表格搜索更快地评估命中/未命中。 - Craig McQueen
3这个算法的速度明显比表格搜索快，即使在
gcc -O0 下，我的机器上它比简单的线性表查找快了5倍，使用 -O2 时，线性搜索需要超过一秒钟，而1百万次查找的总时间为 0.00。它几乎与已接受的答案在100亿次迭代中的速度相同，在 -O0 下甚至更快，并且在 -O2 内部只有0.2秒的差异。如果你只需要判断键是否存在/有效，则该哈希函数更快--hash(n)==-1 不需要访问内存... 并且你可以通过该函数安全地添加键而保持完美。 - tobyodavies5你的哈希表可能比数据表查找更快，但这不是我想说的。澄清一下：你的哈希表可能对于这个小数据集很有效，这点我们认同。但对于一个大小为n的数据集，你的哈希表是O(n)，而被接受的答案是O(1)。哈希函数的目标是提供一个O(1)的解决方案。因此，在原问题的数据集特定情况下，你的解决方案是令人满意的，但在“查找大于某个阈值的数据集的完美哈希函数”的更普遍情况下，你的答案不适用。 - Craig McQueen
但是对于超过这个值的任何内容，完美哈希函数都没有意义，这不是关于哈希函数的一般性问题。然而，在适当的范围内，这是一种有效的方法来高效地实现完美哈希函数。此外，编译器可以优化为跳转表或搜索树。它不一定是
O(n)，而通常是O(1)或O(log(n))。 - tobyodavies显示剩余3条评论
13
发现一个
我尝试了几个方法，最终半自动找到了一个：
(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
- DigitalRoss
5
在某些平台上（例如嵌入式设备），模运算很昂贵，因此最好避免使用“% 13”。但是，低位AND运算很便宜，并且等效于2的幂次方的模数。
我尝试编写一个简单的程序（用Python语言），使用简单的形式，如
这是我使用的Python程序：
我尝试编写一个简单的程序（用Python语言），使用简单的形式，如
((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()
- Craig McQueen
3
Bob Jenkins也有这样的程序：http://burtleburtle.net/bob/hash/perfect.html
除非你非常幸运，否则对于给定的数据集，没有“好的”完美哈希函数。完美哈希算法通常在键上使用简单的哈希函数（使用足够的位数使其无冲突），然后使用表来完成它。
- Fabian Giesen
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的unsigned short/long向量，并使用匹配的索引。
为什么要使用向量搜索？
- 您可以通过将最常出现的值放置在向量的开头来微调它。
- 我认为目的是将哈希索引插入具有良好顺序编号的开关中。从这个角度来看，先使用开关查找索引，然后再将其插入另一个开关似乎很浪费。也许您应该考虑根本不使用哈希，直接进入最终的开关？
- 开关版本的哈希无法微调，并且由于值的差异很大，将导致编译器生成二叉搜索树，这将导致大量比较和条件/其他跳转（特别昂贵），需要时间（我假设您已经转向哈希以获得速度）并且需要空间。
- 如果您想进一步加快向量搜索速度，并且正在使用x86系统，则可以基于汇编指令repne scasw（短）/repne scasd（长）实现向量搜索，这将更快。在几个指令的设置时间之后，您会发现第一个条目在一个指令中，而最后一个在十一个指令中，然后是一些指令清理。这意味着最佳情况下5-10个指令，最坏情况下15-20个指令。这应该打败基于开关的哈希，除了可能有一两个例外。
- Olof Forshell
0
尝试以下代码，将您的n值映射到0到12之间的唯一索引：
(1369%(n+1))%13
- steviekm3
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接