Grokking Data Structures

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 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 ...