标签: murmurhash

我一直试图高度了解MurmurHash的作用.

我已经阅读了一个基本的描述,但还没有找到何时使用它的好解释以及原因.我知道它非常快,但想知道更多.

我问了一个相关的问题,关于如何将UUID放入Redis bitset,有人建议使用MurmurHash.它有效,但我想了解风险/收益.

h[n]:[t]当k为small(<= 5)时,我需要k个独立散列族的哈希函数.或者我需要从均匀随机选择的n个哈希值[1-t],使得它们是k个独立的.我正在尝试实现一些我需要的随机算法.我正在[1-t]使用范围生成n个随机数

scipy.stats.randint(0,self._t).rvs(self._n)

但这似乎对我的申请来说太慢了.由于我不需要完全随机性但只有4个明智的独立性,我想知道我是否可以加快速度.我知道我可以使用多项式哈希族来获得明智的独立性,但这是最好的吗？如果是,是否有任何快速实现,我可以插入？如果不是,有哪些替代方法(库,可能在Python中)？

我已经看过这个线程获得一个k-wise独立哈希函数,但我不确定接受的答案是什么意思:" 如果你需要k个不同的哈希,只需重复使用相同的算法k次,使用k个不同的种子 " .

任何建议都非常感谢.谢谢.

我需要(并且找不到)MurmurHash的纯Python(没有c ++)实现,而且我也是新手自己写的.速度或内存使用量对我的项目无关紧要.

我在这里找到了一个尝试,但它限制为31位散列,我真的需要64位散列.

注:对于那些谁需要一个快速的实现,有一个MurmurHash2库在这里和MurmurHash3库在这里

我们正试图在我们的开发团队中解决内部争论:

我们正在寻找64位PHP哈希函数.我们发现了MurmurHash3的PHP实现,但MurmurHash3是32位或128位,而不是64位.

同事#1认为,要从MurmurHash3生成64位散列,我们可以简单地对128位散列的第一个(或最后一个或任何)64位进行切片,并且它将像本机一样防碰撞64位散列函数.

同事#2认为我们必须找到一个原生的64位散列函数来减少冲突,并且128位散列的64位片段不会像本机64位散列那样具有抗冲突性.

谁是对的？

如果我们采用像SHA1而不是Murmur3这样的加密哈希的第一个(或最后一个或任何)64位,答案是否会改变？

我正在使用SHA-1来检测程序处理文件中的重复项.它不需要加密强大并且可以是可逆的.我找到了这个快速哈希函数列表https://code.google.com/p/xxhash/

如果我想在SHA-1附近的随机数据上获得更快的功能和冲突,我该选择什么？

也许128位哈希足以用于文件重复数据删除？(vs 160 bit sha-1)

在我的程序中,哈希是在0到512 KB的块上计算的.

我正在实现一个简单的布隆过滤器作为练习.

Bloom过滤器需要多个哈希函数,出于实际目的,我没有.

假设我想拥有3个哈希函数,仅仅获取我正在检查成员资格的对象的哈希是否足够,哈希(使用murmur3)然后添加+1,+ 2,+ 3(对于3)不同的哈希)再次哈希之前？

由于murmur3函数具有非常好的雪崩效应(真正展开结果),这对于所有目的都不合理吗？

伪代码:

function generateHashes(obj) {
  long hash = murmur3_hash(obj);
  long hash1 = murmur3_hash(hash+1);
  long hash2 = murmur3_hash(hash+2);
  long hash3 = murmur3_hash(hash+3);
  (hash1, hash2, hash3)
}

如果没有,那么这将是一个简单有用的方法？我希望有一个解决方案,如果需要,我可以轻松扩展更多哈希函数.

谢谢

Haskell和Python似乎不同意Murmurhash2的结果.Python,Java和PHP返回相同的结果,但Haskell没有.关于Haskell上的Murmurhash2我做错了吗？

这是我的Haskell Murmurhash2的代码:

import Data.Digest.Murmur32

    main = do
    print $ asWord32 $ hash32WithSeed 1 "woohoo"

这是用Python编写的代码:

import murmur

if __name__ == "__main__":
    print murmur.string_hash("woohoo", 1)

Python返回3650852671,而Haskell返回3966683799

在Scala 2.10中,MurmurHash由于某种原因被弃用,说我MurmurHash3现在应该使用.但是API是不同的,并且没有有用的scaladoc用于MurmurHash3- >失败.

例如,当前代码:

trait Foo {
  type Bar
  def id: Int
  def path: Bar

  override def hashCode = {
    import util.MurmurHash._
    var h = startHash(2)
    val c = startMagicA
    val k = startMagicB
    h = extendHash(h, id, c, k)
    h = extendHash(h, path.##, nextMagicA(c), nextMagicB(k))
    finalizeHash(h)
  }
}

我该如何使用MurmurHash3呢？这需要一个快速的操作,最好不分配,所以我不希望建立一个Product,Seq,Array[Byte]或whathever MurmurHash3似乎为我提供.

我必须使用 x86 32 位 murmurhash 来确定我在 Kafka 中发送消息的分区。另一个应用程序正在使用 NodeJS murmurhash.v3() 方法从预期分区获取消息。

我尝试了两种方法：

1. 首先，我从https://svn.apache.org/repos/asf/mahout/trunk/math/src/main/java/org/apache/mahout/math/MurmurHash3.java获取了 Java 类
2. 我还尝试将NodeJS murmurhash.v3()的JS代码翻译成Java（下表中的N到A列）

这是我用来从 Apache java 方法获取值的代码：

int ret = MurmurHash3.MurmurHashV3(key, new Long(KAFKA_PARTITION_SEED).intValue());

注意：目前，KAFKA_PARTITION_SEED = 100，但这只是一个测试值。未来将是一个 Long 值。

这是我完成的从 NodeJS转换为 Java 的代码：

    static int MurmurHashV3(String key, int seed) {
    int remainder;
    int bytes;
    int h1;
    int h1b;
    int c1;
    int c2;
    int k1;
    int i;

    remainder = key.length() & 3; // key.length % 4
    bytes = key.length() - remainder;
    h1 = …

我正在尝试使用 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_t 混合到这些函数中以产生雪崩的结果，这会产生我喜欢的伪随机分布。

我想向这个系统引入更多坐标（即 z 和 w），所以我想使用更大的雪崩混合器来散列我的坐标。我相信出于我的目的，我希望看到函数本身产生的最大值是 uint64_t，碰撞本身不是问题，但结果的随机性是问题。

murmur3 …