哈希表查找時間

Question

當我們在哈希表中插入/查找關鍵字時，教科書表示它是O（1）次。但是，怎麼可能有一個O（1）查找時間？如果散列表將密鑰存儲在一個向量中，則它將花費O（N），如果在二叉樹中，則它將是O（logN）。我只是無法用O（1）訪問時間映像某些數據結構。

謝謝！

Answer 1

哈希表散列您的密鑰並將其放入數組中。

例如，hash（x）= 3，其中x是您的密鑰。該表然後將其放入數組[3]。從數組訪問是O（1）。

Answer 2

哈希表至少包含數組和哈希函數。當一個對象被添加到表中時，散列函數就會在對象上計算出來，並且它將被存儲在數組中的相應值的索引處。例如，如果hash(obj) = 2然後是arr[2] = obj。

散列表上的平均插入/查找是O(1)。

但是，當對象計算相同的散列值時，可能會發生衝突。

在一般情況下，數組的每個索引都有「桶」來處理這些衝突。也就是說，所有三個對象都存儲在哈希表的索引處的其他數據結構（可能是鏈表或另一個數組）。

因此，在散列表上查找的最壞情況是O(n)，因爲存儲在散列表中的所有對象都可能發生衝突並存儲在同一個存儲桶中。