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 that is a game changer for dictionaries—the hash table
- how hashing works
- comparing chaining and open addressing, two strategies for resolving conflicts
So far, we have discussed data structures that allow us 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 that can be retrieved 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!