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

Ответ 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):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

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

Ответ 2

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

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 по __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 и т.д.).

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

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