Отображение из разреженного пространства ключей в пространство плотных ключей

Question

У меня есть список событий с UUID, идентифицирующим браузеры.Учитывая это разреженное пространство клавиш, я бы хотел отобразить пространство с плотными клавишами.

Помимо фильтров Блума, какие еще варианты у меня есть?

Если бы у меня было что-то, сопоставленное64-битное значение, было бы идеально, особенно если бы это было алгоритмическое, а не справочная таблица.

Answer 1

Чтобы гарантировать отсутствие коллизий, используйте любой стандартный алгоритм словаря / таблицы символов.Вот что они делают.

Для минимальных коллизий доступны все виды хэш-функций.Lookup3.c Боба Дженкинса довольно популярен.Затем вы должны задать себе вопрос, будете ли вы подвергаться злонамеренному выбору UUID.Если это так, вам нужна лучшая хеш-функция и безопасная случайная соль.(Если вы можете терпеть скорость, ключ HMAC является идеальным способом для этого.)

Answer 2

Если список событий постоянен и не является динамическим, вы можете использовать функцию Minimal Perfect Hashing.