O'Reilly logo

Everyday Data Structures by William Smith

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required