Анализ использования простых чисел в хеш-функциях

Question

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

key(s)=s[0]*31(len–1)+s[1]*31(len–2)+ ... +s[len–1]

Пример кода:

public int hashCode( ) 
{
    int h = hash;
    if (h == 0) 
    {
        for (int i = 0; i < chars.length; i++) 
        {
            h = MULT*h + chars[i];
        }
        hash = h;
    }
    return h;
}

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

Предположим, что MULT равнялось 26, и рассмотрим хеширование строки из ста символов.Как сильно влияет первый символ строки на конечное значение «h»?Значение первого символа будет умножено на MULT в 99 раз, поэтому, если арифметика была выполнена с бесконечной точностью, значение будет состоять из некоторого набора битов, за которым следуют 99 нулевых битов младшего разряда - каждый раз, когда вы умножаете на MULT, вы вводите другоеноль младшего разряда, верно?Конечная арифметика компьютера просто отбирает все лишние старшие биты, поэтому фактический вклад первого символа в «h» равен ... точно нулю!Значение 'h' зависит только от крайних правых 32 строковых символов (при условии 32-битного целого), и даже тогда все не так уж прекрасно: первый из этих последних 32 байтов влияет только на самый левый бит `h 'и не имеет никакого эффектана оставшиеся 31. Очевидно, что четное MULT - плохая идея.

Answer 1

Я думаю, что легче увидеть, если вы используете 2 вместо 26. Они оба имеют одинаковый эффект на младшем бите h.Рассмотрим 33-символьную строку некоторого символа c, за которой следуют 32 нулевых байта (для наглядности).Поскольку строка не является полностью нулевой, можно надеяться, что хеш будет ненулевым.

Для первого символа ваш вычисленный хеш h равен c[0].За второй символ вы берете h * 2 + c[1].Так что теперь h это 2*c[0].Третий символ h теперь равен h*2 + c[2], что соответствует 4*c[0].Повторите это еще 30 раз, и вы увидите, что множитель использует больше битов, чем доступно в вашем месте назначения, то есть фактически c[0] не оказал никакого влияния на окончательный хэш.

Конечная математика работает точното же самое с другим множителем, таким как 26, за исключением того, что промежуточные хэши будут по модулю 2^32 очень часто во время процесса.Поскольку число 26 четное, оно все равно добавляет один бит 0 к младшему концу каждой итерации.

Answer 2

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

Теперь давайте рассмотрим, что происходит, когда вы используете множитель, такой как 31. Ну, 31 равен 32-1 или 2 ^ 5 - 1. Поэтому, когда вы используете это, ваше окончательное значение хеш-функции будет:

\ sum {c_i 2 ^ {5 (len-i)} - \ sum {c_i}

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

В результате использование множителя 31 означает, что хотя символы, отличные от последнегосемь влияют на строку, она полностью не зависит от их порядка.Если вы возьмете две строки, которые имеют одинаковые последние 7 символов, для которых другие символы также одинаковы, но в другом порядке, вы получите одинаковый хеш для обоих.Вы также получите тот же хеш для таких вещей, как «az» и «by», отличных от последних 7 символов.

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

public unisgned hashCode(string chars)
{
    unsigned h = 0;
    for (int i = 0; i < chars.length; i++) {
        h = (h<<5) + (h>>27);  // ROL by 5, assuming 32 bits here
        h += chars[i];
    }
    return h;
}

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

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

Answer 3

Этот хеш можно описать так (здесь ^ - возведение в степень, а не xor).

hash(string) = sum_over_i(s[i] * MULT^(strlen(s) - i - 1)) % (2^32).

Посмотрите на вклад первого символа.Это

(s[0] * MULT^(strlen(s) - 1)) % (2^32).

Если строка достаточно длинная (strlen (s)> 32), то это ноль.

Answer 4

даст уникальное значение

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