有多少散列桶

一个好的经验法则(不总是理想的,好吧,只是经验法则)是,如果哈希表被填充到80%,则重新散列。这意味着,如果你有100个桶和80个物品在里面,不管你以前有多少次碰撞,现在是时候增加容量了。

你应该增加多少?嗯,也没有完美的价值。最简单的解决方案是在每次增加时将容量加倍。所以它是200,400,800等等。如果您认为这太多(毕竟当哈希表变大时,它将从8 MB内存跳到16 MB内存,而您可能永远无法填满16 MB内存),请选择一个较小的增长因子。至少有三分之一是推荐的(从100增长到133),我想说,也许让它每次增长50%作为一个折衷方案。

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

重新散列是非常缓慢的,所以应该尽量避免。因此,如果您需要重新散列,不要将容量增长得太小,否则在添加更多项目时,您必须很快重新散列。因此,当需要重新散列时,使容量明显大于表中当前项目的数量,其他所有内容的容量都太小。

一般来说,你要注意负载系数(非正式地,你已经说过了),它正式定义为_= n / n 即已用桶与总桶的比率。为了使哈希表正常工作(或至少从数学角度考虑其性能),它应该是_±<1。

其他的一切都取决于经验测试:如果您看到哈希表在“0.5”开始时表现不好,那么一定要保持在该值之下。该值还取决于碰撞解决技术。使用链的散列可能需要其他负载因素,而不是使用开放寻址的散列。另一个因素是缓存位置。如果你的桌子太大,它就放不进主存。由于您对数组的访问是随机的,从缓存加载可能会成为一个瓶颈。

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

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

在一个封闭的哈希表中,您可以使用哈希值找到初始bucket,如果它被占用,您可以探测下一个值。在简单的情况下,您可以通过查找下一个空闲bucket来完成此操作,或者您可以从项目中创建第二个哈希值并逐步执行此操作(尽管您必须确保这是哈希表大小的主模,以便访问所有bucket)。

打开的哈希表通常不会调整大小。您将初始大小设置为您认为对该问题合理的大小。正如其他人指出的那样,您可以在一个开放的哈希表上调整大小,但是关于这个数据结构的性能的推理现在变得非常困难。如果当给定的桶的长度为l时调整大小,则 可以 最后只对整个哈希表中的L项进行大小调整,这是非常低效的。

当加载因子(哈希表中的项目数/存储桶数)达到某个预定义值时,将调整关闭的哈希表的大小。我倾向于使用80%,但准确的数值不太可能太关键。

封闭哈希表的好处在于 摊销 插入一个项目的成本总是O(1)(假设一个好的哈希函数)。由于调整大小的成本,插入一个特定的项目可能是O(N),但这很少发生。

取决于正在生成的哈希表的类型。如果使用固定的基于数组的哈希表(与bucket的链接列表不同),则应在表满或达到最大探测计数时(取决于您更关心速度还是内存)调整数组的大小。如果您使用的是链表,那么内存就不那么重要了,因为它不需要探测空的空间,所以调整大小也没什么大不了的。

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

如果使用线性散列,则表本身会自动通过保持恒定的加载因子来调整大小。