Как создать собственный миксер Murmur Avalanche?

Question

Как создать собственный миксер Murmur Avalanche?

Я пытаюсь использовать микшер Avalanche для хеширования целочисленных координат. Я использую Murmur3-х 32-битные и 64-битные лавинные смесители для этого (а не фактическая общая хэш-функция). Для моего приложения вся хеш-функция не нужна, только Avalanche Mixer, видимый здесь:

uint32_t murmurmix32( uint32_t h )
{
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;

return h;
}uint64_t murmurmix64( uint64_t h )
{
h ^= h >> 33;
h *= 0xff51afd7ed558ccdULL;
h ^= h >> 33;
h *= 0xc4ceb9fe1a85ec53ULL;
h ^= h >> 33;

return h;
}

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

Я хочу ввести больше координат в эту систему (т.е. z и w), поэтому я хочу использовать более крупные лавинные смесители для хеширования моих координат. Я полагаю, что для моих целей максимальное значение, которое я хочу видеть из самой функции, — это uint64_t, столкновения сами по себе не являются проблемой, но случайность результатов такова.

Похоже, что в murmur3 больше лавинного микшера, чем в 64. Я смотрел на этот сайт а также этот чтобы получить несколько подсказок о некоторых альтернативных лавинных хешах:

Качество этих лавин, по-видимому, достаточно хорошее для моего приложения, но меня особенно интересуют вдохновляющие шумы городского Хэша.

В CityHash у них есть микшер, «вдохновленный шумом»:

uint64 Hash128to64(const uint64_t& x_high, const uint64_t& x_low) {
// Murmur-inspired hashing.
const uint64 kMul = 0x9ddfea08eb382d69ULL;
uint64 a = (x_low ^ x_high) * kMul;
a ^= (a >> 47);
uint64 b = (x_high ^ a) * kMul;
b ^= (b >> 47);
b *= kMul;
return b;
}

Это кажется довольно быстрым для двух 64-битных чисел. Я смущен тем, как они взяли свой собственный «вдохновленный» хэш из Murmur. Как можно создать собственный микшер из лавины с шумом 2 ^ n?

4

c++hash murmurhash random

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Если вы действительно заинтересованы не в столкновениях, а в случайности результатов, то вам следует попробовать использовать PRNG с состоянием 128 бит и выходом 64 бит.

И довольно хорошо это известный PRNG называется Xoroshiro128 + — Быстрая, довольно хорошая случайность.

Код можно найти Вот

ОБНОВИТЬ

Да, похоже, проблема в том, чтобы использовать его для кеширования, потому что ГСЧ возвращает сначала только сумму по модулю 2⁶⁴. Интересно, поможет ли простая модификация (в основном, вычисление результата перемещения после поворотов / xors)

static inline uint64_t rotl(const uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}

uint64_t next(uint64_t* s) {
const uint64_t s0 = s[0];
uint64_t s1 = s[1];

s1 ^= s0;
s[0] = rotl(s0, 55) ^ s1 ^ (s1 << 14); // a, b
s[1] = rotl(s1, 36); // c

return s[0] + s[1];
}

0