Почему в Python dict может быть несколько ключей с одним и тем же хешем?

Я пытаюсь понять hashфункцию Python под капотом. Я создал собственный класс, все экземпляры которого возвращают одно и то же значение хеш-функции.

class C:
    def __hash__(self):
        return 42

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

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements

Я поэкспериментировал еще немного и обнаружил, что если я переопределяю __eq__метод таким образом, что все экземпляры класса сравниваются одинаково, тогда dictразрешается только один экземпляр.

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element

Поэтому мне любопытно узнать, как у a dictможет быть несколько элементов с одним и тем же хешем.

Подробное описание того, как работает хеширование Python, см. В моем ответе на вопрос, почему ранний возврат медленнее, чем в остальном?

В основном он использует хэш для выбора слота в таблице. Если в слоте есть значение и хэш совпадает, он сравнивает элементы, чтобы увидеть, равны ли они.

Если хэш не совпадает или элементы не равны, он пробует другой слот. Есть формула для выбора этого (которую я описываю в указанном ответе), и она постепенно вытягивает неиспользуемые части хеш-значения; но как только он израсходует их все, он в конечном итоге пройдет через все слоты в хеш-таблице. Это гарантирует, что в конечном итоге мы либо найдем соответствующий элемент, либо пустой слот. Когда поиск находит пустой слот, он вставляет значение или отказывается (в зависимости от того, добавляем мы или получаем значение).

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

Вот все, что мне удалось собрать о диктатах Python (вероятно, больше, чем кто-либо хотел бы знать, но ответ исчерпывающий). Привет Дункану за то, что он указал на то, что Python использует слоты, и повел меня в эту кроличью нору.

• Словари Python реализованы в виде хеш-таблиц .
• Хеш-таблицы должны допускать хеш-коллизии, т.е. даже если два ключа имеют одинаковое хеш-значение, реализация таблицы должна иметь стратегию для однозначной вставки и извлечения пар ключ и значение.
• Python dict использует открытую адресацию для разрешения хеш-коллизий (объяснение ниже) (см. Dictobject.c: 296-297 ).
• Хеш-таблица Python - это просто непрерывный блок памяти (вроде массива, поэтому вы можете выполнять O(1)поиск по индексу).
• Каждый слот в таблице может хранить одну и только одну запись. Это важно
• Каждая запись в таблице на самом деле представляет собой комбинацию трех значений -. Это реализовано как структура C (см. Dictobject.h: 51-56 )

• Рисунок ниже представляет собой логическое представление хеш-таблицы Python. На рисунке ниже 0, 1, ..., i, ... слева - это индексы слотов в хеш-таблице (они предназначены только для иллюстративных целей и, очевидно, не хранятся вместе с таблицей!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• Когда новый dict инициализируется, он начинается с 8 слотов . (см. dictobject.h: 49 )

• При добавлении записей в таблицу мы начинаем с некоторого слота, iкоторый основан на хеш-коде ключа. CPython использует исходный i = hash(key) & mask. Где mask = PyDictMINSIZE - 1, но это не особо важно). Просто обратите внимание, что начальный слот i, который проверяется, зависит от хэша ключа.
• Если этот слот пуст, запись добавляется в слот (я имею в виду, по записи <hash|key|value>). Но что, если этот слот занят !? Скорее всего, потому что другая запись имеет такой же хеш (конфликт хешей!)
• Если слот занят, CPython (и даже PyPy) сравнивает хэш И ключ (под сравнением я имею в виду ==сравнение, а не isсравнение) записи в слоте с ключом текущей вставляемой записи ( dictobject.c: 337 , 344-345 ). Если оба совпадают, то он считает, что запись уже существует, отказывается и переходит к следующей записи, которую нужно вставить. Если хэш или ключ не совпадают, он начинает зондирование .
• Зондирование означает лишь поиск слотов по слотам в поисках пустого слота. Технически мы могли бы просто пойти один за другим, i + 1, i + 2, ... и использовать первый доступный (это линейное зондирование). Но по причинам, красиво объясненным в комментариях (см. Dictobject.c: 33-126 ), CPython использует случайное зондирование . При случайном зондировании следующий слот выбирается в псевдослучайном порядке. Запись добавляется в первый пустой слот. Для этого обсуждения фактический алгоритм, используемый для выбора следующего слота, на самом деле не важен (см. Dictobject.c: 33-126 для алгоритма проверки ). Что важно, так это то, что слоты проверяются до тех пор, пока не будет найден первый пустой слот.
• То же самое происходит и с поиском, только начинается с начального слота i (где i зависит от хеша ключа). Если и хэш, и ключ не совпадают с записью в слоте, он начинает зондирование, пока не найдет слот с совпадением. Если все слоты исчерпаны, он сообщает об ошибке.
• Кстати, размер dict будет изменен, если он будет заполнен на две трети. Это позволяет избежать замедления поиска. (см. dictobject.h: 64-65 )

Вот так! Реализация Python dict проверяет как хеш-равенство двух ключей, так и нормальное равенство ( ==) ключей при вставке элементов. Таким образом , в целом, если есть два ключа, aи bи hash(a)==hash(b), но a!=b, то оба могут гармонично существовать в Словаре Python. Но если hash(a)==hash(b) и a==b , то они не могут быть одновременно в одном слове.

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

Я предполагаю, что краткий ответ на мой вопрос: «Потому что так это реализовано в исходном коде;)»

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

Изменить : ниже ответ один из возможных способов борьбы с хэш - коллизий, это, однако , не как Python делает это. Указанная ниже вики-страница Python также неверна. Лучшим источником, приведенным ниже @Duncan, является сама реализация: https://github.com/python/cpython/blob/master/Objects/dictobject.c Прошу прощения за путаницу .

Он хранит список (или корзину) элементов в хэше, а затем выполняет итерацию по этому списку, пока не найдет фактический ключ в этом списке. Картинка говорит более тысячи слов:

Здесь вы видите, John Smithи Sandra Deeоба хешируют 152. Ковш 152содержит их обоих. При поиске Sandra Deeон сначала находит список в корзине 152, затем просматривает этот список, пока не Sandra Deeбудет найден, и вернется 521-6955.

Ниже неправильно это только здесь для контекста: On вики в Python вы можете найти код (псевдо?) , Как Python выполняет поиск.

На самом деле существует несколько возможных решений этой проблемы, ознакомьтесь со статьей в Википедии для хорошего обзора: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

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

Когда это произойдет, ваша производительность со временем будет ухудшаться, поэтому вы хотите, чтобы ваша хеш-функция была как можно более «случайной».

В потоке я не видел, что именно python делает с экземплярами определенных пользователем классов, когда мы помещаем его в словарь в качестве ключей. Давайте прочитаем некоторую документацию: она заявляет, что только хешируемые объекты могут использоваться в качестве ключей. Hashable - это все неизменяемые встроенные классы и все классы, определенные пользователем.

Пользовательские классы по умолчанию имеют методы __cmp __ () и __hash __ (); с ними все объекты сравниваются неравно (кроме самих себя), а x .__ hash __ () возвращает результат, полученный из id (x).

Итак, если у вас есть постоянно __hash__ в вашем классе, но вы не предоставляете никаких методов __cmp__ или __eq__, тогда все ваши экземпляры не равны для словаря. С другой стороны, если вы предоставляете какой-либо метод __cmp__ или __eq__, но не предоставляете __hash__, ваши экземпляры по-прежнему будут неравными с точки зрения словаря.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

Выход

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}