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

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

Хэш-функция

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

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

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

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

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

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

Хэши норм...

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

Давайте попробуем такую функцию хэширования:

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(???)? Проверьте свою догадку.

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

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

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

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

Вывод 3 Основание и модуль должны быть взаимно просты - поэтому в реальных применениях предлагаю простые числа и .

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

Вывод 4 Хэш-функция префикса по -ый символ равна . (т.е. аналогично тому как было с префиксными суммами)

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

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