哈希表大小調整，線性探測和複雜性

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）時，調整大小/重新哈希將被執行。

散列函數的代價恆定的時間，所以得到元素的代價也是恆定的時間。