algorithm - 哈希表大小调整、线性探测和复杂性

Question

我正在研究一些旧试卷并发现以下内容:

Demonstrate how a closed address hashing algorithm works using the data set {4, 2, 12, 3, 9, 11, 7, 8, 13, 18} as an input example.

Assume the lenght of the array is initially 7. You should demonstrate:

i. how the hash table is built, step-by-step ii. how a search on a hash table can be acheived in O(1) time.

现在，假设数组初始设置为 7，我可以使用的最大哈希函数是 n mod 7，因为要插入的元素多于数组的大小，数组必须调整大小。

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

关于第二部分，如果多个元素散列到同一个值，如何实现O(1) 搜索？当然，我需要按顺序遍历数组中的聚集元素吗？

这个假设是否正确？

Answer 1

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

当哈希表已满时，良好的实现不会调整大小/重新哈希。有一个负载因子，当负载因子高于 0.75(或 0.8？不记得确切)时，开放寻址/线性探测方法的性能会急剧下降因此，当负载因子达到限制(例如 0.75)时，调整大小/重新哈希将被执行。

哈希函数花费常数时间，因此获取元素也花费常数时间。