12 Dictionaries and hash tables: How to build and use associative arrays
In this chapter
- Discovering how the dictionary ADT improves indexing
- Implementing a dictionary with the data structures we already know
- Introducing a new data structure, the hash table, a game changer for dictionaries
- How hashing works
- Comparing chaining and open addressing, two strategies to resolve conflicts
So far in this book we have discussed data structures that allow you to retrieve stored data based on the position of elements. For arrays and linked lists, we can retrieve elements based on their position in the data structure. For stacks and queues, the next element we can retrieve is at a specific position.
Now, we introduce key-based data structures, sometimes called associative arrays. This chapter also introduces the dictionary, the epitome of key-based abstract data types, followed by a discussion of efficient implementation strategies for retrieving elements by key.
The dictionary problem
Our little friend Mario is getting really serious about collecting baseball cards. Do you know what his favorite part is? Trading cards with his friends!
Mario has a good memory, but now that he has hundreds of cards, it’s hard for him to remember all the cards he already owns and the ones he’s missing. Especially since when he trades with his friends, he only has a few moments to claim a card, before someone else takes it.