Я работаю в системе, где коллизии хешей будут проблемой.По сути, существует система, которая ссылается на элементы в хэш-таблице + древовидная структура.Однако рассматриваемая система сначала компилирует текстовые файлы, содержащие пути в структуре, в двоичный файл, содержащий вместо этого хэшированные значения.Это сделано из соображений производительности.Однако из-за этого коллизии очень плохи, так как структура не может хранить 2 элемента с одинаковым хеш-значением;часть, запрашивающая элемент, не будет иметь достаточной информации, чтобы знать, какой он нужен.
Моя первоначальная мысль состоит в том, что 2 хеша, использующих 2 разных алгоритма или один и тот же алгоритм дважды, с 2 солями будут болееустойчивый к столкновениям.Два элемента, имеющие одинаковый хэш для разных алгоритмов хеширования, были бы очень маловероятными.
Я надеялся сохранить значение хеш-функции 32-битным по соображениям пространства, поэтому я подумал, что вместо этого я мог бы перейти на использование двух 16-битных алгоритмоводного 32-битного алгоритма.Но это не увеличило бы диапазон возможных значений хеша ...
Я знаю, что переключение на два 32-битных хеша будет более устойчивым к коллизиям, но мне интересно, если переключение на 2 16-битных хеша имеетхоть какой-то выигрыш над одним 32-битным хешем?Я не самый склонный к математике человек, поэтому я даже не знаю, как начать проверять ответ, кроме как заставить его принуждать ...
Некоторые сведения о системе:
Предметылюди получают имена, они не являются случайными строками и обычно состоят из слов, букв и цифр без пробелов.Это вложенная хеш-структура, поэтому, если бы у вас было что-то вроде {a => {b => {c => 'blah'}}}, вы могли бы получить значение 'blah', получив значение a / b / c,скомпилированный запрос будет состоять из 3 хеш-значений в непосредственной последовательности, хеш-значения a, b и затем c.
Проблема возникает только при столкновении на данном уровне.Столкновение между предметом на верхнем и нижнем уровнях - это нормально.Вы можете иметь {a => {a => {...}}}, почти гарантируя столкновения, которые находятся на разных уровнях (не проблема).
На практике любой данный уровень, вероятно, будет иметь менее 100значения для хэша, и ни один из них не будет дубликатом на одном уровне.
Чтобы проверить алгоритм хеширования, который я принял (забыл, какой из них, но я его не изобрел), я скачал весь список модулей CPAN Perl, splitвсе пространства имен / модули в уникальные слова, и, наконец, хэшируя каждое в поиске коллизий, я столкнулся с 0 коллизиями.Это означает, что алгоритм имеет разные значения хеш-функции для каждого уникального слова в списке пространств имен CPAN (или что я сделал это неправильно).Мне это кажется достаточно хорошим, но это все еще мучает мой мозг.