Chapter 10. Hashing and Symbol Tables

We have previously looked at lists, where items are stored in sequence and accessed by index number. Index numbers work well for computers. They are integers so they are fast and easy to manipulate. However, they don't always work so well for us. If we have an address book entry, for example, with index number 56, that number doesn't tell us much. There is nothing to link a particular contact with number 56. It just happens to be the next available position in the list.

In this chapter, we are going to look at a similar structure: a dictionary. A dictionary uses a keyword instead of an index number. So, if that contact was called James, we would probably use the keyword James to locate the contact. That is, instead of accessing the contact by calling contacts [56], we would use contacts ["james"].

Dictionaries are often built using hash tables. As the name suggests, hash tables rely on a concept called hashing. That is where we are going to begin our discussion...