Is set.pop() deterministic?

by

The answer in general is no. The python source that @Christophe and @Marcin (un)helpfully point to shows that elements are popped in the order they appear in the hash table. So, pop order (and presumably iteration order) is deterministic, but only for fixed hash values.
That’s the case for numbers but not for strings, according to the Note in the documentation of __hash__, which incidentally also touches on your question directly:

Note by default the hash() values of str, bytes and datetime objects are “salted” with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.

[ … ]

Changing hash values affects the iteration order of dicts, sets and other mappings. Python has never made guarantees about this ordering (and it typically varies between 32-bit and 64-bit builds).

Edit: As @Marcin points out, the link I quoted does not apply to Python 2.
Hash randomization became the default with Python 3.3. Python 2.7 does not have intentionally non-deterministic string hashing by default.

In general, this is a problem for any object whose hash is not a repeatable function of its value (e.g., if the hash is based on memory address). But conversely, if you define your own __hash__ method for the objects in your sets, you can expect that they will be returned in a reproducible order. (Provided the set’s history and the platform are kept fixed).

More Related Contents:

  1. Converting a list to a set changes element order
  2. How to get all subsets of a set? (powerset)
  3. Python Sets vs Lists
  4. Python -Intersection of multiple lists?
  5. In Python, when to use a Dictionary, List or Set?
  6. How can I create a Set of Sets in Python?
  7. Time complexity of python set operations?
  8. Empty set literal?
  9. How to construct a set out of list items in python?
  10. Find sets of disjoint sets from a list of tuples or sets in python
  11. How to make a set of lists
  12. Is python’s “set” stable?
  13. What is the difference between sets and lists in Python?
  14. Get unique values in List of Lists
  15. What is time complexity of a list to set conversion?
  16. Fastest way to search a list in python
  17. Understanding the set() function
  18. set of list of lists in python
  19. Access the sole element of a set [duplicate]
  20. How to create the union of many sets using a generator expression?
  21. A set union find algorithm
  22. Python, subclassing immutable types
  23. Python’s and Numpy’s nan and set
  24. How to retrieve an element from a set without removing it?
  25. Elegant way to remove items from sequence in Python? [duplicate]
  26. Type error Unhashable type:set
  27. Why does a set display in same order if sets are unordered?
  28. add object into python’s set collection and determine by object’s attribute
  29. Find non-common elements in lists
  30. Can Python’s set absence of ordering be considered random order?

Leave a Comment