木头的博客

我是木头 有些想法 有点精力

0%

哈希函数质数速查表

在设计一个好的散列配置的过程中,有一个用于散列表大小的素数列表是有帮助的。

下面就是这样一份速查表,它具有以下特性:

  1. 列表中的每个数字都是质数
  2. 每个数字的大小都略小于前一个数字的两倍
  3. 每个数字都尽可能远离最接近的两个2的幂

对哈希表使用素数是一个好主意,因为它最大限度地减少了哈希表中的聚类。第 (2) 项很好,因为它可以方便地在扩展数据时增长哈希表。据称,第 (3) 项在实践中已显示出特别好的结果。

declwrupr% errprime
642^52^610.04166753
1282^62^71.04166797
2562^72^80.520833193
5122^82^91.302083389
10242^92^100.130208769
20482^102^110.4557291543
40962^112^120.2278653079
81922^122^130.1139326151
16,3842^132^140.00813812289
32,7682^142^150.06917324593
65,5362^152^160.01017349157
131,0722^162^170.01322498317
262,1442^172^180.002543196613
524,2882^182^190.006358393241
1,048,5762^192^200.000127786433
2,097,1522^202^210.0003181572869
4,194,3042^212^220.0003503145739
8,388,6082^222^230.0002076291469
16,777,2162^232^240.00004012582917
33,554,4322^242^250.00007525165843
67,108,8642^252^260.00001050331653
134,217,7282^262^270.000023100663319
268,435,4562^272^280.000009201326611
536,870,9122^282^290.000001402653189
1,073,741,8242^292^300.000011805306457
2,147,483,6482^302^310.0000001610612741

这几栏依次是2的上界幂对应的十进制数、2的下限幂、2的上限幂、素数与前两者的最佳中间值的相对偏差(百分比),最后是素数本身。

Happy hashing!


转载自 https://planetmath.org/goodhashtableprimes