Хеши бывают разной длины. От
8 бит до 512 бит. И в зависимости от сложности самой функции
и от разрядности возможны такие ситуации что для разных файлов вдруг хеш совпадает.
В криптографии отдельно изучают
парадокс дней рождений (когда группа случайных людей порядка
20 человек вдруг имеет 50% вероятность нахождения пары людей с одинаковой датой рождения
вида MM/DD). Вобщем этот парадокс для криптунов - шибко важный и они носятся с ним везде
и любят обсуждать применительно к атакам на шифры и ЭЦП.
Кажется Брюс Шнайер предлагал свою метрику для ожидания коллизий в зависимости от длины
ключа.
В Java существовала атака на хеш-мап основанная на том что хеш-функция несовершеннаа
и может давать коллизии.
Для латиницы
public static int hashCode(byte[] value) {
int h = 0;
byte[] var2 = value;
int var3 = value.length;
for(int var4 = 0; var4 < var3; ++var4) {
byte v = var2[var4];
h = 31 * h + (v & 255);
}
return h;
}
Насколько я понимаю ни к чему страшному атака не приводила. Просто хеш-мапа вырождалась
в список и некоторые тайм-критичные системы (Tomcat/Jetty) могли тормозить на отдаче хедеров.
Фиксилось это просто заменой бакетов хеш-табли на деревья при определенном условии. ТАм
было что-то вроде - если длина цепочки в бакете больше чем константа - то генерировать дерево.
Вобщем некоторые кибер-задроты не поленились и нашли такие строки которые дают одинаковые хеши.
Некоторые хеш-функции (CRC-32) обладают интересными свойствами. На диапазоне целых до 4 млрд
эта функция вообще дает 0 коллизий и точно отображает ключ в бакет. Кажется это свойства
тех полиномов на базе которых CRC вообще строятся. (Насчет CRC я точно не уверен. Мой приятель
этот факт проверял на С++).
Я честно говоря считал что в хешах уже все известно но периодически их придумывают новые с разными
свойствами. Вот для нужд биг-даты в 2008 был придуман Mur-mur
https://en.wikipedia.org/wiki/MurmurHash
И еще примерно 9 лет назад один чел создал хеш-функцию
xxhash которая якобы супер-быстрая
https://github.com/Cyan4973/xxHash но я не мерял. Такая себе функция-шустрик.
Вобщем из свойств раздличают
криптографические (SHA) (трудно создать коллизию) и вот
эти вот шустрики
которые летают как CPU и годятся для хешей но при этом ЭЦП на них строить не рекомендуется.
