6

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

四叉树哈希 

#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 个周期。

4

3 回答 3

3

用倒数乘法替换模
这个散列函数中的主要循环食者是模运算符。

如果你用乘以倒数来代替这个除法，计算会快得多。
请注意，计算倒数涉及 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

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

于 2013-09-28T04:56:13.083 回答
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 是否真的比上述类型的散列具有更好的属性，但它同样快并且被广泛使用。

于 2013-09-27T05:59:38.310 回答
0

假设hashprime是一个常数，您可以将模运算实现为按位掩码。我不确定细节，但也许这个答案可以把你推向正确的方向。

于 2013-09-27T07:23:13.687 回答