c - 具有伪随机散列方法的散列数组的大小

Question

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

Answer 1

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

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

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

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

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

对于素值，我建议在您的 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() 应该返回一个大整数。

Answer 2

随着元素数量的增加，您可以重新散列哈希表。此过程会更改存储桶的数量。根据细节，这甚至可能是必要的。

• 如果您使用链接（即具有相同哈希值的所有元素进入同一个桶），那么理论上您可以无限期地增长表而无需重新哈希，但它最终基本上只是一个链表（或任何序列容器代表一个桶）。因此，您应该跟踪当前的负载因子（元素数除以存储桶数）并在它变得太大时增大表。

• 如果您使用探测（“开放寻址”），则一旦探测无法找到新元素的空闲位置，您就必须重新散列。