Картографическая функция

Question

У меня есть набор из 128-битного числа и размер набора <2 ^ 32 ... так что теоретически я могу иметь функцию отображения, которая отображает все 128-битные числа на 32-битное число .... как я могу построить отображениефункция ???</p>

Answer 1

Похоже, вы ищете минимальный идеальный хеш , который отображает n ключей на n последовательных целых чисел.

Ссылка на вики-страницу в приведенном выше предложении упоминает две библиотеки, которые реализуют это.

Также см. Это для более подробной информации: http://burtleburtle.net/bob/hash/perfect.html

Answer 2

Установите позицию вашего числа как деление его значения на 2 ^ 32.

Answer 3

Общая конструкция - хранить все 128-битные значения в большом массиве, отсортированном в порядке возрастания.Затем каждое значение «сопоставляется» с его индексом в массиве.Чтобы «вычислить» карту, вы выполняете двоичный поиск в массиве, чтобы получить точный индекс значения в массиве.Со значениями 2 ³² размер массива составляет 64 ГБ, а двоичный поиск влечет за собой 35 или около того поисков в массиве.

Вообще говоря, вы не можете сделать действительно лучше, чем это.Однако, если ваши 128-битные значения имеют достаточно равномерный разброс (это зависит от того, откуда они поступают), тогда структура большого массива может быть сжата с большим запасом, особенно если вы можете гарантировать, что все входные данные для вашей карты всегда будут частьюиз набора 128-битных значений;Бьюсь об заклад, вы можете сократить его до пары гигабайт - но поиск будет стоить дороже.

Для более практичного решения вам придется работать со структурой из ваших 128-битных значений: откуда они берутся, что они представляют ...

Answer 4

Не зная природу входных данных, невозможно дать оптимальный алгоритм хеширования. Но если вход распределяется равномерно, вы можете использовать младшие 32 бита входа. Это означает возможность столкновения, поэтому вы должны иметь дело с этим.