Most developers have experience with hash tables in some form, as nearly all programming languages include hash table implementations. Hash tables store data by applying a `hash`

function to the object, which determines its placement in an underlying array.

While a detailed description of hashing algorithms is out of scope of this book, it is sufficient for you to understand that a `hash`

function simply maps any input data object (which might be any size) to some expected output. While the input might be large, the output of the `hash`

function will be a fixed number of bits.

In a typical hash table design, the result of the `hash`

function is divided by the number of array slots; the remainder then becomes the assigned slot number. Thus, the slot can be computed using *hash(o) % n*, where *o* is the object and *n* is the number of slots. Consider the following hash table with names as keys and addresses as values:

In the preceding diagram, the values in the table on the left represent...