如何使用BST實現哈希表？

哈希表的另一個常見實現（除了鏈表）是使用BST作爲基礎數據結構。
我搜索了網頁，所以找不到答案。 How do I implement a Hashtable using a Binary Search Tree?的答案就像將BST包裝到哈希表中一樣，我不認爲這意味着使用BST實現哈希表。如何使用BST實現哈希表？

請給我看看put()和get()方法的代碼。

來源

2013-09-21 Bin

你是什麼意思？使用具有BST的桶進行衝突解決而不是鏈接列表？此外，「向我顯示代碼」在這裏立即脫離主題。你需要展示你已經嘗試過的東西，你被困住的地方，你研究過什麼，等等。 – delnan

@Bin看到更新的答案 – alfasin

包含在java 8中：[提高java.util.HashMap的性能散列衝突條件通過使用平衡樹而不是鏈接列表來存儲映射條目。在LinkedHashMap類中實現相同的改進。]（http://openjdk.java.net/jeps/180） – Ritesh

答案是，你根本做不到！

插入/抽空在BST是O（log n）的，而在哈希表應該是O（1）

UPDATE：
現在我看着書後...
斌你錯過了什麼蓋爾指的是 - 原來的問題是：

設計並實現其使用鏈的哈希表（鏈表） 來處理衝突

然後在回答最後它說

另一種常見的實現（除鏈表）的哈希表使用BST作爲底層的數據結構。

它指的是同樣的事情，原題：使用BST的是隻有當衝突發生時，這意味着桶部分將作爲BST /列表不是哈希地圖本身來實現！

2013-09-21 09:50:21 alfasin

是的，我同意你的看法，我在一本名爲的書中讀到這樣的話，它們是：另一個常見的實現散列表將使用BST作爲基礎數據結構。檢索一個元素將不再是O（1），但它可以防止我們創建一個不必要的大數組來保存物品。所以，@alfasin你如何看待它？ – Bin

我有這本書的第4版，找不到這樣的問題，你能指導我閱讀章節/頁面嗎？ – alfasin

mine是第5版，第8章面向對象設計 - >問題10 – Bin

回答