A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Hash Tables

Most programming languages include a data structure called a hash table, and it has an amazing superpower: fast reading. Note that hash tables are called by different names in various programming languages. Other names include hashes, maps, hash maps, dictionaries, and associative arrays.

Here’s an example of the menu as implemented with a hash table using Ruby:

menu = { "french fries" => 0.75, "hamburger" => 2.5,
"hot dog" => 1.5, "soda" => 0.6 }

A hash table is a list of paired values. The first item in each pair is called the key, and the second item is called the value. In a hash table, the key and value have some significant association with one another. In this example, the string, "french fries" is the key, and ...