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

Question

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

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

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

Answer 1

Простой и правильный способ реализации __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):
        return isinstance(self, type(other)) and self.__key() == other.__key()

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

Answer 2

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

class A(object):

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

    def __eq__(self, othr):
        return ((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 на __hash__ предлагает объединить хэши подкомпонентов, используя что-то вроде XOR, что дает нам следующее:

class B(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) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Бонус: более надежный __eq__ добавлен туда для хорошей меры.

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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

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

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

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

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

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

Answer 5

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

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

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

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

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