Hash table fundamentals
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...
