Целочисленная функция ha sh, сталкивающаяся после нескольких итераций - PullRequest
Новая
       104

Целочисленная функция ha sh, сталкивающаяся после нескольких итераций

2 голосов
/ 23 марта 2020

Я работаю с кодом, который вычисляет хэши списков объектов, алгоритм был взят из этого вопроса: Быстрый и простой Ха sh Кодовые комбинации . На основании второго ответа значения для seed и factor равны 1009 и 9176. Он хорошо работает для вычисления хэшей случайных списков целых чисел, но я обнаружил, что он просто не работает, когда списки похожи.

Если мы создадим список из 20 случайных целых чисел и вычислим га sh, используя: 

int[] hashCodes = {
    -1641555406,
    1406166370,
    431811193,
    -719284004,
    -463280747,
    138136561,
    -1634028130,
    -792182888,
    1325264708,
    2143865166,
    25622596,
    -977152280,
    1955313253,
    -1440973864,
    1627089736,
    1733757615,
    -576076691,
    -145918914,
    1015082677,
    -954685337,
    -1307289157
};
int hashCode = 1009;
foreach (var c in hashCodes)
    hashCode = hashCode * 9176 + c;

И затем изменим только первое число: 

hashCodes[0] = -145574454;
hashCode = 1009;
foreach (var c in hashCodes)
    hashCode = hashCode * 9176 + c;

мы получим тот же код ha sh. Результат одинаков для любого случайного списка целых чисел - если отличается только первое число, мы получим один и тот же код ha sh около 8-10 итераций.

Я полагаю, что это из-за целочисленного переполнения и усекать старшие биты, но я не уверен. Я попытался использовать начальное число и коэффициент, основанный на первом ответе (17 и 31 соответственно), и он работал нормально. Это почему?

Как рассчитать такой ха sh (ха sh списка целых чисел)?

Редактировать: Согласно комментарию, это не криптографически безопасно, ха sh и не используется как таковой, это просто способ присвоить уникальный целочисленный ключ спискам целых чисел.

1 Ответ

2 голосов
/ 23 марта 2020

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

Число 9176 можно записать в двоичном виде как 10001111011000, и на практике младший 1-бит будет определять, сколько раундов вам нужно выполнить, прежде чем первая запись полностью выпадет из списка.

Последний 1-разрядный находится в позиции 3 (или 4-й позиции справа), и это означает, что вы перемещаете биты из первых позиций 4 влево на каждой итерации. К тому времени, как вы сделали это 8 раз, вы полностью удалили это число из 32-битного буфера (int - 32-битный).

Лучший метод (но см. Мой комментарий ниже ) будет, по крайней мере, гарантировать, что биты не будут потеряны полностью, поэтому другой, но все же довольно простой способ вычисления кода ha sh может выглядеть следующим образом: 

hashCode = ((hashCode << 27) | (hashCode >> 5)) ^ c;

Это в основном вращается текущий га sh кодирует 27 бит слева, и 5 выпадающих битов поворачиваются обратно справа, а затем исключающее ИЛИ с c также записывает это число.

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

И действительно , из-за принципа голубиная дыра , вы не может вычислить уникальный номер для списка чисел, и это не имеет никакого отношения к тому, какой алгоритм кода ha sh вы используете. Никто из них не решит эту часть проблемы. Поэтому я бы действительно попросил вас переосмыслить то, что вы делаете в первую очередь.

...