哈希表Ω（n^2）運行時？

我對此很困惑。閱讀完教科書並完成練習後，我仍然不明白它的工作原理，但不幸的是，我不能親自去看教授，並且很難聯繫（夏季在線課程，不同的時區）。我覺得如果我明白如何解決這個問題，它會'點擊'。教科書詳細說明了散列函數和運行時間，但我覺得這個問題超出了我們所學知識的範圍。如果有人能指出我可能會有所幫助的東西，那會很棒。哈希表Ω（n^2）運行時？

1）考慮插入米鍵爲哈希表T [0 ..米 - 1]的方法，其中米是素數，並且我們使用打開的尋址。我們使用的散列函數是h（ķ，我）=（ķ + 我）模米。得到的米示例鍵K1，K2 ...公里，使得操作的以下序列需要Ω（N^2）時間：

刀片（K1），插入（K2），...，插入（公里）

據我所知，插入操作都應該採取O（1）時間，或在某些情況下，爲O（n）。我究竟應該拿出能夠將時間變成Ω（n^2）的密鑰？我希望能夠理解這一點，我覺得我錯過了一些巨大的提示，因爲教科書的章節看起來很簡單，對我來說很有意義，並且完全沒有幫助。在這個問題上說，m是一個主要的，這是重要的嗎？我只是迷失了方向，Google曾經讓我失望過。

來源

2017-07-05 user4832877

你的意思是歐米茄（m^2），而不是歐米茄（n^2）？ – user3080953

不，問題肯定會使用n。 – user4832877

每個降序（一個）序列都可以，例如：'m，m-1，m-2，...，2,1,0' – wildplasser

這裏的關鍵詞是哈希衝突：

爲了哈希函數很好地工作，你需要的值一定的投入要均勻分佈在所有m可能值項存儲在。如果哈希表的元素插入的條目數大致相同，則可以預期每個元素都存儲在其散列值（或其附近）（意味着只需少量的探測），從而使訪問，插入和刪除成爲常量時間操作。

如果您發現每次散列函數映射到相同值的不同輸入值（碰撞），插入期間探測步驟將不得不跳過所有以前添加的元素，每個元素的時間爲Ω（n）一般。因此，我們得到Ω（n²）的運行時間

來源

2017-07-05 19:16:46

謝謝。因此，例如3,9和27將工作，因爲這些都散列到0，除非我改變？ – user4832877

如果你的散列表有'm = 3'條目，那麼是的，就像6,15,24，......你創建衝突的方式取決於你的散列函數，但我認爲你有這個概念。 –

哈希表Ω（n^2）運行時？

回答

相關問題