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 sets are used in common applications, we should take some time to examine how they are implemented under the hood. The majority of sets come in three varieties: hash table-based sets, tree-based sets, and array-based sets.

Hash table-based sets

Hash table-based sets are typically used for unordered collections of data. As such, the majority of sets you will encounter for non-specialized applications will be hash table-based. Hash table-based sets share similar operational costs with dictionaries. For example, search, insert, and delete operations all have an operational cost of O(n).

Tree-based sets

Tree-based sets are typically based on binary search trees, but they sometimes can be based on other structures. ...

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