c++ - 如何创建自定义 Murmur Avalanche 混合器？

Question

我正在尝试使用 Avalanche 混合器来散列整数坐标。我一直在使用 Murmur3's 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 更大的雪崩混合器。我看过 this website和 this one获得一些关于一些替代雪崩哈希的线索:

• Jenkins lookup3

• Hsieh SuperFastHash

• Spooky Hash

• City Hash

这些 avalanches 的质量似乎足以满足我的应用需求，但我对 City hash 的 murmur inspirations 特别感兴趣。

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

Answer 1

Pelle Evensen 已经在他关于 mostlymangling.blogspot.com 的博客文章中大致回答了您的问题“如何创建自定义 Murmur Avalanche 混合器”。 ，尤其是以下两个:

• “On the mixing functions in 'Fast Splittable Pseudorandom Number Generators', MurmurHash3 and David Stafford's improved variants on the MurmurHash3 finalizer”，自 2018 年 7 月 13 日起，他分析了原始的 MurmurHash3 混合函数和 David Stafford 的变体，包括单独的和包含在 SplitMix PRNG 中的。
• “Stronger, better, morer, Moremur; a better Murmur3-type mixer”，2019年12月16日，基于MurmurHash3的混合函数模板，展示了自己改进的混合函数。