Минимальная идеальная хеш-функция

Question

У меня много целых чисел в диапазоне [0; 2 ^ 63-1]. Однако есть только 10 ^ 8 целых чисел. нет дубликатов . Полный список известен во время компиляции, но это просто уникальные случайные числа . Эти цифры никогда не меняются .
Чтобы хранить одно целое число в явном виде , требуется 8 байт, и есть соответствующие 1-байтовые значения, поэтому для явного хранения требуется около 860 МБ.
Поэтому я хочу найти минимальную идеальную хеш-функцию для отображения каждого из 10 ^ 8 целых чисел из [0; 2 ^ 63-1] в [0; 10 ^ 8-1]. Я должен найти эту функцию только один раз, данные никогда не меняются, и функция может быть сложной. Но оно должно быть минимальным, совершенным, а расчет должен быть быстрым. Как я могу сделать это лучше? Может быть, можно найти и использовать некоторые подпоследовательности, если они происходят?
Спасибо.

Answer 1

Пусть ваш компьютер сделает всю работу за вас:

http://www.gnu.org/software/gperf/

Цитата: "GNU gperf является идеальным генератором хеш-функций. Для заданного списка строк он создает хеш-функцию и хеш-таблицу в форме кода на C или C ++ для поиска значения в зависимости от входной строки. Хеш-функция идеальна, это означает, что хеш-таблица не имеет коллизий, а для поиска в хеш-таблице требуется только сравнение одной строки. "

Answer 2

Я работаю над алгоритмом и реализацией Java, которым требуется менее 1,6 бит на ключ .

Ранее я реализовал минимальный идеальный инструмент хеш-функции в Java , для которого требуется менее 2,0 бит на ключ

Другие алгоритмы реализованы в CMPH . Например, CHD требуется около 2,06 бит на ключ по умолчанию. Его можно настроить так, чтобы он занимал меньше места, но тогда генерация будет медленнее.