Describe why a very large hash table will likely increase the performance (i.e. faster additions and lookup) at the expense of wasting memory, and vice versa, why a small hash table will use less memory but result in a decrease in performance.

Question

What will be an ideal response?

Answer 1

A larger hash table decreases the chance of a collision. At every collision point we
end up performing a linear search through a linked list. In the worst case, if every
item hashed to the same number we would store everything in a single linked list. In
the best case the hash table is large enough so that only a single item is stored at every
hash location.