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 we are examining, the basic dictionary classes are based on hash tables by default. The general concept of a hash table based dictionary is that mapping for a specified key is stored at an index of an array, where the index is obtained by applying...