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

Ответ 1

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

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

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

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

Ответ 2

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

# 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-equal в h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167, так что алгоритм commutative (хэш не зависит от порядка, в котором установлены элементы встречается). Поскольку множества имеют неупорядоченный тест равенства, хэш для 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 был добавлен для обработки случаев с вложенными фризонсетями и для того, чтобы алгоритм рассеивался в шаблоне, ортогональном хэш-алгоритмам для других объектов (строки, кортежи, ints и т.д.).

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.

Ответ 3

В

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

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

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

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