如何使用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

回答