Проверка совпадений строк с использованием хэшей, без двойной проверки всей строки
Я пытаюсь проверить, идентичны ли две строки как можно быстрее. Могу ли я защитить себя от коллизий хешей, не сравнивая также всю строку?
У меня есть кэш элементов, которые обозначены строкой. Я храню хэш строки, длину строки и саму строку. (В настоящее время я использую djb2 для генерации хеша.)
Чтобы проверить, совпадает ли входная строка с элементом в кеше, я вычисляю хэш ввода и сравниваю его с сохраненным хешем. Если это совпадает, я сравниваю длину ввода (которую я получил как побочный эффект вычисления хэша) с сохраненной длиной. Наконец, если это совпадает, я делаю полное сравнение строк ввода и сохраненной строки.
Нужно ли делать это полное сравнение строк? Например, существует ли алгоритм хеширования строк, который может математически гарантировать, что никакие две строки одинаковой длины не будут генерировать одинаковый хеш? Если нет, может ли алгоритм гарантировать, что две разные строки одинаковой длины будут генерировать разные хеш-коды, если какой-либо из первых N символов будет отличаться?
По сути, любая схема сравнения строк, которая предлагает производительность O(1), когда строки отличаются, но лучше, чем производительность O(n), когда они совпадают, будет улучшением по сравнению с тем, что я делаю сейчас.
2 ответа
Например, существует ли алгоритм хеширования строк, который может математически гарантировать, что никакие две строки одинаковой длины не будут генерировать одинаковый хеш?
Нет, и не может быть. Подумайте об этом: хеш имеет конечную длину, а строки - нет. Скажите ради аргумента, что хеш 32-битный. Можете ли вы создать более 2 миллиардов уникальных строк одинаковой длины? Конечно, вы можете - вы можете создавать бесконечное количество уникальных строк, поэтому сравнение хешей недостаточно для гарантии уникальности. Этот аргумент масштабируется до более длинных хэшей.
Если нет, может ли алгоритм гарантировать, что две разные строки одинаковой длины будут генерировать разные хеш-коды, если какой-либо из первых N символов будет отличаться?
Ну, да, если количество битов в хэше равно количеству битов в строке, но это, вероятно, не тот ответ, который вы искали.
Некоторые из алгоритмов, используемых для циклических проверок избыточности, имеют гарантии, например, если разность ровно на один бит, то CRC гарантированно будет отличаться на определенной длине разряда, но это работает только для относительно коротких разрядов.
Вы должны быть защищены от коллизий, если используете современную функцию хеширования, такую как один из вариантов алгоритма безопасного хеширования (SHA).