CODEWITHSUNDEEP
data-structureshashtable
theomega
theomega

Reputation: 32051

How to implement a HashTable using a HashSet

I was asked the following interview-question:

Suppose you have a HashSet implementation providing its ordinary interface. How can you use one or more instances of HashSet to implement a HashTable providing the ordinary HashTable interface it its ordinary time constraints?

I asked twice, but they meant it this way and not the other way around (implementing a HashSet using a HashTable is quite simple, Java does this for example).

I answered that it was not possible. This answer did not seem to statisfy the interviewer, so I am searching for a better answer. I could not find a solution, even when searching on the internet and on Stack Overflow.

I think it was a trick question, but to make sure I post this question here on SO.

Upvotes: 2

Views: 519

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

One standard way to do this is to treat the hash table as a hash set of key/value pairs, where the hash code of the key/value pair is purely the hash code of the key and the equality comparison function says that any two key/value pairs are equal precisely when their keys are equal. That way, the normal hash set operations will store key/value pairs in a way where

  • No two key/value pairs with the same key are stored, and
  • looking up the key in the hash table will find the key/value pair object with that key, from which the value can be looked up.

Hope this helps!

Upvotes: 5

Related Questions