Как правильно и хорошо реализовать hash ()?

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

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

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

5 103
python nsdictionary gethashcode hashtable

5 ответов:

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

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

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

    def __eq__(x, y):
        return x.__key() == y.__key()

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

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

123

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

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)). Другими словами, хэш сталкивается с кортежем его ключевых членов. Может быть, это не имеет значения очень часто на практике?

The документация 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 и т. д.).

17

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

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

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

15

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

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

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

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

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

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

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

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

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

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

3

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

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

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

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

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

0