Как определяется порядок элементов, возвращаемых списком (frozenset())?

Question

У меня есть следующая примерная установка в Python:

a = list(frozenset(['haha', 'lol']))
b = list(frozenset(['lol', 'haha']))

Есть ли

a == b

всегда возвращать True?

Возможно ли, что список заморозок из тех же элементов может вернуть False с вышеуказанной настройкой?

Answer 1

Семантика эквивалентности между (замороженными) наборами заключается в том, что если они содержат эквивалентные элементы, они эквивалентны. Наборы не имеют порядка.

Но, поскольку списки имеют порядок, приведение к списку потенциально может привести к тому, что они не будут эквивалентны (зависит от порядка итерации по (замороженному) набору - что является подробностью реализации).

Вот пример коллизии во внутренней реализации, которая вызывает другой порядок итераций из-за порядка внедрения (это в реализации CPython):

>>> a = list(frozenset([1, 9]))
>>> b = list(frozenset([9, 1]))
>>> a == b
False

Пример со строками:

Сначала нужно найти столкновение (я не буду вдаваться в подробности):

>>> hash('1') % 8
0
>>> hash('2') % 8
5
>>> hash('3') % 8
2
>>> hash('4') % 8
3
>>> hash('5') % 8
1
>>> hash('6') % 8
4
>>> hash('7') % 8 
5  # same as '2' ! Found!

Теперь нам нужно добавить в набор в другом порядке, чтобы вызвать повторный хеш (опять же, не вдаваясь в детали):

>>> s1, s2 = '2', '7'
>>> a = list(frozenset([s1, s2]))
>>> b = list(frozenset([s2, s1]))
>>> a == b
False