Python Frozenset алгоритм хеширования / реализация

В настоящее время я пытаюсь понять механизм позади хэш-функции, определенной для встроенного в Python frozenset тип данных. Реализация показана внизу для справки. Что меня особенно интересует, так это обоснование выбора этой операции рассеяния:

lambda h: (h ^ (h << 16) ^ 89869747) * 3644798167

где h это хэш каждого элемента. Кто-нибудь знает, откуда они? (То есть была какая-то особая причина выбирать эти числа?) Или они были просто выбраны произвольно?


Вот фрагмент официальной реализации CPython,

static Py_hash_t
frozenset_hash(PyObject *self)
{
    PySetObject *so = (PySetObject *)self;
    Py_uhash_t h, hash = 1927868237UL;
    setentry *entry;
    Py_ssize_t pos = 0;

    if (so->hash != -1)
        return so->hash;

    hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
    while (set_next(so, &pos, &entry)) {
        /* Work to increase the bit dispersion for closely spaced hash
           values.  The is important because some use cases have many
           combinations of a small number of elements with nearby
           hashes so that many distinct combinations collapse to only
           a handful of distinct hash values. */
        h = entry->hash;
        hash ^= (h ^ (h << 16) ^ 89869747UL)  * 3644798167UL;
    }
    hash = hash * 69069U + 907133923UL;
    if (hash == -1)
        hash = 590923713UL;
    so->hash = hash;
    return hash;
}

и эквивалентная реализация в Python:

def _hash(self):
    MAX = sys.maxint
    MASK = 2 * MAX + 1
    n = len(self)
    h = 1927868237 * (n + 1)
    h &= MASK
    for x in self:
        hx = hash(x)
        h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
        h &= MASK
    h = h * 69069 + 907133923
    h &= MASK
    if h > MAX:
        h -= MASK + 1
    if h == -1:
        h = 590923713
    return h

3 ответа

Решение

Если не вмешаться Раймонд Хеттингер (автор кода), мы никогда не узнаем наверняка;-) Но в этих вещах обычно меньше "науки", чем вы могли бы ожидать: вы берете некоторые общие принципы и набор тестов и играете Константы почти произвольно, пока результаты не выглядят "достаточно хорошо".

Некоторые общие принципы "очевидно" в работе здесь:

  1. Чтобы получить желаемую быструю "дисперсию битов", нужно умножить на большое целое число. Поскольку результат хеширования CPython должен умещаться в 32 бита на многих платформах, для этого лучше всего использовать целое число, для которого требуется 32 бита. И действительно, (3644798167).bit_length() == 32,

  2. Чтобы избежать систематической потери младших битов, вы хотите умножить на нечетное целое число. 3644798167 странно.

  3. В более общем смысле, чтобы избежать составления шаблонов во входных хешах, вы хотите умножить на простое число. И 3644798167 простое.

  4. И вам также нужен множитель, двоичное представление которого не имеет очевидных повторяющихся шаблонов. bin(3644798167) == '0b11011001001111110011010011010111', Это довольно запутано, и это хорошо;-)

Другие константы выглядят для меня совершенно произвольно.

if h == -1:
    h = 590923713

часть необходима по другой причине: внутренне, CPython принимает -1 возвращаемое значение из целочисленной функции C в значении "необходимо вызвать исключение"; то есть это ошибка возврата. Таким образом, вы никогда не увидите хеш-код -1 для любого объекта в CPython. Возвращаемое значение вместо -1 является полностью произвольным - оно просто должно быть одно и то же значение (вместо -1) каждый раз.

РЕДАКТИРОВАТЬ: играть вокруг

Я не знаю, что Рэймонд использовал, чтобы проверить это. Вот что я бы использовал: посмотрите на хеш-статистику для всех подмножеств набора последовательных целых чисел. Это проблематично, потому что hash(i) == i для большого числа целых i,

>>> all(hash(i) == i for i in range(1000000))
True

Простое кеширование хэшей вместе приведет к массовому аннулированию таких входных данных.

Итак, вот небольшая функция для генерации всех подмножеств, а другая - для простого xor для всех хеш-кодов:

def hashxor(xs):
    h = 0
    for x in xs:
        h ^= hash(x)
    return h

def genpowerset(xs):
    from itertools import combinations
    for length in range(len(xs) + 1):
        for t in combinations(xs, length):
            yield t

Затем драйвер и небольшая функция для отображения статистики столкновений:

def show_stats(d):
    total = sum(d.values())
    print "total", total, "unique hashes", len(d), \
          "collisions", total - len(d)

def drive(n, hasher=hashxor):
    from collections import defaultdict
    d = defaultdict(int)

    for t in genpowerset(range(n)):
        d[hasher(t)] += 1
    show_stats(d)

Использование грязного простого хэша пагубно:

>> drive(20)
total 1048576 unique hashes 32 collisions 1048544

Хлоп! OTOH, используя _hash() Разработано для Frozensets отлично работает в этом случае:

>>> drive(20, _hash)
total 1048576 unique hashes 1048576 collisions 0

Тогда вы можете поиграть с этим, чтобы увидеть, что делает, а что нет, реально изменить _hash(), Например, он по-прежнему отлично работает на этих входах, если

    h = h * 69069 + 907133923

устранен. И я понятия не имею, почему эта линия есть. Аналогичным образом, он продолжает отлично работать на этих входах, если ^ 89869747 во внутреннем цикле убирается - тоже не знаю почему это есть. И инициализация может быть изменена с:

    h = 1927868237 * (n + 1)

чтобы:

    h = n

без вреда и здесь. Это все соответствует тому, что я ожидал: это мультипликативная константа во внутреннем цикле, которая имеет решающее значение по причинам, уже объясненным. Например, добавьте к нему 1 (используйте 3644798168), и тогда он больше не будет простым или нечетным, а статистика ухудшится до:

total 1048576 unique hashes 851968 collisions 196608

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

total 1048576 unique hashes 483968 collisions 564608

Используйте множитель с очевидным двоичным шаблоном, например 0b01010101010101010101010101010101и еще хуже:

total 1048576 unique hashes 163104 collisions 885472

Тренируйся! Эти вещи веселые:-)

Решаемая проблема заключается в том, что предыдущий алгоритм хеширования в Lib/sets.py имел ужасную производительность для наборов данных, возникающих в ряде алгоритмов графов (где узлы представлены в виде Frozensets):

# Old-algorithm with bad performance

def _compute_hash(self):
    result = 0
    for elt in self:
        result ^= hash(elt)
    return result

def __hash__(self):
    if self._hashcode is None:
        self._hashcode = self._compute_hash()
    return self._hashcode

Новый алгоритм был создан, потому что он имел гораздо лучшую производительность. Вот обзор основных частей нового алгоритма:

1) Xor-равно в h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 необходимо, чтобы алгоритм был коммутативным (хеш не зависит от порядка, в котором встречаются элементы множества). Поскольку множества имеет неупорядоченный критерий равенства, хеш для frozenset([10, 20]) должен быть таким же, как для frozenset([20, 10]),

2) XOR с 89869747 был выбран за интересный битовый рисунок 101010110110100110110110011 который используется для разделения последовательностей близких значений хеша до умножения на 3644798167 случайным образом выбранное большое простое число с другим интересным шаблоном битов.

3) XOR с hx << 16 был включен для того, чтобы младшие биты имели два шанса повлиять на результат (что привело к лучшей дисперсии близких значений хеша). В этом я был вдохновлен тем, как алгоритмы CRC перетасовывают биты обратно на себя.

4) Если я правильно помню, единственная особая константа - это 69069. У этого была некоторая история из мира линейных конгруэнтных генераторов случайных чисел. См. https://www.google.com/search?q=69069+rng для некоторых ссылок.

5) Последний шаг вычислений hash = hash * 69069U + 907133923UL был добавлен для обработки случаев с вложенными Frozensets и для рассредоточения алгоритма по шаблону, ортогональному алгоритмам хеширования для других объектов (строк, кортежей, целых и т. д.).

6) Большинство других констант были случайным образом выбраны большие простые числа.

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

Например, вот тест эффективности из Lib/test/test_set.py, который не удался для алгоритмов с меньшей диффузией:

def test_hash_effectiveness(self):
    n = 13
    hashvalues = set()
    addhashvalue = hashvalues.add
    elemmasks = [(i+1, 1<<i) for i in range(n)]
    for i in xrange(2**n):
        addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))
    self.assertEqual(len(hashvalues), 2**n)

Другими ошибочными примерами были наборы мощностей строк и небольших целочисленных диапазонов, а также алгоритмы графов в наборе тестов: см. TestGraphs.test_cuboctahedron и TestGraphs.test_cube в Lib/test/test_set.py.

В

(h ^ (h << 16) ^ 89869747) * 3644798167

мультипликативное целое число - большое простое число, чтобы уменьшить столкновения. Это особенно актуально, поскольку операция ведется по модулю.

Остальное, вероятно, произвольно; Я не вижу причин для 89869747 быть конкретным. Самое важное использование, которое вы получили бы из этого, - это увеличение хешей небольших чисел (большинство целых хэшей для себя). Это предотвращает высокие столкновения для наборов маленьких целых чисел.

Это все, что я могу придумать. Для чего вам это нужно?

Другие вопросы по тегам