CS 503 Quiz 6

CS 503, Advanced Programming I

Quiz 6, 18 April 2007

Large load factors are bad. Are small load factors bad too? Explain.
Yes, but less so than large load factors. Small load factors indicate that the scatter table is being underused and possibly wasting space.
In dynamic hash tables it may be sensible to organize chains as binary search trees. Does it make sense to do so if the hash table is static?
Yes: If the chains are long, then organizing them into binary search trees my reduce the worst-case search time to odrlgn(). No: If the chains are long enough to make using binary search trees sensible, then the hash table has too many elements and should be resized (or else the hash function isn't uniform and should be replaced).
A good, general-purpose hash function is supposed to be both uniform and random. Give an example of a hash function that is random but not uniform. Explain how your bad hash function can cause performance problems. Don't forget to state your assumptions.
Assuming the key is an unsigned integer, the hash function
```
unsigned hash(unsigned k)
  return ((k*k) & 0x100) >> 2
```
returns a random bit. Unless the scatter table has two buckets, hash() is random but not uniform.
An open-address hash table using hash() will have clusters; a chained hash table using hash() will have only two chains. In either case, search performance will quickly degrade to O(n).
What is the ideal load factor for a open-addressed hash table? Explain.
The ideal load factor would be 0.5, meaning that half the table was occupied. A smaller load factor suggests the table is too big, while a larger load factor suggests the table is too small.
However, this answer depends on the hash function being uniform with empty and full buckets interspersed evenly. If the hash function is non-uniform, all the occupied buckets could appear as a single cluster, producing worst-case performance.

This page last modified on 27 April 2006.