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

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

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

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

  • Когда использовать == и когда использовать?
  • Как проверить, ссылаются ли две переменные на один и тот же объект на Python?
  • Python if not == vs if! =
  • Pandas DataFrames с сравнением равенства NaNs
  • Python проверяет, является ли строка одним из определенного набора значений
  • Почему ключевое слово «есть» имеет другое поведение, когда в строке есть точка?
  •  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. Но то же самое относится к наборам; множества также могут иметь несколько элементов с одинаковым значением хэша.

  • Могу ли я передавать значения словаря / ввод и клавиши для работы
  • Словарь Python vs Если скорость сообщения
  • Почему вы должны вызывать .iteritems () при итерации по словарю в python?
  • Как проверить, ссылаются ли две переменные на один и тот же объект на Python?
  • Большинство питоновских способ построить словарь из единого списка
  • Python проверяет, является ли строка одним из определенного набора значений
  • 5 Solutions collect form web for “Как 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 )

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

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

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

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

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

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

    На самом деле существует несколько возможных решений этой проблемы, ознакомьтесь с статьей wikipedia для приятного обзора: 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} 
    Python - лучший язык программирования в мире.