хэширование небольшого числа в случайное 64-битное целое число

Question

Я ищу хэш-функцию, которая работает с маленьким целым числом (скажем, в диапазоне 0 ... 1000) и выдает 64-разрядное целое число.

Набор результатов должен выглядеть как случайныйраспределение 64-битных целочисленных значений: равномерное распределение без линейной корреляции между результатами.

Я надеялся, что для выполнения функции потребуется всего несколько циклов ЦП.(код будет на C ++).

Я рассмотрел умножение ввода на большое простое число и взятие по модулю 2 ** 64 (что-то вроде линейного конгруэнтного генератора), но между выходами есть очевидные зависимости(в младших битах).

Поиск в Google ничего не обнаружил, но я, вероятно, использую неправильные условия поиска.

Существует ли такая функция?

---

Некоторая справочная информация:

Я хочу не использовать в алгоритме большую постоянную таблицу с псевдослучайными числами и вычислять случайные числа на лету.

Безопасность не является проблемой.

Answer 1

Я протестировал 64-битный финализатор MurmurHash3 (предложенный @aix и в этом посте ).Это дает ноль, если входное значение равно нулю, поэтому я сначала увеличил входной параметр на 1:

typedef unsigned long long uint64;

inline uint64 fasthash(uint64 i)
{
  i += 1ULL;
  i ^= i >> 33ULL;
  i *= 0xff51afd7ed558ccdULL;
  i ^= i >> 33ULL;
  i *= 0xc4ceb9fe1a85ec53ULL;
  i ^= i >> 33ULL;
  return i;
}

Здесь входной аргумент i представляет собой небольшое целое число, например элемент {0, 1, ..., 1000}.Вывод выглядит случайным образом:

i       fasthash(i) decimal:    fasthash(i) hex:
0       12994781566227106604    0xB456BCFC34C2CB2C
1       4233148493373801447     0x3ABF2A20650683E7
2       815575690806614222      0x0B5181C509F8D8CE
3       5156626420896634997     0x47900468A8F01875
...     ...                     ...

Нет линейной корреляции между последующими элементами серии:

Диапазон обеих осей равен 0..2^64-1

Answer 2

Почему бы не использовать существующую хеш-функцию, такую ​​как MurmurHash3 с 64-разрядным финализатором?По словам автора, на текущем оборудовании Intel функция занимает десятки циклов ЦП на ключ.

Answer 3

1000 * 1000 = 1 000 000. Это хорошо вписывается в Int32.

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

Answer 4

Дано: введите i в диапазоне от 0 до 1000.

const MaxInt - максимальное значение, которое может содержаться в 64-битном int. (вы не сказали, подписано оно или нет, 2 ^ 64 = 18446744073709551616)

и функция rand (), которая возвращает значение от 0 до 1 (большинство языков имеют такую ​​функцию)

вычислить hashvalue = i * rand () * (MaxInt / 1000)