Как python вычисляет хэш кортежа

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

В этом примере,

a = (1, [1,2])
hash(a)

Он ошибочно говорит, что список раскалывается. Поэтому я думаю, что это не вычисляется по id, или, вероятно, есть проверка того, является ли элемент изменчивым.

Теперь посмотрим на этот пример

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

Здесь оказывается, что хэш ta не изменяется с модификацией его элемента, т. a0. Так может быть, a0 id используется для расчета хэша? Является ли a0 каким-то образом считаемым неизменным? Как python знает, является ли тип изменчивым?

Теперь рассмотрим этот случай

b = (1, 2)
id(b)  # 3980742764
c = (1, 2)
id(c)  # 3980732588
tb = (1, b)
tc = (1, c) 
hash(tb)  # -1383040070
hash(tc)  # -1383040070

Кажется, что содержание b и c используется для вычисления хэша.

Как я должен понимать эти примеры?

Ответ 1

Ни. Он рассчитывается на основе хэшей этих элементов, а не содержимого (значений).

Взгляните на этот параграф в глоссарии документации python.

Что-то хешируется или нет, и как оно хэшируется, зависит от реализации его метода .__hash__(). Сам Python понятия не имеет о изменчивости объекта.

В вашем первом примере tuple происходит с самим хешем на основе его элементов, в то время как list не имеет хеша вообще - метод .__hash__() не используется для него (и по уважительной причине). Вот почему tuple с объектом list внутри него не хешируется.

Теперь, имея это в виду, давайте взглянем на документацию модели данных python и что она должна сказать по теме:

По умолчанию пользовательские классы имеют __eq__() и __hash__(); с ними все объекты сравниваются неравномерно (кроме самих себя) и x.__hash__() возвращает соответствующее значение, так что x == y подразумевает, что x is y и hash(x) == hash(y).

Вот почему вам не нужно определять .__hash__() для ваших классов - python делает это для вас в этом случае. Однако реализация по умолчанию не использует поля экземпляра в учетной записи. Поэтому вы можете изменять значения внутри вашего объекта, не изменяя его хэш.

В этом отношении вы правы - реализация по умолчанию (CPython) хеширования для пользовательских классов основана на id() объекта, а не на значениях внутри него. Это деталь реализации, но она отличается от версий Python. В более поздних версиях Python связь между hash() и id() связана с некоторой рандомизацией.

Но как это на самом деле хеш?

Хотя детали довольно сложны и, вероятно, связаны с некоторой продвинутой математикой, реализация хеш-функции для кортежных объектов записывается на C и может быть видна здесь (см. static Py_hash_t tuplehash(PyTupleObject *v).

Расчет включает в себя XORing константу с хэшами каждого из элементов кортежа. Строка, отвечающая за хэширование элементов, такова:

y = PyObject_Hash(*p++);

Итак, чтобы ответить на ваш первоначальный вопрос: он делает кучу XOR hokus-pocus с хэшами каждого из своих элементов. Независимо от того, используется ли содержимое этих элементов, зависит их специфические хэш-функции.

Ответ 2

Основной контракт хэширования состоит в том, что равные объекты имеют равные хэши. В частности, хеширование непосредственно не заботится о изменчивости или мутации; он заботится только о мутации, которая влияет на сопоставления равенства.

Ваш первый кортеж не сотрясается, потому что мутация вложенного списка изменит поведение кортежа при сравнении равенств.

Мутация a0 во втором примере не влияет на хэш кортежа, потому что это не влияет на сопоставления равенства. a0 все еще только равен самому себе, а его хэш не изменяется.

tb и tc в вашем третьем примере имеют равные хэши, потому что они равны кортежам, независимо от того, являются ли их элементы одними и теми же объектами.

Все это означает, что кортежи не могут (напрямую) использовать id для хэшей. Если бы они это сделали, одинаковые кортежи с четкими, но равными элементами могли бы хешировать по-разному, нарушая контракт хэширования. Без специальных типов элементов, единственные кортежи, которые могут использоваться для вычисления собственных хэшей, являются хешами их элементов, поэтому кортежи основывают свои хэши на хэшах своих элементов.

Ответ 3

Ответ на вопрос "Является ли хеш кортежа вычисляемым на основе идентичности или значения?" is: Ни то, ни другое.

Правильный ответ заключается в том, что хеш кортежа вычисляется из хэшей элементов. Как рассчитываются эти хэши, (более или менее) не имеет значения.

Простой способ доказать это - увидеть, что происходит, когда вы помещаете список в кортеж:

>>> hash( (1, 2) )
3713081631934410656
>>> hash( (1, []) )
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Поскольку списки не хешируются, кортеж, содержащий список, также не является хешируемым.

Давайте более подробно рассмотрим этот пример, который вы привезли:

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

Почему установка a0.x = 20 влияет на хеш кортежа? Ну, если мы модифицируем этот код для вывода хэша a0, вы увидите, что установка a0.x = 20 не влияет на значение хеша a0:

a0 = A()
print(hash(a0))  # -9223363274645980307
a0.x = 20
print(hash(a0))  # -9223363274645980307

Причиной этого является то, что python реализует хэш-функцию по умолчанию для вас. Из документов:

По умолчанию пользовательские классы имеют __eq__() и __hash__(); с ними все объекты сравниваются неравномерно (кроме самих себя) и x.__hash__() возвращает соответствующее значение, так что x == y подразумевает, что x is y и hash(x) == hash(y).

Хэш-функция по умолчанию игнорирует атрибуты объекта и вычисляет хэш на основе идентификатора объекта. Независимо от того, какие изменения вы внесете в a0, его хэш всегда останется прежним. (Хотя можно определить пользовательскую хэш-функцию для экземпляров вашего класса A, реализовав собственный метод __hash__.)

Добавление: причина, по которой списки не хешируются, заключается в том, что они изменяемы. Из документов:

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

Списки попадают в эту категорию.

Ответ 4

хэш tuple основан на содержимом, а не на _id_s кортежей. И хеши вычисляются рекурсивно: если один элемент не хешируется (например, элемент list), то сам кортеж не является хешируемым.

Это совершенно нормально, если a и b являются кортежами и a == b, то hash(a) == hash(b) (если хэши можно вычислить, конечно), даже если a is not b.

(напротив, hash(a) == hash(b) не означает, что a == b)

Информация, передаваемая с помощью is часто не очень полезно, так как питон объекта интернируя, например.