多少个哈希桶

Question

如果我注意到哈希表（或构建在哈希表上的任何其他数据结构）正在填满，那么你应该在什么时候构建一个包含更多桶的新表。到目前为止，在表格中给出n个项目，你如何计算出新的桶数量？

所以我想说我有100个桶。当有50个项目时，我应该重组吗？ 500？ 5000？或者我应该寻找最完整的桶和关键吗？然后，当我达到这一点时，我有多大的新哈希表？

与此相关，如果您事先知道大约会有多少项，那么有没有办法计算存储桶的数量以获得良好的平均性能？

我知道真正的答案取决于许多其他考虑因素，例如在特定示例中速度与大小的重要性，但我正在寻找一般的guildlines。

我也知道我不应该优化这种事情，除非良好的分析表明这是一个瓶颈。我只是在想一个会使用大量哈希表的项目，并想知道如何处理这个问题。

Answer 1

一个好的经验法则（不总是理想的，好吧，只是一个经验法则）是在散列表填充高达80％时重新散列。这意味着如果你有100个水桶和80个项目，无论你之前有多少次碰撞，都需要时间来增加容量。

你应该增加多少钱？嗯，也没有完美的价值。最简单的解决方案是每增加一倍的容量。所以它分为200,400,800等。如果您认为这太多了（毕竟当哈希表变得非常大并且您可能永远不会填满16 MB时，它将从8 MB内存跳到16 MB），请选择较小的增长因子。至少建议使用1/3（从100增加到133）我会说，也许让它每次增长50％作为妥协。

请注意，所有这些还取决于如何处理冲突。处理它们（我个人最喜欢的）的一种简单方法是在发生碰撞时将项目存储在链接列表中。如果在同一个键上放置了3个项目，则仍然只能找到3个比较项目。由于链表对搜索非常有效，您可能希望提前增加容量，例如如果使用60％的容量来保持哈希表的快速。 OTOH，你可以做一些更复杂的事情并保持关于碰撞次数的统计数据。只要你几乎没有任何冲突（如果你有一个非常好的哈希函数），就没有必要重新哈希，即使它的99％的容量正在使用中。此外，如果您以复杂的方式处理冲突（例如，每个节点都是一个已排序的表，您可以在这些中执行二进制搜索），如果表加载到200％，那么查找可能仍然足够快（因此您有两倍的项目作为能力）。在这种情况下，你可以保持统计数据最大的排序表有多大，当它变大时，比方说，8个条目，你认为这变得太慢，然后你重新哈希。

重新散列非常慢，因此应尽可能经常避免。因此，如果您需要重新哈希，请不要仅仅增加容量，否则在添加更多项目时必须很快再次重新哈希。因此，当您需要重新哈希时，使容量显着大于表中当前项目的数量，其他一切都是太少的容量。

Answer 2

一般情况下，你要注意负载因素（非正式地，你已经说过），正式定义为<！>＃945; <！> nbsp; = <！> nbsp; n <！> nbsp; / <！> nbsp; N ，即用于总桶数的比率。为了使哈希表正常运行（或者至少以数学术语表示其性能），它应该是<！>＃945; <！> nbsp; <！> lt; <！> nbsp; 1。

其他一切都取决于实证测试：如果你看到你的哈希表在<！>＃945开始表现不佳; <！> nbsp; <！> gt; <！> nbsp; 0.5，那么一定要保持在这个价值之下。此值还取决于您的碰撞解决技术。使用链接进行散列可能需要其他负载因子，而不是使用开放寻址进行散列。另一个因素是缓存局部性。如果你的表太大，它将不适合主内存。由于您对数组的访问是随机的，因此从缓存加载可能会成为瓶颈。

Answer 3

通常有两种类型的哈希表：打开和关闭。

在打开的哈希表中，您可以根据哈希找到正确的存储桶，然后构建一个挂在该存储桶上的项目列表。

在一个封闭的散列表中，您可以使用散列值找到初始存储区，如果它被占用，则会探测下一个值。在简单的情况下，您可以通过查找下一个空闲存储桶来执行此操作，或者您可以从项目中创建第二个哈希值并逐步创建（尽管您必须确保这是散列表大小的模数，因此您将访问所有水桶）。

通常不会调整开放哈希表的大小。您将初始大小设置为您认为合理的问题。正如其他人指出的那样你可以在一个开放的哈希表上调整大小，但现在推理这个数据结构的性能变得非常困难。如果在给定存储桶的长度为L时调整大小，那么可能最终仅在整个哈希表中的L个项目上调整大小，这是非常低效的。

当加载因子（哈希表中的项目数/桶数）达到某个预定义值时，将调整闭合哈希表的大小。我倾向于使用80％，但确切的值不太可能太关键。

封闭散列表的好处是插入项的摊销成本总是O（1）（假设散列函数很好）。由于调整大小的成本，插入特定项目可能是O（N），但这种情况很少发生。

Answer 4

取决于您正在构建的哈希表的类型。如果您使用的是基于固定数组的哈希表（与存储桶的链接列表相对），则应在表填满或达到最大探测次数时调整阵列大小（取决于您是否更关心速度或记忆）。如果您正在使用链接列表，那么内存并不是一个问题，因为并且不必探测空白空间，因此调整大小并不是一件大事。

哈希表的关键是哈希算法，而不是桶的数量。理想情况下，您总是希望每个存储桶中最多只有一个项目，因此理想情况下，当哈希表中的项目数量=存储桶数量时，应该调整大小。如果您的数据分布不均匀，那么使用更好的哈希算法比使用更好的调整大小策略更好。

Answer 5

如果使用Linear Hashing，表本身会自动通过维持一个恒定的加载因子来处理调整大小。