Какой правильный и хороший способ реализовать __hash__()
?
Я говорю о функции, которая возвращает хеш-код, который затем используется для вставки объектов в хеш-таблицы, или словари.
As __hash__()
возвращает целое число и используется для «объединения» объектов в хеш-таблицы. Я предполагаю, что значения возвращаемого целого числа должны быть равномерно распределены для общих данных (чтобы минимизировать коллизии). Какая хорошая практика, чтобы получить такие ценности? Являются ли столкновения проблемой? В моем случае у меня есть небольшой класс, который действует как контейнерный класс, содержащий несколько целых, несколько чисел с плавающей запятой и строку.
источник
__key
функции, это примерно так же быстро, как и любой хэш. Конечно, если известно, что атрибуты являются целыми числами, и их не так уж много, я полагаю, что вы могли бы потенциально работать немного быстрее с некоторыми хэшированными в домашних условиях хэшами, но, скорее всего, они не будут так хорошо распределены.hash((self.attr_a, self.attr_b, self.attr_c))
это будет на удивление быстро (и правильно ), поскольку создание маленькихtuple
s специально оптимизировано, и это продвигает работу по получению и объединению хешей для встроенных Си, что обычно быстрее, чем код уровня Python.None
когда ключ меняется. Я решил это путем сохранения идентификатора объекта в качестве ключа, а не просто объекта.Джон Милликин предложил решение, подобное этому:
Проблема с этим решением заключается в том, что
hash(A(a, b, c)) == hash((a, b, c))
. Другими словами, хэш сталкивается с хэшем кортежа его ключевых членов. Может быть, это не имеет большого значения на практике?Обновление: документы Python теперь рекомендуют использовать кортеж, как в примере выше. Обратите внимание, что в документации говорится
Обратите внимание, что обратное неверно. Объекты, которые не сравниваются равными, могут иметь одинаковое значение хеш-функции. Такое столкновение хэшей не приведет к тому, что один объект заменит другой при использовании в качестве ключа dict или элемента set, если объекты также не будут сравниваться .
Устаревшее / плохое решение
Документация Python, что дает нам это:__hash__
предлагает объединить хэши подкомпонентов, используя что-то вроде XORОбновление: как указывает Blckknght, изменение порядка a, b и c может вызвать проблемы. Я добавил дополнительный,
^ hash((self._a, self._b, self._c))
чтобы захватить порядок значений хэширования. Этот финал^ hash(...)
может быть удален, если объединяемые значения нельзя переставить (например, если они имеют разные типы и, следовательно, значение_a
никогда не будет присвоено_b
или_c
, и т. Д.).источник
hash(A(1, 2, 3))
будет равнаhash(A(3, 1, 2))
(и они оба хэша равны любому другомуA
примеру с перестановкой1
,2
и3
ее ценности). Если вы хотите, чтобы у вашего экземпляра был тот же хеш, что и у кортежа их аргументов, просто создайте значение Sentinel (либо как переменную класса, либо как глобальное), затем включите его в кортеж, который нужно хэшировать: return hash ((_ sentinel) , self._a, self._b, self._c))isinstance
может быть проблематичным, поскольку объект подклассаtype(self)
теперь может быть равен объектуtype(self)
. Таким образом, вы можете обнаружить, что добавление aCar
и aFord
к aset()
может привести к вставке только одного объекта, в зависимости от порядка вставки. Кроме того, вы можете столкнуться с ситуацией, гдеa == b
True, ноb == a
False.B
, вы можете изменить это наisinstance(othr, B)
hash((type(self), self._a, self._b, self._c))
.B
вместоtype(self)
, также часто считается лучшей практикой возвращатьсяNotImplemented
при обнаружении неожиданного типа__eq__
вместоFalse
. Это позволяет другим определяемым пользователем типам реализовывать объект,__eq__
который знает о немB
и может сравнивать его, если они этого хотят.Пол Ларсон из Microsoft Research изучил множество хэш-функций. Он мне это сказал
работал на удивление хорошо для широкого спектра струн. Я обнаружил, что подобные полиномиальные методы хорошо работают для вычисления хэша разнородных подполей.
источник
(hash * 1000003) XOR ord(c)
для строк с 32-разрядным циклическим умножением. [Цитата ]__hash__
метод; нам не нужно кататься самостоятельно. Вопрос заключается в том, как реализовать__hash__
типичный пользовательский класс (с кучей свойств, указывающих на встроенные типы или, возможно, на другие подобные пользовательские классы), к которым этот ответ вообще не относится.Я могу попытаться ответить на вторую часть вашего вопроса.
Коллизии, вероятно, будут вызваны не самим хеш-кодом, а отображением хеш-кода на индекс в коллекции. Так, например, ваша хеш-функция может возвращать случайные значения от 1 до 10000, но если ваша хеш-таблица содержит только 32 записи, вы получите коллизии при вставке.
Кроме того, я думаю, что коллизии будут разрешаться коллекцией внутри, и есть много методов для разрешения коллизий. Простейшим (и худшим) является то, что с учетом записи, вставляемой по индексу i, добавьте 1 к i, пока вы не найдете пустое место и не вставите туда. Поиск затем работает так же. Это приводит к неэффективным поискам для некоторых записей, поскольку у вас может быть запись, для поиска которой требуется пройти всю коллекцию!
Другие методы разрешения коллизий сокращают время поиска, перемещая записи в хэш-таблице, когда элемент вставляется для распределения объектов. Это увеличивает время вставки, но предполагает, что вы читаете больше, чем вставляете. Существуют также методы, которые пытаются разветвлять различные конфликтующие записи, чтобы записи кластеризовались в одном конкретном месте.
Кроме того, если вам нужно изменить размер коллекции, вам потребуется перефразировать все или использовать метод динамического хеширования.
Короче говоря, в зависимости от того, что вы используете для хеш-кода, вам может потребоваться реализовать собственный метод разрешения коллизий. Если вы не храните их в коллекции, вы, вероятно, можете воспользоваться хеш-функцией, которая просто генерирует хеш-коды в очень большом диапазоне. Если это так, вы можете убедиться, что ваш контейнер больше, чем он должен быть (чем больше, тем лучше), в зависимости от ваших проблем с памятью.
Вот несколько ссылок, если вы заинтересованы больше:
объединенное хеширование в Википедии
В Википедии также есть сводка различных методов разрешения коллизий:
Кроме того, « Организация и обработка файлов » Tharp охватывает множество методов разрешения коллизий. ИМО это отличный справочник по алгоритмам хеширования.
источник
Очень хорошее объяснение того, когда и как реализовать эту
__hash__
функцию, можно найти на сайте программирования :Просто скриншот, чтобы предоставить обзор: (Получено 2019-12-13)
Что касается личной реализации метода, вышеупомянутый сайт предоставляет пример, который соответствует ответу millerdev .
источник
Зависит от размера возвращаемого хеш-значения. Это простая логика, что если вам нужно вернуть 32-битное целое число на основе хэша четырех 32-битных целых, вы получите коллизии.
Я бы предпочел битовые операции. Например, следующий псевдокод C:
Такая система могла бы работать и для чисел с плавающей запятой, если вы просто взяли их в качестве их битовых значений, а не представляли бы значения с плавающей запятой, возможно, лучше.
Что касается строк, у меня мало / нет идей.
источник