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