Problem
Suppose that each entry in a hash table occupies s words of storage (exclusive of the pointer member needed if chaining is used), where we take one word as the amount of space needed for a pointer. Also suppose that there are n occupied entries in the hash table, and the hash table has a total of t possible positions (t is the same as hash_size), including occupied and empty positions.
(a) If open addressing is used, determine how many words of storage will be required for the hash table. (b) If chaining is used, then each node will require s + 1 words, including the pointer member. How many words will be used altogether for the n nodes?
(c) If chaining is used, how many words will be used for the hash table itself? (Recall that with chaining the hash table itself contains only pointers requiring one word each.)
(d) Add your answers to the two previous parts to find the total storage requirement for chaining.
(e) If s is small (that is, the entries have a small size), then open addressing requires less total memory for a given load factor λ = n/t , but for large s (large entries), chaining requires less space altogether. Find the break-even value for s , at which both methods use the same total storage. Your answer will be a formula for s that depends on the load factor λ, but it should not involve the numbers t or n directly.
(f) Evaluate and graph the results of your formula for values of λ ranging from 0.05 to 0.95.