‘order’ of unordered Python sets

by

You should watch this video (although it is CPython1 specific and about dictionaries — but I assume it applies to sets as well).

Basically, python hashes the elements and takes the last N bits (where N is determined by the size of the set) and uses those bits as array indices to place the object in memory. The objects are then yielded in the order they exist in memory. Of course, the picture gets a little more complicated when you need to resolve collisions between hashes, but that’s the gist of it.

Also note that the order that they are printed out is determined by the order that you put them in (due to collisions). So, if you reorder the list you pass to set_2, you might get a different order out if there are key collisions.

For example:

list1 = [8,16,24]
set(list1)        #set([8, 16, 24])
list2 = [24,16,8]
set(list2)        #set([24, 16, 8])

Note the fact that the order is preserved in these sets is “coincidence” and has to do with collision resolution (which I don’t know anything about). The point is that the last 3 bits of hash(8), hash(16) and hash(24) are the same. Because they are the same, collision resolution takes over and puts the elements in “backup” memory locations instead of the first (best) choice and so whether 8 occupies a location or 16 is determined by which one arrived at the party first and took the “best seat”.

If we repeat the example with 1, 2 and 3, you will get a consistent order no matter what order they have in the input list:

list1 = [1,2,3]
set(list1)      # set([1, 2, 3])
list2 = [3,2,1]
set(list2)      # set([1, 2, 3])

since the last 3 bits of hash(1), hash(2) and hash(3) are unique.

1Note The implementation described here applies to CPython dict and set. I think that the general description is valid for all modern versions of CPython up to 3.6. However, starting with CPython3.6, there is an additional implementation detail that actually preserves the insertion order for iteration for dict. It appears that set still do not have this property. The data structure is described by this blog post by the pypy folks (who started using this before the CPython folks). The original idea (at least for the python ecosystem) is archived on the python-dev mailing list.

More Related Contents:

  1. Why is “1000000000000000 in range(1000000000000001)” so fast in Python 3?
  2. How does the @property decorator work in Python?
  3. What’s with the integer cache maintained by the interpreter?
  4. About the changing id of an immutable string
  5. Why does id({}) == id({}) and id([]) == id([]) in CPython?
  6. When is del useful in Python?
  7. How does swapping of members in tuples (a,b)=(b,a) work internally?
  8. How does asyncio actually work?
  9. How to override the copy/deepcopy operations for a Python object?
  10. Two variables in Python have same id, but not lists or tuples
  11. How do chained comparisons in Python actually work?
  12. time.sleep — sleeps thread or process?
  13. Python string with space and without space at the end and immutability
  14. Python Compilation/Interpretation Process
  15. Is there anything faster than dict()?
  16. When are .pyc files refreshed?
  17. Integer File Descriptor “0” in open()
  18. Why do two identical lists have a different memory footprint?
  19. What algorithm does Python’s built-in sort() method use?
  20. Why does list ask about __len__?
  21. How is super() in Python 3 implemented?
  22. Why is copying a shuffled list much slower?
  23. How exactly is Python Bytecode Run in CPython?
  24. Improving performance of very large dictionary in Python
  25. Why does creating a list from a list make it larger?
  26. Runtime of python’s if substring in string
  27. Why is a function/method call in python expensive?
  28. How does str(list) work?
  29. How does the Python for loop actually work?
  30. ‘is’ operator behaves unexpectedly with floats

Leave a Comment