c - 使用伪随机哈希方法的哈希数组的大小

Question

我对设置良好且有效的散列数组大小感到困惑。我正在读的书说负载因子应该在 75% 左右才能成为一个好的散列数组。但在我实际尝试测试散列数组放置键之前，我不知道如何从理论上决定数组的大小。在达到最佳散列数组大小方面是否有任何线索或关键技巧？大小是否取决于您使用的散列方法？

Answer 1

您的哈希表解决方案不应该依赖于事先知道要放入表中的元素数量。相反，动态增长和收缩的结构是最好的。

建议使用较小的哈希表大小 (<= 1) 进行初始化，并在负载因子达到 150-200% 时将哈希表大小增加四倍左右。这涉及将整个旧表重新散列到新表中，但在现实生活中的示例中不应经常发生。

还应该有大约是增长阈值的 1/2 的收缩阈值。

通过使增长和收缩阈值彼此远离，如果您在临界大小附近添加/删除哈希表元素，则可以避免大量工作。

哈希表大小还有一个额外的好处，那就是它们是质数。典型的哈希函数由一些预哈希函数组成，例如unsigned Hash(unsigned item)，然后用哈希表大小修改结果:BucketIndex = Hash(item)%HashTableSize 如果 Hash() 表现不佳，素数哈希表大小可以改善分散性。

对于素数，我建议在哈希数据结构中保留 HashPrime_Index，然后在需要知道哈希表的大小时使用下表。

static const size_t HashPrime[] = { 0, 2, 3, 7, 13, 31, 61, ... }; // Primes just less than powers of 2.

增长时，使用 0, 3, 13, ... 收缩时，使用 ..., 61, 13, 2。

当您使用素数哈希表大小时，最佳哈希表大小对方法 Hash() 的依赖程度要小得多。注意:Hash() 应返回一个大整数。