Everyday Data Structures

Advanced topics

Now that we have examined how dictionaries are used in common applications, we should take some time to examine how dictionaries are implemented under the hood. The majority of dictionaries come in two distinct flavors: hash table based and search tree based. Although the mechanics of the two approaches are similar, and they typically share many of the same methods and functionality, the inner workings and ideal applications for each type are very different.

Hash table based dictionaries

The most common implementation of a dictionary is the hash table based associative array. When properly implemented, the hash table approach is extremely efficient and allows for O(1) complexity searches, inserts, and deletes. In each of the languages ...