Chapter Objectives

Many applications require a dynamic set that supports only the dictionary operations
INSERT, SEARCH, and DELETE. Example: a symbol table in a compiler.

A hash table is effective for implementing a dictionary.

• The expected time to search for an element in a hash table is O(1), under some
  reasonable assumptions.
• Worst-case search time is Θ(n), however.

A hash table is a generalization of an ordinary array.

• With an ordinary array, we store the element whose key is k in position k of the array.
• Given a key k, we find the element whose key is k by just looking in the kth
  position of the array. This is called direct addressing.
• Direct addressing is applicable when we can afford to allocate an array with
  one position for every possible key.

We use a hash table when we do not want to (or cannot) allocate an array with one
position per possible key.

• Use a hash table when the number of keys actually stored is small relative to the number of possible keys.
• A hash table is an array, but it typically uses a size proportional to the number of keys to be stored (rather than the number of possible keys).
• Given a key k, don’t just use k as the index into the array.
• Instead, compute a function of k, and use that value to index into the array. We call this function a hash function.

Issues that we’ll explore in hash tables:

• How to compute hash functions. We’ll look at the multiplication and division methods.
• What to do when the hash function maps multiple keys to the same table entry. We’ll look at chaining and open addressing.