Странный набор Python и поведение хэша - как это работает?

Question

У меня есть класс с именем GraphEdge, который я хотел бы однозначно определить в наборе (встроенный тип set) с помощью его членов tail и head, которые устанавливаются через __init__ .

Если я не определю __hash__, я вижу следующее поведение:

>>> E = GraphEdge('A', 'B')
>>> H = GraphEdge('A', 'B')
>>> hash(E)
139731804758160
>>> hash(H)
139731804760784
>>> S = set()
>>> S.add(E)
>>> S.add(H)
>>> S
set([('A', 'B'), ('A', 'B')])

Множество не может знать, что E и H одинаковы по моему определению, поскольку они имеют различные хэши (которые, как мне известно, использует тип набора для определения уникальности), поэтому он добавляет оба как отдельные элементы. Поэтому я определяю довольно наивную хеш-функцию для GraphEdge примерно так:

def __hash__( self ):
    return hash( self.tail ) ^ hash( self.head )

Теперь вышеприведенное работает как положено:

>>> E = GraphEdge('A', 'B')
>>> H = GraphEdge('A', 'B')
>>> hash(E)
409150083
>>> hash(H)
409150083
>>> S = set()
>>> S.add(E)
>>> S.add(H)
>>> S
set([('A', 'B')])

Но ясно, что ('A', 'B') и ('B', 'A') в этом случае вернут один и тот же хеш, поэтому я ожидаю, что не смогу добавить ('B', 'A') к набору, уже содержащему ('A', 'B'). Но это не то, что происходит:

>>> E = GraphEdge('A', 'B')
>>> H = GraphEdge('B', 'A')
>>> hash(E)
409150083
>>> hash(H)
409150083
>>> S = set()
>>> S.add(E)
>>> S.add(H)
>>> S
set([('A', 'B'), ('B', 'A')])

Так что тип набора использует хэш или нет? Если так, как возможен последний сценарий? Если нет, то почему не работает первый сценарий (без определения __hash__)? Я что-то упустил?

Редактировать: Для справки для будущих читателей, я уже определил __eq__ (также на основе tail и head).

Answer 1

У вас есть столкновение хешей. При столкновении хэшей набор использует оператор == для проверки, действительно ли они равны друг другу.

Answer 2

Важно понимать, как хэш и == работают вместе, потому что оба используются наборами. Для двух значений x и y важное правило таково:

x == y ==> hash(x) == hash(y)

(х равно у означает, что хэши х и у равны). Но обратное неверно: два неравных значения могут иметь одинаковый хэш.

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

Answer 3

Вы должны всегда определять и __eq__(), и __hash__(), если вам нужен хотя бы один из них.Если хеши двух объектов равны, для проверки уникальности выполняется дополнительная проверка __eq__().