Пусть есть строка \(A\) длины \(N\) и строка \(B\) длины \(M\), чтобы проверить совпадают ли они потребуется сравнить все символы, итого в худшем случае \(O(N+M)\).

А что если мы держим в руках записную книжку с большим количеством строк-паролей и к нам часто приходит запрос “вот пароль - есть ли он в записной книжке”? Если в записной книжке суммарная длина строк \(N\) и пришедший запрос длины \(M\) то наивная сверка пароля с каждым паролем из книжки займет много времени - \(O(N+M)\). А хотелось бы быстрее. Та же ситуация складывается когда хочется найти все вхождения некоторого слова в одном большом текстовом документе.

Хэш-функция

Что если мы научимся однозначным образом заменять строчки числами?

В таком случае мы сможем каждую строчку с которой нам приходится работать заменять на число (посчитанное за \(O(N)\), где \(N\)-длина этой строки). И теперь если есть сколько-то строк, то сравнить любые две из этих строк мы сможем за \(O(1)\), т.к. достаточно будет сравнить их сопоставленные числа (т.е. сравнить их хэши).

Какие же свойства в таком случае мы ожидаем от такой функции по строчке считающей число (функции хэширования)?

  • одинаковые строчки должны сопоставляться одинаковым числам

  • разные строчки сопоставлялись разным числам

Заметим что второе свойство невозможно соблюсти, ведь значений у int всего \(2^{32}\), а строчки могут быть произвольной длины, следовательно число разных строк сколь угодно велико, а значит коллизии неизбежны (т.е. совпадения значений хэш функции для разных строк).

Хэши норм...

Ну и ладно, мы же тут не ядерный реактор проектируем, работает же в 99% случаях. (но все-таки функцию “длина строки” как хэш-функцию лучше не брать…)

Давайте попробуем такую функцию хэширования: \(hash(s) = (s[0] + s[1] + s[2] + s[3] + ... + s[n-1])\)

static int hashSimple(String s) {
    int res = 0;
    for (int i = 0; i < s.length(); ++i) {
        res += s.charAt(i); // s.charAt(i) возвращает i-ый символ строки типа char,
                            // который на самом деле является неотрицательным числом от 0 до 65535 включительно
                            // (т.е. вариантов значений 2^16, т.е. 16 бит, т.е. 2 байта)
    }
    return res;
}

public static void main(String[] args) {
    int aCode = 'a';
    System.out.println("(int) a = " + aCode); // например у символа 'a' код (т.е. сопоставляемое число) равен 97
    int bCode = 'b';
    System.out.println("(int) b = " + bCode); // например у символа 'b' код (т.е. сопоставляемое число) равен 98
    // основная часть символов содержится в так называемой ASCII таблице:
    // http://www.asciitable.com/ (проверьте что там у этих символов такие же коды)

    System.out.println(hash("a"));
    System.out.println(hash("b"));
    System.out.println(hash("ab"));
}

Но на самом деле:

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

2) при этом часто хэш функции применяются для ускорения какого-то этапа грубой проверки на которой не критично иногда ошибаться (не влияет на корректность работы системы в целом)

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

Упражнение 1 Заметьте что с приведенным выше хэшом придумать контр-пример очень просто, попробуйте сделать это сами - придумайте какая строчка коллизирует (т.е. совпадает) по своему хэшу с таким хэшом от строчки “ab”, иначе говоря когда hashSimple("ab") == hashSimple(???)? Проверьте свою догадку.

Опр Полиномиальный хэш - функция \(hash(s) = (s[0] + s[1] \cdot p + s[2] * p^2 + s[3] \cdot p^3 + ... + s[n-1] \cdot p^{n-1}) \bmod m\), где \(s\) - строка (и соответственно \(s[i]\) - \(i\)-ый символ - иначе говоря просто число), \(p\) и \(m\) - основание и модуль хэширования.

Упражнение 2 Докажите что какое бы основание \(p\) и модуль \(m\) ни были выбраны - если взять \(m+1\) разную строчку, то хотя бы у двух из них хэш совпадет. Ого, принцип Дирихле в программировании!

Вывод 2 Модуль должен быть как можно больше, а значит должен быть близок к числу разных значений \(int\) (т.к. мы в нем храним посчитанный хэш) т.е. к \(2^{32}\).

Упражнение 3 Пусть в полиномиальном хэшировании используется основание \(p=8\) и \(m=64\). Придумайте две строки совпадающие по такому хэшу (не обязательно воспринимать строки как символы, достаточно придумать вместо строки массив из чисел, где число - номер символа).

Вывод 3 Основание и модуль должны быть взаимно просты - поэтому в реальных применениях предлагаю простые числа \(p=239017\) и \(m=10^9+7=1000000007\).

Упражнение 4 Что если для строки \(s\) длины \(N\) мы хотим посчитать полиномиальный хэш для всех строчек-префиксов? Как сделать это быстрее чем за \(O(N*N)\)?

Вывод 4 Хэш-функция префикса по \(i\)-ый символ равна \(hashPrefix(s, i) = hashPrefix(s, i-1) + s[i] \cdot p^{i}\). (т.е. аналогично тому как было с префиксными суммами)

Рекомендуемые источники

Интересные задачи на хэши с разбором и теорией