How to improve performance of a hashtable with 1 million elements and 997 buckets?

Question

This is an interview question.

Suppose that there are 1 million elements in the table and 997 buckets of unordered lists. Further suppose that the hash function distributes keys with equal probability (i.e., each bucket has 1000 elements).

What is the worst case time to find an element which is not in the table? To find one which is in the table? How can you improve this?

My solution: The worst case time of finding an element not in table and in table are all O(1000). 1000 is the length of the unsorted list.

Improve it : (0) straightforward, increase bucket numbers > 1 million. (1) each bucket holds a second hashtable, which use a different hash function to compute hash value for the second table. it will be O(1) (2) each bucket holds a binary search tree. It will be O(lg n).

is it possible to make a trade-off between space and time. Keep both of them in a reasonable range.

Any better ideas ? thanks !

Answer 1

The simplest and most obvious improvement would be to increase the number of buckets in the hash table to something like 1.2 million -- at least assuming your hash function can generate numbers in that range (which it typically will).