Равномерно распределенная хеш-функция

Question

Мне нужна хеш-функция, которая принимает в качестве входных данных несколько (например, 2 или 3) целых без знака и возвращает значение с плавающей запятой в диапазоне от -1 до + 1.

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

Надеюсь, спросить не так уж много: S ...

Answer 1

Murmurhash - это очень хорошая (сильная) и быстрая хеш-функция, которая провела серьезное тестирование на ней.

http://sites.google.com/site/murmurhash/

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

#define MURMURHASH2A_R 24
#define MURMURHASH2A_MULTIPLIER 0x5bd1e995
#define MURMURHASH2A_SEED 2166136261U  // No seed suggested, so using FNV32_OFFSET_BASIS
#define murmurhash2a_init(h) do { h = MURMURHASH2A_SEED; } while (0)
#define murmurhash2a_update(h,word)                     \
do {                                                    \
  u_int mmh2ak = (word) * MURMURHASH2A_MULTIPLIER;      \
  mmh2ak ^= mmh2ak >> MURMURHASH2A_R;                   \
  mmh2ak *= MURMURHASH2A_MULTIPLIER;                    \
  h *= MURMURHASH2A_MULTIPLIER;                         \
  h ^= mmh2ak;                                          \
 } while (0)
#define murmurhash2a_final(h)                   \
do {                                            \
  h ^= h >> 13;                                 \
  h *= MURMURHASH2A_MULTIPLIER;                 \
  h ^= h >> 15;                                 \
 } while (0)

u_int hash;
murmurhash2a_init(hash);
murmurhash2a_update(hash,firstint);
murmurhash2a_update(hash,secondint);
[...]
murmurhash2a_final(hash);

Очевидно, это возвращает 0-2 ^ 32-1.На сайте ропот есть 64-битная версия.Преобразование целого числа в число с плавающей точкой в ​​диапазоне оставлено читателю в качестве упражнения (в делении).

Answer 2

Вы можете использовать стандартную схему для таких задач: (a0 + Q*a1 + Q^2*a2 + Q^3*a3 + ...) % M, где M - очень большое простое число, а Q - коэффициент по вашему выбору.
Если у вас есть достаточно случайный хэш в диапазоне [0, M), преобразование его в число с плавающей запятой [-1, 1] становится тривиальным.

Или вы можете удалить % M и разрешить целочисленное переполнение, хотя я не уверен, насколько он безопасен (с точки зрения «равномерно распределенного»).

Последовательность выходов из функции должна выглядеть как случайная последовательность, даже если входные числа являются последовательными.
Для этого вы можете вместо ai использовать ai*ai в выражении. В любом случае, вот простая реализация на Java.

double hash(int... a) {
    int Q = 433494437;
    int result = 0;
    for (int n : a) {
        result = result * Q + n * n;
    }
    result *= Q;
    return (double) result / Integer.MIN_VALUE;
}

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