如何优化/改进此哈希函数

Question

我有一个存储四叉树条目的哈希表.
哈希函数如下所示:

四叉树哈希

#define node_hash(a,b,c,d) \
  (((int)(d))+3*(((int)(c))+3*(((int)(b))+3*((int)(a))+3)))

请注意,此操作的结果始终使用模数素数进行分块,如下所示:

h = node_hash(p->nw, p->ne, p->sw, p->se) ;
h %= hashprime ;
...

与最佳散列的比较
一些统计分析表明,这种散列在减少碰撞方面是最佳的.
给出带有b桶和n条目的哈希表.使用完美散列的碰撞风险是:
(n - b * (1 - power((b-1)/b,n)))) * 100 / n
当n = b时,这意味着碰撞风险为37%.

一些测试表明,上面的哈希与标准非常吻合(对于哈希表的所有填充级别).

运行时运行时间
在很大程度上取决于值hashprime

计时(1000次运行中最好的)是:

hashprime   CPU-cycles per run
--------------------------------
 4049               56
16217               68
64871              127    <-- whoooh

有没有办法改善这一点,同时仍然保持最佳的碰撞风险？

通过优化模数运算(在循环外使用'魔术'数字计算机替换它).
用其他哈希函数替换哈希函数.

背景
产生以下组件:

//--------h = node_hash(p->nw, p->ne, p->sw, p->se) ;
mov eax,[rcx+node.nw]       <<+
lea eax,[eax+eax*2+3]         |
add eax,[rcx+node.ne]         |
lea eax,[eax+eax*2]           +-  takes +/- 12 cycles
add eax,[rcx+node.sw]         |
lea eax,[eax+eax*2]           |
add eax,[rcx+node.se]       <<+
//--------h %= hashprime ;
mov esi,[hashprime]
xor edx,edx
div esi
mov rax,rdx                    <<--- takes all the rest

[编辑]
我或许可以做以下事实:

C = A % B等同于C = A – B * (A / B)
使用的事实,整数除法是与由它的倒数相乘.
因此,将公式转换为C = A - B * (A * rB)
注意,对于整数除法,倒数是幻数,请参阅:http://www.hackersdelight.org/magic.htm
C代码在此处:http://web.archive.org/web/20070713211039/ http://hackersdelight.org/HDcode/magic.c

[FNV哈希]

请参阅:http://www.isthe.com/chongo/tech/comp/fnv/#FNV-1a

hash = offset_basis
for each byte to be hashed
 hash = hash xor octet_of_data
 hash = hash * FNV_prime (for 32 bits = 16777619)
return hash

对于截断为32位= 16字节的4个指针,FNV哈希需要27个周期(手工组装)
不幸的是,这导致哈希冲突达到81%,应该是37%.
运行完整的15次乘法需要179个周期.

Answer 1

像这样的东西可能会有用：

static inline unsigned int hash4(unsigned int a, unsigned int b,
    unsigned int c, unsigned int d) {
  unsigned long long foo = 123456789*(long long)a ^ 243956871*(long long)b
                         ^ 918273645*(long long)c ^ 347562981*(long long)d;
  return (unsigned int)(foo >> 32);
}

将我输入的四个奇数替换为随机生成的64位奇数；上面的那些效果不会那么好。（64 位，因此高 32 位在某种程度上是低位的随机混合。）这与您提供的代码差不多快，但它允许您使用 2 的幂表大小而不是质数表大小，而无需害怕。

每个人用于类似工作负载的东西是FNV 哈希。我不确定 FNV 是否确实比上述类型的哈希具有更好的属性，但它的速度同样快，而且使用相当广泛。