Какой правильный и хороший способ реализовать __hash __ ()?

150

Какой правильный и хороший способ реализовать __hash__()?

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

As __hash__()возвращает целое число и используется для «объединения» объектов в хеш-таблицы. Я предполагаю, что значения возвращаемого целого числа должны быть равномерно распределены для общих данных (чтобы минимизировать коллизии). Какая хорошая практика, чтобы получить такие ценности? Являются ли столкновения проблемой? В моем случае у меня есть небольшой класс, который действует как контейнерный класс, содержащий несколько целых, несколько чисел с плавающей запятой и строку.

user229898
источник

Ответы:

185

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

Вот пример использования ключа для хэша и равенства:

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

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

Джон Милликин
источник
1
Помимо незначительных накладных расходов, связанных с выделением __keyфункции, это примерно так же быстро, как и любой хэш. Конечно, если известно, что атрибуты являются целыми числами, и их не так уж много, я полагаю, что вы могли бы потенциально работать немного быстрее с некоторыми хэшированными в домашних условиях хэшами, но, скорее всего, они не будут так хорошо распределены. hash((self.attr_a, self.attr_b, self.attr_c))это будет на удивление быстро (и правильно ), поскольку создание маленьких tuples специально оптимизировано, и это продвигает работу по получению и объединению хешей для встроенных Си, что обычно быстрее, чем код уровня Python.
ShadowRanger
Допустим, объект класса A используется в качестве ключа для словаря, и если атрибут класса A изменится, его значение хеш-функции также изменится. Не создаст ли это проблемы?
Мистер Матрикс
1
Как говорится в приведенном ниже ответе @ love.by.Jesus, метод хеш-функции не должен быть определен / переопределен для изменяемого объекта (определяется по умолчанию и использует id для равенства и сравнения).
Мистер Матрикс
@ Мигель, я столкнулся с точной проблемой , что происходит, словарь возвращает, Noneкогда ключ меняется. Я решил это путем сохранения идентификатора объекта в качестве ключа, а не просто объекта.
Jaswant P
@JaswantP Python по умолчанию использует идентификатор объекта в качестве ключа для любого хешируемого объекта.
Мистер Матрикс
22

Джон Милликин предложил решение, подобное этому:

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

Проблема с этим решением заключается в том, что hash(A(a, b, c)) == hash((a, b, c)). Другими словами, хэш сталкивается с хэшем кортежа его ключевых членов. Может быть, это не имеет большого значения на практике?

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

Единственным обязательным свойством является то, что объекты, которые сравниваются равными, имеют одинаковое значение хеш

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

Устаревшее / плохое решение

Документация Python__hash__ предлагает объединить хэши подкомпонентов, используя что-то вроде XOR , что дает нам это:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Обновление: как указывает Blckknght, изменение порядка a, b и c может вызвать проблемы. Я добавил дополнительный, ^ hash((self._a, self._b, self._c))чтобы захватить порядок значений хэширования. Этот финал ^ hash(...)может быть удален, если объединяемые значения нельзя переставить (например, если они имеют разные типы и, следовательно, значение _aникогда не будет присвоено _bили _c, и т. Д.).

millerdev
источник
5
Обычно вы не хотите делать XOR-атрибуты напрямую, так как это приведет к коллизиям, если вы измените порядок значений. То есть, hash(A(1, 2, 3))будет равна hash(A(3, 1, 2))(и они оба хэша равны любому другому Aпримеру с перестановкой 1, 2и 3ее ценности). Если вы хотите, чтобы у вашего экземпляра был тот же хеш, что и у кортежа их аргументов, просто создайте значение Sentinel (либо как переменную класса, либо как глобальное), затем включите его в кортеж, который нужно хэшировать: return hash ((_ sentinel) , self._a, self._b, self._c))
Blckknght
1
Использование вами isinstanceможет быть проблематичным, поскольку объект подкласса type(self)теперь может быть равен объекту type(self). Таким образом, вы можете обнаружить, что добавление a Carи a Fordк a set()может привести к вставке только одного объекта, в зависимости от порядка вставки. Кроме того, вы можете столкнуться с ситуацией, где a == bTrue, но b == aFalse.
МаратК
1
Если вы создаете подклассы B, вы можете изменить это наisinstance(othr, B)
millerdev
7
А мысли: ключ кортеж может включать в себя тип класса, который предотвратил бы другие классы с тем же набором ключевых атрибутов не показывались быть равно: hash((type(self), self._a, self._b, self._c)).
Бен Мошер
2
Помимо пункта об использовании Bвместо type(self), также часто считается лучшей практикой возвращаться NotImplementedпри обнаружении неожиданного типа __eq__вместо False. Это позволяет другим определяемым пользователем типам реализовывать объект, __eq__который знает о нем Bи может сравнивать его, если они этого хотят.
Марк Амери
16

Пол Ларсон из Microsoft Research изучил множество хэш-функций. Он мне это сказал

for c in some_string:
    hash = 101 * hash  +  ord(c)

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

Джордж В. Рейли
источник
8
Очевидно, Java делает то же самое, но с использованием 31 вместо 101
user229898
3
Какой смысл использовать эти цифры? Есть ли причина выбрать 101 или 31?
bigblind
1
Вот объяснение простых множителей: stackoverflow.com/questions/3613102/… . 101, кажется, работает особенно хорошо, основываясь на экспериментах Пола Ларсона
Джордж В. Рейли
4
Python использует (hash * 1000003) XOR ord(c)для строк с 32-разрядным циклическим умножением. [Цитата ]
Tylerl
4
Даже если это действительно так, в данном контексте это бесполезно, поскольку встроенные строковые типы Python уже предоставляют __hash__метод; нам не нужно кататься самостоятельно. Вопрос заключается в том, как реализовать __hash__типичный пользовательский класс (с кучей свойств, указывающих на встроенные типы или, возможно, на другие подобные пользовательские классы), к которым этот ответ вообще не относится.
Марк Амери
3

Я могу попытаться ответить на вторую часть вашего вопроса.

Коллизии, вероятно, будут вызваны не самим хеш-кодом, а отображением хеш-кода на индекс в коллекции. Так, например, ваша хеш-функция может возвращать случайные значения от 1 до 10000, но если ваша хеш-таблица содержит только 32 записи, вы получите коллизии при вставке.

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

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

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

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

Вот несколько ссылок, если вы заинтересованы больше:

объединенное хеширование в Википедии

В Википедии также есть сводка различных методов разрешения коллизий:

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

Kryptic
источник
1

Очень хорошее объяснение того, когда и как реализовать эту __hash__функцию, можно найти на сайте программирования :

Просто скриншот, чтобы предоставить обзор: (Получено 2019-12-13)

Снимок экрана: https://www.programiz.com/python-programming/methods/built-in/hash 2019-12-13

Что касается личной реализации метода, вышеупомянутый сайт предоставляет пример, который соответствует ответу millerdev .

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))
loved.by.Jesus
источник
0

Зависит от размера возвращаемого хеш-значения. Это простая логика, что если вам нужно вернуть 32-битное целое число на основе хэша четырех 32-битных целых, вы получите коллизии.

Я бы предпочел битовые операции. Например, следующий псевдокод C:

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

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

Что касается строк, у меня мало / нет идей.

щенок
источник
Я знаю, что будут столкновения. Но я понятия не имею, как они обрабатываются. Более того, мои значения атрибутов в комбинации очень редко распределены, поэтому я искал разумное решение. И как-то я ожидал, что где-нибудь будет лучшая практика.
user229898