问题标签 [murmurhash]

我想在 Java 应用程序中使用 MurmurHash2 算法（32 位）进行下载验证。GitHub 上存在各种实现，但我想使用MessageDigest实现，因为我对如何以这种方式“翻译”散列算法感兴趣，并且它提供了使用DigestInputStream来“即时”计算散列的可能性下载时。

我的问题：这是否简单/容易完成？这是不可能的吗？你能指出我更多的资源如何做到这一点吗？

我目前正在尝试实现一个哈希表/trie，但是当我将参数传递给 murmurhash2 时，它会返回一个数字，但我得到 unsigned int 溢出的运行时错误：

test.c:53:12：运行时错误：无符号整数溢出：24930 * 1540483477 不能用“无符号整数”类型表示

test.c:60:4: 运行时错误：无符号整数溢出：2950274797 * 1540483477 不能用“无符号整数”类型表示 6265

我在第 53 行和第 60 行放了一堆星星（*）

我不确定我是否传递了一些错误的参数。任何帮助将不胜感激！

当h[n]:[t]k 很小时<= 5（或者我需要从其中均匀随机选择 n 个哈希值[1-t]，以便它们是k 明智独立的。我正在尝试在需要的地方实现一些随机算法。[1-t]我正在使用从范围内生成 n 个随机数

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

但这对我的应用程序来说似乎太慢了。因为我不需要完全随机性，但只需要 4 次独立，我想知道我是否可以加快速度。我知道我可以使用多项式哈希族来获得 k 明智的独立性，但这是最好的吗？如果是，是否有任何我可以插入的快速实现？如果不是，还有哪些替代方法（库，可能在 Python 中）？

我看过这个线程获取一个 k 方向独立散列函数，但我不确定接受的答案是什么意思：“如果你需要 k 个不同的散列，只需重复使用相同的算法 k 次，使用 k 个不同的种子” .

非常感谢任何建议。谢谢。

我正在尝试将字符串散列到长度为 n 的字节数组中的某个位置。我正在使用Murmur哈希函数的以下实现：

https://github.com/tnm/murmurhash-java/blob/master/src/main/java/ie/ucd/murmur/MurmurHash.java

为了获得long以下形式的 64 位哈希：

我现在如何将这个 long 转换为范围内的整数0 - byte_array.length-1？

我试图在 C 中实现哈希表来存储英文单词。所以我在互联网上搜索了一些最好的非加密哈希函数。其中一些是Murmurhash、Seahash、xxHash，但它们似乎都很难实现。所以我搜索了一些更简单的，然后我发现了DJB2, sdbm, lost loss。在实施 sdbm 我得到了这个

我的代码是

如果你也可以帮助我处理 Murmurhash、Seahash 或 xxHash，请这样做。

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

布隆过滤器需要多个哈希函数，出于实际目的，我没有。

假设我想要 3 个散列函数，仅仅获取我正在检查成员资格的对象的散列，散列它（使用 murmur3）然后添加 +1、+2、+3（对于 3不同的哈希值）在再次对它们进行哈希处理之前？

由于 murmur3 函数具有非常好的雪崩效应（确实分散了结果），这对于所有目的来说不是合理的吗？

伪代码：

如果不是，那将是一种简单、有用的方法吗？我想要一个解决方案，如果需要，我可以轻松扩展更多哈希函数。

谢谢

我使用MurmerHash为同一个键生成一堆哈希值，如下所示。它为 50 个不同的种子输出 50 个不同的哈希值。

但是当我有大量密钥（即 1000 万个密钥）时，时间效率并不高。有没有其他方法可以让它更快？

我见过几个问题，问“两个 16 位散列是否具有与 32 位散列相同的冲突率？” 或“两个 32 位散列是否具有与 64 位散列相同的冲突率？” 答案似乎是“是的，如果它们是不相关的体面散列函数”。但是，这是什么意思？

MurmurHash3 的作者这样说：

MurmurHash2_x86_64 并行计算两个 32 位结果并在最后混合它们，这速度很快，但意味着抗碰撞性仅与 32 位散列一样好。我建议避免使用这种变体。

他建议不要使用MurmurHash2_x86_64，但没有提到关于MurmurHash3_x86_128哪个似乎混合四个32 位结果以产生 128 位结果的建议。

而且这个功能看起来更糟：如果消息小于 8 字节，则h3and的输出h4总是会发生冲突。h2也容易发生碰撞，100% 的时间会产生这样的结果：

任何长度小于 16 的空字节组合都将导致这些冲突，无论种子如何。

无论如何，如果Appleby所说的关于他的功能是真的，两个32位结果的抗碰撞性不比单个32位结果好，为什么每次我强制碰撞一个结果，都没有失败，其他不受影响？仅一个哈希中的冲突呈指数级增长。

我问这个的原因是因为我想在 JavaScript 中实现一个 64 位（或更大）的哈希来进行体面的错误检测。32 位散列函数还不够好。GitHub 上目前没有任何可用的解决方案足够快。由于 JavaScript 使用 32 位按位整数，因此只有使用算术运算的函数uint32_t在 JS 中是兼容的。许多 32 位函数似乎能够产生更大的输出而不会造成太多的性能损失。

我已经（在 JavaScript 中）实现了MurmurHash2_x86_64和MurmurHash3_x86_128，它们的性能令人印象深刻。我还实现了 MurmurHash2_160。

所有这些都具有与 32 位哈希相同的抗碰撞性吗？您如何判断结果是否足够相关以成为问题？我希望 64 位输出具有 64 位散列的强度，160 位输出与 160 位散列等一样强 - 同时满足 32 位算术的要求（JavaScript 限制）。

更新：这是我的自定义 64 位哈希，专为速度而设计（比我在 Chrome/Firefox 下优化的 32 位 MurmurHash3 更快）。

它基于 MurmurHash2。每个内部状态h1，h2都单独初始化，但与相同的密钥块混合。然后将它们与备用状态（例如h1 ^= h2）混合。作为最终确定的一部分，它们在最后再次混合。

有什么迹象表明这比真正的 64 位散列更弱吗？它正确地通过了我自己的基本雪崩/碰撞测试，但我不是专家。

我有一个 MySQL 数据库，其中包含一些 Murmur2 哈希（作为无符号 64 位整数），这些哈希是由 Percona UDF 生成的，该 UDF 附带 MySQL 数据库的 Percona 链，可在此处找到https://github.com/percona/build-test/ blob/master/plugin/percona-udf/murmur_udf.cc

我的问题是，现在我需要在 PHP 端生成这些相同的哈希，但我似乎无法找到或调整任何现有的东西来为相同的输入工作/输出相同的输出。

我尝试过的事情：

1. 将 Percona UDF 中的 C++ 函数复制到我最初生成 32 位 int 散列https://github.com/StirlingMarketingGroup/php_murmurhash的 PHP 扩展的分叉版本中。这几乎可以工作，就像在它编译时一样，但是当我在 PHP 中执行函数时，apache 服务器会因段错误而崩溃，而且我对 C++ 和 PHP 扩展还不够熟悉，无法调试它

段错误是由我运行此函数引起的

当我下载https://github.com/kibae/php_murmurhash（原始，32 位，散列生成扩展）并按照说明操作时，它工作正常，但是一旦我替换了函数（仅在 MurmurHash2.cpp 文件中编辑为https ://github.com/StirlingMarketingGroup/php_murmurhash/blob/master/MurmurHash2.cpp）相同的函数调用使 PHP 脚本崩溃。

2. 尝试将 Percona UDF C++ 函数移植到 PHP。我不太确定我的 PHP 函数在试图解释指针递增时是否 100% 准确，但我怀疑更多，所以我得到与 PHP 版本完全不同的输出的原因与 PHP 不支持无符号整数有关。

这是我作为 Percona C++ 函数的端口编写的 PHP 函数

在 MySQL 中，我得到了这个

在 PHP 中我得到

因此，查看 MySQL 和 PHP 结果，无论有符号还是无符号都与我的 PHP 输出相匹配。

有什么东西可以用我以前的两种方法中的任何一种来解决，或者我可以使用一种已经有效的方法吗？

我的驱动程序中的 Token 函数不支持复合分区键，但它适用于单个分区键，它以 8 位形式的二进制作为输入并将其传递给 murmur3 哈希函数并提取 64 符号-little-integer (Token) 来自 murmur3 的结果并忽略任何额外的二进制缓冲区。

所以我希望为复合分区键生成二进制文件，然后像往常一样将其传递给 murmur3，算法或按位运算将非常有用，或者至少是任何编程语言的源代码。

我不是指 murmur3 部分，只是转换/混合复合分区键并以二进制形式输出原始字节的令牌端。