多少个哈希桶

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

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

与此相关的是,如果您事先知道将要进入的项目大小,是否有办法计算桶数以获得良好的平均性能？

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

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

一个好的拇指规则(不总是理想的,好吧,只是拇指的规则)是重新哈希,如果哈希表填充高达80%.这意味着如果你有100个水桶和80个项目,无论你之前有多少次碰撞,都有时间增加容量.

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

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

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

一般来说,你要注意负载因子(非正式地,你已经说过),它正式定义为α=  n  /  N,即用于总桶数的比率.为了使哈希表正常运行(或至少以数学术语推断其性能),它应该是α<1.

其他一切都取决于经验测试:如果你看到你的哈希表在α> 0.5时起作用不好,那么一定要保持在该值之下.此值还取决于您的碰撞解决技术.使用链接进行散列可能需要其他负载因子,而不是使用开放寻址进行散列.另一个因素是缓存局部性.如果你的表太大,它将不适合主内存.由于您对阵列的访问是随机的,因此从缓存加载可能会成为瓶颈.