散列表上線性探測的運行時間

Question

線性探測插入，刪除和搜索的運行時間（大哦）是多少？

感謝

Answer 1

理論最壞情況是O（n），因爲如果你恰巧插入所有元件，使得它們連續碰撞後，插入將有最後一個元素被放入表n步從原來的哈希位置。

然而，如果你知道輸入元素的分佈（可能假定是隨機的，但當然假設是母親......），你可以計算平均預期步數，知道你的散列函數的分佈（希望統一，但它取決於算法的質量），哈希表的長度和插入的元素數量。

如果您的散列函數足夠均勻，則可以使用生日問題計算碰撞概率，並根據這些概率計算預期的探測長度。