AVL vs帶鏈接的Hashtable

Question

我知道avl樹的最好情況和最壞情況會被記錄爲查找，插入和刪除。然而，最好的情況和最糟糕的情況是，鏈接的哈希表是什麼？如果給出兩個神祕數據結構，我將如何區分兩者？

Answer 1

鏈接的哈希表最好的情況和最壞的情況是什麼？

查找，插入，刪除操作的最佳時間爲O（1）或恆定時間。對於最壞的時候，

• 插入：O（K），其中k =最長鏈元件的數目：O（1），假定鏈通過只是增加了鏈
• 刪除的端部進行。 k == n散列函數非常差，並且所有n值映射到相同條目並被鏈接。所以，絕對最壞的情況是O（n）。
• 發現：O（N），使用同樣理由刪除

我將如何區分這兩個如果給出了兩個神祕的數據結構？

只是一個想法：在這兩種結構

• 插入數據並繪製插入時間插入操作VSñ。選擇數據以使模仿AVL樹的最壞情況（即如果整數，請按1000000，99999，999998 ...的順序插入），但不適用於散列表。
• 注意正在生成的情節。 AVL樹將從頭開始具有插入時間log（n），而對於散列表，這應該是相當恆定的。大約第1000個插入式ALV樹將插入10次（假設插入發生最壞情況）。但是對於hashtable，插入時間應該和以前幾乎相同。假設散列表有足夠的容量和散列函數是不夠愚蠢與序列數據，如'1000000，99999，999998 ...'
• 衝突如果仍然不確定，然後轟炸這兩個結構與插入，希望填滿散列表並強制它開始鏈接。多次插入後，注意情節。 AVL仍然保持log（n）曲線，但散列表將顯示不同的曲線，如：具有較高常數值的恆定時間。