How is set() implemented?

by

According to this thread:

Indeed, CPython’s sets are implemented as something like dictionaries
with dummy values (the keys being the members of the set), with some
optimization(s) that exploit this lack of values

So basically a set uses a hashtable as its underlying data structure. This explains the O(1) membership checking, since looking up an item in a hashtable is an O(1) operation, on average.

If you are so inclined you can even browse the CPython source code for set which, according to Achim Domma, was originally mostly a cut-and-paste from the dict implementation.

Note: Nowadays, set and dict‘s implementations have diverged significantly, so the precise behaviors (e.g. arbitrary order vs. insertion order) and performance in various use cases differs; they’re still implemented in terms of hashtables, so average case lookup and insertion remains O(1), but set is no longer just “dict, but with dummy/omitted keys”.

More Related Contents:

  1. Python Sets vs Lists
  2. In Python, when to use a Dictionary, List or Set?
  3. Time complexity of python set operations?
  4. Are sets ordered like dicts in python3.6
  5. How is tuple implemented in CPython?
  6. Why don’t Python sets preserve insertion order?
  7. How do I sort a list of dictionaries by a value of the dictionary?
  8. What would a “frozen dict” be?
  9. How can I create a Set of Sets in Python?
  10. How to convert SQL Query result to PANDAS Data Structure?
  11. Why (0-6) is -6 = False? [duplicate]
  12. Why do -1 and -2 both hash to -2 in CPython? [duplicate]
  13. What do I use for a max-heap implementation in Python?
  14. How can I extract a single value from a JSON response?
  15. List of all unique characters in a string?
  16. Python string with space and without space at the end and immutability
  17. Find sets of disjoint sets from a list of tuples or sets in python
  18. How to make a set of lists
  19. Get unique values in List of Lists
  20. What is time complexity of a list to set conversion?
  21. Nested list comprehension scope
  22. Understanding the set() function
  23. How to make a dictionary that returns key for keys missing from the dictionary instead of raising KeyError?
  24. set of list of lists in python
  25. Access the sole element of a set [duplicate]
  26. Is a variable swap guaranteed to be atomic in python?
  27. Adding counters deletes keys
  28. A set union find algorithm
  29. Python, subclassing immutable types
  30. How to retrieve an element from a set without removing it?

Leave a Comment