algorithm - 测量哈希函数质量(用于映射/关联数组)

Question

我正在研究 C 中的关联数组库(我没有编写)。类似于 C++ 中的 map 或 Python 的字典。

有一些非标准的哈希函数，我不确定它们是否非常好。 (也许最初的开发者只是扔了一些神奇的数字、异或运算符并希望最好)。

我编写了一个测试来衡量哈希函数在给定一些样本输入的情况下的执行情况，以衡量它将项目分配到固定数量的桶(在本例中为模数数组大小)中的均匀程度。

这样，只要有足够的输入，就会有一些方法来衡量哈希函数的执行情况。

对于任何编写关联数组的人来说，这似乎都是一个普遍的问题。

---

是否有一些衡量哈希函数执行情况的约定？ (就分发质量而言，而不是速度)。

最差的情况是每个输入的结果相同，而最好的情况是均匀分布(或尽可能接近)。

请注意，我不是在寻找密码强度。

Answer 1

有一个Formula (页中)出自龙书。

我个人有一个经验法则:(假设线性链接)将 N 项插入 N 个槽-> 链中，并计算访问总数(链中第一个:= 1 次访问；第二个:= 2 次访问，等等)需要获取所有 N 个元素。 (这等于 SUM ( chainlen * (chainlen +1)/2) ，对所有链求和)

给定随机输入数据，对于任何合理的哈希函数，该指标应为 1.5 * N，或略低于该值。

---

使用 2543846 个唯一标记/单词(及其统计信息)列表的典型运行示例散列到正好 2543846 个槽/桶中:

plasser@pisbak:~/src/hash$ ./diskhash woorden.txt woorden.hsh
Ptr = 0x7fb5c264f000, Sz = 37362821
Array= 0x7fb5bff7e000 Cnt = 2543846
__________________
Histogram of seek lenghts:
len:    Count     Hops   Fraction (Cumulative)
  1:  1606429  1606429 0.63149617 (0.63149617)
  2:   672469  1344938 0.26435130 (0.89584747)
  3:   205046   615138 0.08060472 (0.97645219)
  4:    48604   194416 0.01910650 (0.99555869)
  5:     9477    47385 0.00372546 (0.99928415)
  6:     1581     9486 0.00062150 (0.99990565)
  7:      215     1505 0.00008452 (0.99999017)
  8:       24      192 0.00000943 (0.99999961)
  9:        1        9 0.00000039 (1.00000000)
Tot:  2543846  3819498           (1.50147)
Cnt  2543846 Empty   937417 (0.36850) Collisions 247 RedDragon 7638996/7631537=1.000977
__________________

• 空槽的比例是 0.36850 ，这应该是 (1/e)
• 具有多个项目(chain-length > 1)的槽的比例也约为 (1/e)
• 恰好有 1 个项目的插槽部分是剩余的::1 - (2/e)
• 冲突次数似乎有点高，但对于 32 位哈希值上的 250 万个项目，这并不异常(exception)。