Что такое корректный и хороший способ реализовать __ хеш __ ()?
Что такое корректный и хороший способ реализовать __hash__()?
Я говорю о функции, которая возвращает хэш-код, который затем используется для вставки объектов в хеш-таблицы иначе словари.
Как __hash__() возвращает целое число и используется для объектов "binning" в хеш-таблицы, я предполагаю, что значения возвращенного целого числа должны быть равномерно распределены для общих данных (для уменьшения коллизий). Что хорошая практика должна получить такие значения? Действительно ли коллизии являются проблемой? В моем случае у меня есть маленький класс, который действует как контейнерный класс, содержащий некоторый ints, некоторые плавания и строку.
4 ответа
Простой и правильный способ реализовать __ 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 до 10000, но если в вашей хэш-таблице всего 32 записи, вы получите коллизии при вставке.
Кроме того, я думаю, что коллизии будут разрешаться внутренней коллекцией, и существует множество методов разрешения коллизий. Самый простой (и худший) - это, учитывая запись для вставки в индекс i, добавить 1 к i, пока не найдется пустое место, и вставить туда. Затем извлечение происходит таким же образом. Это приводит к неэффективному извлечению для некоторых записей, так как вы можете получить запись, для поиска которой необходимо обойти всю коллекцию!
Другие методы разрешения коллизий уменьшают время поиска, перемещая записи в хэш-таблице при вставке элемента, чтобы распределить их. Это увеличивает время вставки, но предполагает, что вы читаете больше, чем вставляете. Существуют также методы, которые пытаются разветвить различные сталкивающиеся записи так, чтобы записи группировались в одном определенном месте.
Кроме того, если вам нужно изменить размер коллекции, вам придется все перехешировать или использовать метод динамического хеширования.
Короче говоря, в зависимости от того, для чего вы используете хэш-код, вам, возможно, придется реализовать свой собственный метод разрешения коллизий. Если вы не храните их в коллекции, то, вероятно, можно обойтись хэш-функцией, которая просто генерирует хэш-коды в очень большом диапазоне. В этом случае вы можете убедиться, что ваш контейнер больше, чем нужно (чем больше, тем лучше, конечно), в зависимости от ваших проблем с памятью.
Вот несколько ссылок, если вам интересно больше:
В википедии также есть резюме различных методов разрешения коллизий:
Кроме того, "File Organization And Processing" Тарпа подробно описывает многие методы разрешения коллизий. IMO это отличный справочник по алгоритмам хэширования.
Пол Ларсон из Microsoft Research изучил широкий спектр хеш-функций. Он сказал мне, что
for c in some_string:
hash = 101 * hash + ord(c)
на удивление хорошо работает для самых разных струн. Я обнаружил, что аналогичные полиномиальные методы хорошо работают для вычисления хэша разнородных подполей.
Зависит от размера возвращаемого хэш-значения. По простой логике, если вам нужно вернуть 32-битный int, основанный на хэше из четырех 32-битных int, вы получите коллизии.
Я бы отдал предпочтение битовым операциям. Например, следующий псевдокод на C:
int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);
Такая система могла бы работать и для плавающих чисел, если бы вы просто воспринимали их как битовое значение, а не как реальное представление значения с плавающей точкой, может быть, даже лучше.
Для строк у меня мало идей.