COS 226 Exercises on Hashing

1. [Exercise 14.47, revised] For 10 million integer keys, compute the hash table size that makes each of the three hashing methods (separate chaining, linear probing, and double hashing) use the same number of key comparisons as BSTs for a search miss, on the average, counting the hash function computation as a comparison.

2. [Exercise 14.48, revised] For 10 million integer keys, compute the number of comparisons for each of the three hashing methods (separate chaining, linear probing, and double hashing) for a search miss, on the average, when they can use a total of 30 million words of memory (as BSTs would).