Проверка совпадений строк с использованием хэшей, без двойной проверки всей строки

Question

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

У меня есть кэш элементов, которые имеют строковые ключи.Я храню хэш строки, длину строки и саму строку.(В настоящее время я использую djb2 для генерации хэша.)

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

Нужно ли проводить полное сравнение строк?Например, существует ли алгоритм хеширования строк, который может математически гарантировать, что никакие две строки одинаковой длины не будут генерировать одинаковый хэш?Если нет, может ли алгоритм гарантировать, что две разные строки одинаковой длины будут генерировать разные хеш-коды, если какой-либо из первых N символов будет отличаться?

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

Answer 1

Например, существует ли алгоритм хеширования строк, который может математически гарантировать, что никакие две строки одинаковой длины не будут генерировать одинаковый хэш?

Нет, и не может быть,Подумайте об этом: хеш имеет конечную длину, а строки - нет.Скажите ради аргумента, что хеш 32-битный.Можете ли вы создать более 2 миллиардов уникальных строк одинаковой длины?Конечно, вы можете - вы можете создать бесконечное количество уникальных строк, поэтому сравнение хешей недостаточно, чтобы гарантировать уникальность.Этот аргумент масштабируется до более длинных хэшей.

Если нет, может ли алгоритм гарантировать, что две разные строки одинаковой длины будут генерировать разные хеш-коды, если какой-либо из первых N символов будет отличаться?

Ну, да, если число битов в хэше равно количеству битов в строке, но это, вероятно, не тот ответ, который вы искали.

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

Answer 2

Вы должны быть защищены от коллизий, если используете современную функцию хеширования, например один из вариантов Secure Hash Algorithm (SHA) .