Everyday Data Structures

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