4

我正在尝试使用 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 更大的雪崩混合器。我查看了这个网站和这个网站以获得一些关于一些替代雪崩哈希的线索：

这些雪崩的质量似乎足以满足我的申请，但我对 City hash 的杂音灵感特别感兴趣。

在 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

2 回答 2

2

Pelle Evensen 在mostmangling.blogspot.com上的博文中已经在很大程度上回答了您的问题“如何创建自定义的 Murmur Avalanche 混合器”，特别是以下两个：

于 2020-07-11T18:38:17.437 回答
0

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

相当不错的是著名的 PRNG，称为Xoroshiro128+ - 速度快，随机性非常好。

代码可以在这里找到

更新

是的，由于 RNG 首先返回一个模 2 64的总和，因此使用它进行缓存似乎有问题。想知道简单的修改（基本上，在旋转/异或之后移动结果计算）是否会有所帮助

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];
}
于 2017-07-21T02:58:51.577 回答