Hashtable實現

Question

我最近被問到'你會如何實現一個hastable'。我知道哈希算法是至關重要的，因爲碰撞越少，WRT性能越好，但是應該採用什麼算法/數據結構來爲插入/刪除/查找提供分期不變的時間{O（1）}？

Answer 1

哈希表有兩種主要的可能性：

1. 開放尋址，這是一個簡單的陣列 [動態數組actualy如果你 可以讓你的桌子生長在飛。一旦遇到衝突 - 您需要使用第二個哈希函數來查找元素將映射到的下一個主元。注意當你的哈希表也允許刪除時，這個解決方案有一些麻煩[可以解決]。 [特殊標記爲「已刪除」主菜]
2. 鏈接 - 在這個解決方案中，陣列在每個主菜是鏈表 - containig散列到這個主菜所有元素。在這裏 - 映射到特定值的所有元素都在列表中。

以便允許armotorized O（1）插入/刪除/查找關於哈希表[在這兩種解決方案]重要的部分 - 被分配一個較大的表和重散列一旦達到定義load factor預。

編輯：複雜analsis：
承擔p負載因數一些p < 1。

1. 在每個接入「碰撞」的概率爲p因此陣列的平均訪問爲：Sigma(i * p^(i-1) * (1-p)) for each i in [1,n]這給你：Sigma(i * p^(i-1) * (1-p)) = (1-p) * Sigma(i * p^(i-1)) <= (1-p) * 1/(p-1)^2 = 1-p = CONST。 [看看Sigma(i * p^(i-1)) < 1/(p-1)^2 in wolfram alpha的正確性]。因此平均得到對該陣列的連續數量的訪問。另外：在達到加載因子後，您可能需要重新哈希所有元素，從而導致對該陣列的訪問O(n)。這導致n * O(1) ops [添加n個元素]和1 * O(n) op [rehashing]，所以您得到：(n * O(1) + 1 * O(n))/n = O(1) armotorized時間。
2. 與（1）非常相似，但分析是在列表訪問上完成的。每個操作只需要一個數組訪問，並且需要不同數量的列表訪問 - 具有與之前相同的分析。