Как Python dict может иметь несколько ключей с одинаковым хэшем?

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

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

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

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

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

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

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

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

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

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

Edit: ответ ниже является одним из возможных способов борьбы с хэш-коллизий, однако не как это делает Python. Вики-сайт Python, на который ссылается ниже, также неверен. Лучшим источником, приведенным @Duncan ниже, является сама реализация:http://svn.python.org/projects/python/trunk/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

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

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

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

пользовательские классы имеют __cmp__ () и __хэша__() методы по умолчанию; с ними, все объекты сравните неравные (кроме самих себя) и 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}