Минимальная идеальная хеш-функция
У меня есть много целых чисел в диапазоне [0; 2^63-1]. Однако есть только 10^8 целых чисел. Там нет дубликатов. Полный список известен во время компиляции, но это просто уникальные случайные числа. Эти цифры никогда не меняются.
Чтобы хранить одно целое число явно, требуется 8 байтов, и есть соответствующие 1-байтовые значения, поэтому для явного хранения требуется около 860 МБ.
Поэтому я хочу найти минимальную идеальную хеш-функцию для отображения каждого из 10^8 целых чисел из [0; 2 ^ 63-1] в [0;10^8-1]. Я должен найти эту функцию только один раз, данные никогда не меняются, и функция может быть сложной. Но это должно быть минимально, идеально, и расчет должен быть быстрым. Как я могу сделать это лучше? Может быть, можно найти и использовать некоторые подпоследовательности, если они случаются?
Благодарю.
2 ответа
Пусть ваш компьютер сделает всю работу за вас:
http://www.gnu.org/software/gperf/
Цитата: "GNU gperf является идеальным генератором хеш-функций. Для заданного списка строк он создает хеш-функцию и хеш-таблицу в форме кода на C или C++ для поиска значения в зависимости от входной строки. Хеш-функция идеально, что означает, что хеш-таблица не имеет коллизий, а для поиска в хеш-таблице требуется только сравнение одной строки ".
Я работаю над алгоритмом и реализацией Java, которые требуют менее 1,6 бит на ключ.
Ранее я реализовал минимальный идеальный инструмент хэш-функции в Java, который требует менее 2,0 бит на ключ.
Другие алгоритмы реализованы в CMPH. Например, CHD требуется около 2,06 бит на ключ по умолчанию. Он может быть настроен на использование меньшего количества места, но тогда генерация будет медленнее.