How to implement a hash table using a BST?

Question

Another common implementation(besides linked-list) for a hash table is to use a BST as the underlying data structure.
I've searched the web and SO but can't find the answer. How do I implement a Hashtable using a Binary Search Tree? 's answer just like wrapping the BST into a hash table, I don't think that means implementing hash table using a BST.

Please show me the codes for put() and get() method.

What do you mean by that? Using buckets with a BST for collision resolution instead of a linked list? Also, "show me the codes" is instantly off-topic here. You're expected to show what you've tried, where you're stuck, what you've researched, etc. — user395760
– user395760, Commented Sep 21, 2013 at 9:57
Included in java 8: Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class. — Ritesh
– Ritesh, Commented Dec 20, 2015 at 21:28
I have added an answer here, hope this helps: stackoverflow.com/questions/17279805/… — Prabhash Rathore
– Prabhash Rathore, Commented Feb 13, 2016 at 15:15

Nir Alfasi · Accepted Answer · 2013-10-13 05:27:02Z

2

The answer is that you simply can't!

The insert/find time in a BST is O(log n) while in HashTable it should be O(1)

UPDATE:
Now after I looked at the book...
Bin you missed what Gayle was referring to - the original question was:

Design and implement a hash table which uses chaining (linked lists) to handle collisions

then at the end of the answer it says

Another common implementation(besides linked-list) for a hash table is to use a BST as the underlying data structure.

It refers to the same thing as the original question: the use of BST is only when collisions occur, which means that the buckets part will be implemented as BST/List not the hash-map itself!

edited Oct 13, 2013 at 5:27

answered Sep 21, 2013 at 9:50

Nir Alfasi

53.6k11 gold badges94 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Bin Over a year ago

Yes, I agree with you, I read this in a book named <Cracking the Coding Interview>, the words are : Another common implementation for a hash table is to use a BST as the underlying data structure. Retrieving an element will no longer be O(1), but it prevents us from creating an unnecessarily large array to hold items. So, @alfasin how do you think about it ?

Nir Alfasi Over a year ago

I have the 4th edition of the book and couldn't find such a question, can you direct me to the chapter/page ?

Bin Over a year ago

mine is the 5th edition, Chapter 8 Object-Oriented Design --> question 10

Nir Alfasi Over a year ago

Not there in the 4th addition, anyways, this book has the answers too ;)

Akh Over a year ago

@alfasin. Thank you :) I meant the no of items in the same bucket incase of hash collision. My bad. Should have referred it as M.

|

Collectives™ on Stack Overflow

How to implement a hash table using a BST?

1 Answer 1

11 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related