如何创建自定义Murmur雪崩混合器? [英] How to create a custom Murmur Avalanche Mixer?

问题描述

我正在尝试使用雪崩混合器来哈希整数坐标.我一直在使用 Murmur3的 32位和64位雪崩混合器来这样做(而不是实际的总哈希函数).对于我的应用程序，不需要整个哈希函数，只需在此处看到雪崩混合器即可:

I'm trying to use an Avalanche mixer to hash integer coordinates. I've been using Murmur3's 32bit and 64bit avalanche mixers to do so (and not the actual total hash function). For my application the entire hash function is not needed, only the Avalanche Mixer seen here:

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并将它们混合到这些函数中以产生雪崩的结果，这产生了我喜欢的psuedorandom分布.

These appear fast on my machine, I take two uint32_ts and mix them into these functions to produce avalanched results, this produces a psuedorandom distribution to my liking.

我想向该系统引入更多坐标(即z和w)，所以我想使用更大的雪崩混合器来哈希我的坐标.我认为出于我的目的，我想从函数本身中看到的最大值是uint64_t，冲突本身不是问题，但结果的随机性却是问题.

I want to introduce more coordinates to this system (ie z and w), so I want to use larger avalanche mixers to hash my coordinates. I believe for my puroposes the max value I want to see come out of the function itself is uint64_t, collisions themselves are not a problem, but the randomness of the results are.

似乎murmur3的雪崩混频器没有比64大.我看过此网站和这个以获取一些有关其他雪崩散列的线索:

It does not appear that murmur3 has a larger avalanche mixer than 64. I've looked at this website and this one to get a few clues on some alternative avalanche hashes:

• Jenkins lookup3

谢超速哈希

幽灵般的哈希

城市哈希

这些雪崩的质量对于我的应用程序似乎足够好，但是我对City hash的杂音灵感特别感兴趣.

The quality of these avalanches seem to be good enough for my application but I'm particularly interested in City hash's murmur inspirations.

在CityHash中，他们有一个杂音启发"的混音器:

In CityHash, they have a "murmur inspired" mixer:

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位杂音雪崩混频器?

This seems quite fast for two 64 bit numbers. I'm confused as to how they derived their own "inspired" hash from Murmur. How would one go about creating their own 2^n bit murmur avalanche mixer?

推荐答案

如果您不是真的对冲突感兴趣，而是对结果的随机性感兴趣，那么您应该尝试使用具有128位状态和64位输出的PRNG.

If you really are interested not in collisions, but in the randomness of the results, then you should try to use PRNG with 128bits state and 64bits output.

众所周知，名为 Xoroshiro128 + 的PRNG-非常好随机性.

And pretty good is well-known PRNG called Xoroshiro128+ - fast, quite good randomness.

可以在此处

更新

是的，由于RNG首先返回的总和为2 ⁶⁴ ，所以使用它进行缓存时似乎存在问题.想知道简单的修改(基本上是在旋转/异或之后进行移动结果计算)是否有帮助

Yes, looks like problem to use it for caching due to the fact RNG returns first just a sum modulo 2⁶⁴. Wondering if simple modification (basically, moving result computation after the rotations/xors) will help

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];
}

这篇关于如何创建自定义Murmur雪崩混合器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！