哈希表的另一种常见实现方式(除了链表)是使用 BST 作为底层数据结构。
我已经在网上搜索过,但找不到答案。 How do I implement a Hashtable using a Binary Search Tree?的答案就像将 BST 包装到哈希表中一样,我认为这并不意味着使用 BST 实现哈希表。
请告诉我 put()
和 get()
方法的代码。
最佳答案
答案是你根本做不到!
BST 中的插入/查找时间是 O(log n) 而在 HashTable 中应该是 O(1)
更新:
现在看了书后...
Bin 你错过了 Gayle 所指的内容 - 最初的问题是:
Design and implement a hash table which uses chaining (linked lists) to handle collisions
然后在答案的最后说
Another common implementation(besides linked-list) for a hash table is to use a BST as the underlying data structure.
它指的是与原始问题相同的事情:仅当发生冲突时才使用 BST,这意味着 buckets 部分将实现为 BST/List 而不是 hash-map 本身!
关于java - 如何使用 BST 实现哈希表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18931126/