Идеальная хеш-функция для большого набора целых чисел [1..2^64 - 1]

Question

Мне нужно построить идеальную хеш-функцию, которая отображает набор целых чисел [1..2^64 - 1] на себя (эта функция на самом деле является некоторой сложной перестановкой).

Чтобы объяснить эту проблему, предположим, что у нас есть последовательность целочисленных первичных ключей в базе данных. Нам нужно показать конструирование числа (которое мы показываем пользователям) таким образом, чтобы близкие числа соответствовали первичным ключам, которые находятся как можно дальше друг от друга.

Итак, в основном мне нужна биективная функция для большого набора целых чисел. Например

• 1 -> X1
• 2 -> X3
• 3 -> X3
• ...
• 2 ^ 64 - 1 -> X2 ^ 64 - 1

Любые предложения или ссылки будут оценены.

Answer 1

Максимально разнести любые два числа в интервале от 0 до upperlimit (исключая) я бы установил их расстояние примерно до половины upperlimit,

В Python это будет выглядеть так (код работает только если upperlimit является четным, в противном случае последний элемент сталкивается):

def my_hash(n, upperlimit):
    return n * upperlimit / 2 % upperlimit + n / 2

def my_unhash(n, upperlimit):
    return n % (upperlimit / 2) * 2 + n / (upperlimit / 2)

Пример результата:

upperlimit = 16
for i in range(upperlimit):
    h = my_hash(i, upperlimit)
    u = my_unhash(h, upperlimit)
    print "%02d -> %02d -> %02d" % (i, h, u)

00 -> 00 -> 00
01 -> 08 -> 01
02 -> 01 -> 02
03 -> 09 -> 03
04 -> 02 -> 04
05 -> 10 -> 05
06 -> 03 -> 06
07 -> 11 -> 07
08 -> 04 -> 08
09 -> 12 -> 09
10 -> 05 -> 10
11 -> 13 -> 11
12 -> 06 -> 12
13 -> 14 -> 13
14 -> 07 -> 14
15 -> 15 -> 15

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