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

Question

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

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

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

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

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

class D(C):
    def __eq__(self, other):
        return hash(self) == hash(other)

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

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

Примечание: отредактировал вопрос, чтобы привести пример dict (вместо set), потому что все обсуждения в ответах - о dicts. Но то же самое относится и к сетам; Наборы также могут иметь несколько элементов с одинаковым значением хеш-функции.

Answer 1

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

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

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

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

Answer 2

Здесь есть все о Python, которые я смог собрать (вероятно, больше, чем кто-либо хотел бы знать; но ответ исчерпывающий). Приветствую Duncan за то, что он указывает, что 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 зависит от хэша ключа). Если и хеш, и ключ не совпадают с записью в слоте, он начинает поиск, пока не найдет слот с соответствием. Если все слоты исчерпаны, он сообщает об ошибке.
• Кстати, дикт будет изменен, если он заполнен на две трети. Это позволяет избежать замедления поиска. (см. dictobject.h: 64-65)

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

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

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

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

Answer 3

Изменить: ответ ниже является одним из возможных способов справиться с коллизиями хеша, но это не так, как это делает 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,

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

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

Answer 4

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

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

Answer 5

В потоке я не видел, что именно делает 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}