c – 如何创建自定义Murmur Avalanche混音器？

概述我正在尝试使用Avalanche混音器来舍入整数坐标.我一直在使用 Murmur3’s 32位和64位雪崩混频器(而不是实际的总哈希函数).对于我的应用程序,不需要整个哈希函数,只有这里看到的Avalanche Mixer： uint32_t murmurmix32( uint32_t h ){ h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; 我正在尝试使用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

这些雪崩的质量似乎足以满足我的应用需求,但我对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位杂音雪崩混音器？

解决方法 如果你真的对碰撞不感兴趣,但是在结果的随机性方面,你应该尝试使用具有128位状态和64位输出的PRNG.

而且相当不错的是众所周知的PRNG叫做Xoroshiro128+ – 快速,相当好的随机性.

代码可以在here找到

UPDATE

是的,看起来像使用它进行缓存的问题是由于RNG首先只返回一个模数为264的事实.想知道简单的修改(基本上,在旋转/ 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];}

总结

以上是内存溢出为你收集整理的c – 如何创建自定义Murmur Avalanche混音器？全部内容，希望文章能够帮你解决c – 如何创建自定义Murmur Avalanche混音器？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。