Learning Algorithms

Chapter 3. Better Living Through Better Hashing

In this chapter, you will learn:

• How to store (key, value) pairs in a symbol table and retrieve values associated with a key.¹

• How to use an array to store (key, value) pairs for efficient search, if the size of the array is sufficiently large, compared to the number of pairs stored.

• How to use an array of linked lists to store (key, value) pairs to support the extra ability to remove a key.

• How to resize a symbol table to remain efficient.

• Amortized analysis to determine the average runtime performance when the behavior of an operation can change with successive invocations.

• How geometric resizing reduces the frequency of the costly resize operation, meaning that put() has amortized O(1) performance on average.

• How a computational hash function can uniformly distribute key values, which ensures the efficiency of the symbol table implementation.

Associating Values with Keys

Instead of just storing values, you might need to store a collection of (key, value) pairs to associate values with specific keys. This is known as a symbol table data type, which lets you find the associated value given just its key. Hashing offers an efficient alternative to manually searching through a collection from start to finish just to find a (key, value) pair. It outperforms the search algorithms I covered earlier. A symbol table can be efficient even while allowing for keys (and their values) to be removed. You give up the ability ...