Hash based data structures: set, dict, counter
Learn how set and dict works. Counter data structure
Hash Structures: set and dict
Both set and dict are built on a hash table under the hood. This gives them O(1) average time for insertion, deletion, and lookup — regardless of how many elements they contain. This is their biggest advantage over lists.
set
A set is an unordered collection of unique values. Duplicates are automatically discarded.
Creating a Set
Basic Operations
| Operation | Method | Complexity |
|---|---|---|
| Add | add(x) | O(1) |
| Remove | remove(x) | O(1) |
| Lookup | x in s | O(1) |
| Size | len(s) | O(1) |
Compare this to a list where x in lst is O(n). For large collections with frequent lookups, a set is dramatically faster.
Sets are Unordered
Elements have no guaranteed order — you cannot access by index:
Difference from C++ std::set
In C++, std::set stores elements in sorted order and uses a balanced BST internally — operations are O(log n). Python's uses a hash table — operations are O(1) average but the elements are . If you need sorted unique elements in Python, use when you need to iterate in order.