哈希表大小调整，线性探测和复杂性

Question

我通过一些老试卷的工作和整个下面传来：

展示出一种封闭的地址哈希算法使用 数据是如何工作的设置{4, 2, 12, 3, 9, 11, 7, 8, 13, 18}作为输入例子。

假设数组的lenght最初7.你应该证明：

我。如何构建哈希表，一步一步地进行。如何在O（1）时间内实现对散列表的搜索。现在

，因为该阵列被初始设置为7，最大的散列函数我可以使用是n mod 7，因为有将被插入比阵列的大小以上的元素，该阵列必须被调整大小。

我假设散列函数在调整大小后保持不变？

关于第二部分，如果多个元素哈希到相同的值，如何实现O(1)搜索？当然，我需要依次通过数组中的聚类元素？

这个假设是否正确？

Answer 1

调整您的哈希表后。你应该做一个“昂贵”的重新粉碎。也就是说，你必须重新调整现有的密钥，为它们分配新的插槽。你的散列函数将是id mod newSize。

当散列表已满时，好的实现不会执行调整大小/重新散列。有一个负载因子，当负载因子高于0.75（或者0.8'不准确记得）时，开放寻址/线性探测方法的性能将显着降低。因此，当负载因子达到极限（例如0.75）时，调整大小/重新哈希将被执行。

散列函数的代价恒定的时间，所以得到元素的代价也是恒定的时间。