使用二叉搜索樹實現哈希表

Question

這是從破解哈希表的編碼採訪中引起爭議的一行。

哈希表的另一個常見實現（除了鏈表）是使用BST作爲基礎數據結構。

我知道這個問題之前已經被問過......這很混亂，因爲每個人都給出了兩個不同的答案。例如

Why implement a Hashtable with a Binary Search Tree?

在這個職位最高的投票回答說，援引上述聲明是說在談論使用二叉搜索樹的哈希表的實現，沒有底層陣列。我明白，由於插入的每個元素都有一個散列值（一個整數），因此這些元素構成一個總的順序（每個元素都可以與<和>進行比較）。因此，我們可以簡單地使用二叉搜索樹來保存散列表的元素。

在另一方面，也有人說

Hash table - implementing with Binary Search Tree

書上說，我們應該處理衝突與二叉​​搜索樹。所以有一個底層陣列，當發生衝突時，因爲多個元素獲得相同的散列值並被放置在陣列中的同一個插槽中，這就是BST進入的位置。

因此，陣列中的每個插槽將是一個BST，它保存具有相同散列值的元素。

我傾向於第二篇文章的論點，因爲第一篇文章沒有真正解釋哈希表的這種實現如何處理衝突。我不認爲它可以實現預期的O（1）插入/刪除/查找時間。

但是對於第二篇文章，如果我們有多個獲得相同散列值並放置在BST中的元素，我不確定這些元素是如何排序的（它們如何相互比較？）

請幫助我一勞永逸地解決這個問題！

Answer 1

後的第一次並沒有真正解釋這種實現一個哈希表如何處理衝突

隨着BST，您可以使用，將不產生重複鍵散列函數所以就沒有碰撞。這樣做的好處並不是速度，而是爲了減少內存消耗，並有更好的最壞情況保證。如果您正在爲關鍵實時系統編寫軟件，則可能無法容忍O（n）調整哈希表的大小。

如果我們有得到相同的哈希值，並放置在BST多個元素，我不知道這些元素是如何排序（他們怎麼能對相互比較？）

用另一個函數重試。最後，這一切都取決於你的數據結構的用途（內存與速度更重要嗎？攤銷性能還是最壞情況性能更重要？等等。）