如何优化/改进这个哈希函数

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

如果将4个指针截断为32位（即16字节），FNV哈希需要27个周期（手工汇编）。
不幸的是，这导致哈希冲突率达到81％，而应该是37％。
运行完整的15次乘法需要179个周期。

- Johan

---

@Johan 这只是一个选项而已。我的观点是，让无符号数据类型溢出可能比执行模数操作更有效率。它可能是 unsigned short 或 unsigned char，但它的大小可能会限制这种可能性，因为它是哈希表的大小。 - anthonyvd

@pwny，除非你使用质数进行模运算，否则哈希冲突的数量将会增加，从而失去了哈希的目的。 - Johan

lea习惯用语具有比d+c3+b9+c*27更多的依赖性，这可能会更快。不过，“a，b，c，d”的范围是多少？了解这一点可能有助于模数缩减。 - Aki Suihkonen

我想另一个角度是，你真的需要调用它1300万次吗？你能优化更高级别的算法吗？ - Ken Y-N

最后的 +3 是没有用的，因为你接下来会执行 %= prime。这实际上是将你的桶旋转了 3 个位置，但并不影响冲突。当 x % prime == y % prime 时，也有 x+3 % prime == y+3 % prime。 - MSalters

Answer 1

用倒数乘法代替取模运算

在这个哈希函数中，主要的循环消耗者是取模运算符。

如果您用倒数乘法代替除法，计算速度会更快。请注意，计算倒数需要进行3次除法，因此只有在可以重复使用倒数的情况下才应该这样做。

好了，这是使用的代码：http://www.agner.org/optimize/asmlib.zip 来自：http://www.agner.org/optimize/

// ;*************************  divfixedi64.asm  *********************************
// ; Author:           Agner Fog

//extern "C" void setdivisoru32(uint Buffer[2], uint d)
asm
  mov     r8d, edx               // x
  mov     r9, rcx                // Buffer
  dec     r8d                    // r8d = r8d or esi
  mov     ecx, -1                // value for bsr if r8d = 0
  bsr     ecx, r8d               // floor(log2(d-1))
  inc     r8d
  inc     ecx                    // L = ceil(log2(d))
  mov     edx, 1
  shl     rdx, cl                // 2^L (64 bit shift because cl may be 32)
  sub     edx, r8d
  xor     eax, eax
  div     r8d
  inc     eax
  mov     [r9], eax              // multiplier
  sub     ecx, 1
  setae   dl
  movzx   edx, dl                // shift1
  seta    al
  neg     al
  and     al,cl
  movzx   eax, al                // shift 2
  shl     eax, 8
  or      eax, edx
  mov     [r9+4], eax            // shift 1 and shift 2
  ret
end;

求模运算的代码：

//extern "C" uint modFixedU32(uint Buffer[2], uint d)
asm
  mov     eax,  edx
  mov     r10d, edx                // x
  mov     r11d, edx                 // save x
  mul     dword [rcx]              // Buffer (i.e.: m')
  sub     r10d, edx                // x-t
  mov     ecx, [rcx+4]             // shift 1 and shift 2
  shr     r10d, cl
  lea     eax, [r10+rdx]
  mov     cl,  ch
  shr     eax, cl
  // Result:= x - m * fastDiv32.dividefixedu32(Buffer, x);
  mul     r8d                    // m * ...
  sub     r11d, eax              // x - (m  * ...)
  mov     eax,r11d
  ret
end;

时间的差异如下：

hashprime   classic hash (mod)  new hash        new          old  
(# of runs)    cycles/run       per run       (no cache)   (no cache)
--------------------------------------------------------------------
 4049               56             21            16.6        51
16217               68           not measured
64871              127             89            16.5        50

缓存问题
循环时间的增加是由于数据溢出缓存，导致访问主内存。
当我通过反复哈希相同的值来消除缓存效应时，这一点可以清楚地看到。

- Johan

Answer 2

这样的东西可能很有用：

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是否实际上比上述类型的哈希具有更好的性质，但它同样快速，并且被广泛使用。

- tmyklebu

---

我已经将FNV算法优化到27个循环（有点作弊）。 - Johan

不行，作弊会破坏它，回到179个周期。 - Johan

尝试使用我写的东西，只需使用不同（更大）的数字。请记住，一旦您的表格无法适应L1缓存，大部分时间将花费在L1缺失上。（如果您绘制性能与表格大小的图表，您将看到四到五个明显的区域，其中性能很容易建模，并且在之间有明显的断点，其中情况会急剧恶化。当您开始遭受L1缺失，L2缺失，TLB缺失等时，就会出现急剧的断点。） - tmyklebu

Answer 3

假设hashprime是一个常数，你可以将模操作实现为位掩码。关于细节我不太确定，但也许这个答案能给你一些指引。

- larsmoa

---

通常情况下，由于hashprime表示表中桶的数量，因此随着表的增长，hashprime也会发生变化。如果您控制该表，则可以控制hashprime列表并更改所实现的操作。 - Matthieu M.

@MatthieuM.：是的，没错。我在想如果性能非常重要，并且可以估算出表中元素的数量范围，那么表的大小就可以固定。 - larsmoa