Is python's "set" stable?

user_168465 0
Viewed 10743

The question arose when answering to another SO question (there).

When I iterate several times over a python set (without changing it between calls), can I assume it will always return elements in the same order? And if not, what is the rationale of changing the order ? Is it deterministic, or random? Or implementation defined?

And when I call the same python program repeatedly (not random, not input dependent), will I get the same ordering for sets?

The underlying question is if python set iteration order only depends on the algorithm used to implement sets, or also on the execution context?

set python
7 Answers

A set or frozenset is inherently an unordered collection. Internally, sets are based on a hash table, and the order of keys depends both on the insertion order and on the hash algorithm. In CPython (aka standard Python) integers less than the machine word size (32 bit or 64 bit) hash to themself, but text strings, bytes strings, and datetime objects hash to integers that vary randomly; you can control that by setting the PYTHONHASHSEED environment variable.

From the __hash__ docs:

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.

This is intended to provide protection against a denial-of-service caused by carefully-chosen inputs that exploit the worst case performance of a dict insertion, O(n^2) complexity. See http://www.ocert.org/advisories/ocert-2011-003.html for details.

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

See also PYTHONHASHSEED.

The results of hashing objects of other classes depend on the details of the class's __hash__ method.

The upshot of all this is that you can have two sets containing identical strings but when you convert them to lists they can compare unequal. Or they may not. ;) Here's some code that demonstrates this. On some runs, it will just loop, not printing anything, but on other runs it will quickly find a set that uses a different order to the original.

from random import seed, shuffle

seed(42)

data = list('abcdefgh')
a = frozenset(data)
la = list(a)
print(''.join(la), a)

while True:
    shuffle(data)
    lb = list(frozenset(data))
    if lb != la:
        print(''.join(data), ''.join(lb))
        break

typical output

dachbgef frozenset({'d', 'a', 'c', 'h', 'b', 'g', 'e', 'f'})
deghcfab dahcbgef
user_40149590

The answer is simply a NO.

Python set operation is NOT stable.

I did a simple experiment to show this.

The code:

import random
random.seed(1)

x=[]
class aaa(object):
    def __init__(self,a,b):
        self.a=a
        self.b=b

for i in range(5):
    x.append(aaa(random.choice('asf'),random.randint(1,4000)))

for j in x:
    print(j.a,j.b)

print('====')
for j in set(x):
    print(j.a,j.b)

Run this for twice, you will get this:

First time result:

a 2332
a 1045
a 2030
s 1935
f 1555
====
a 2030
a 2332
f 1555
a 1045
s 1935

Process finished with exit code 0

Second time result:

a 2332
a 1045
a 2030
s 1935
f 1555
====
s 1935
a 2332
a 1045
f 1555
a 2030

Process finished with exit code 0

The reason is explained in comments in this answer.

However, there are some ways to make it stable:

user_59186960
Related