问题标签 [murmurhash]

查看https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp我不这么认为，但我想检查一下。

情况是这样的，如果我有一个 1、2、3 或 4 个字节的键，那么简单地将这些字节的数值而不是散列到 8 个字节是否可靠，或者这些会导致大于 4 的键发生冲突用 murmur3 散列的字节？

我对我应该如何用整数键值调用 MurmurHash3_x86_128() 感到困惑，或者它甚至可能吗？murmurhash3 代码可以在https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp找到。方法定义如下。

我用 len 作为 1 散列整数值。它是正确的还是错误的？

鉴于有数十亿个 cookie，像字符串一样的 UUID，在这个样本上测试 murmur3 等 32 位哈希函数的冲突率的最佳方法是什么？

首先，很难生成数十亿个唯一字符串，因为不可能将其保存在内存中，并且没有 100% 精确的随机字符串生成器。

我能想到的唯一方法是：

1. 生成它们并使用大约。像bloomfilter或cuckoo过滤器这样的数据结构来丢弃可能的重复项。然后我们会说存储在一个文件中的唯一 UUID 正好是 5B。
2. 遍历它们，散列它们并使用散列码重复步骤 1)，同时计算有多少冲突。

有没有更好的方法来做到这一点？这样做还有一个缺点，就是在测试2)中的哈希码时，会有一定的误报率。哈希码也必须写入文件，在可能的误报命中的情况下手动检查。

目前我正在尝试在客户端生成 long 类型的唯一标识符。我有一个父/子关系，其中父级已经有一个 UUID 作为标识符。我想考虑使用 Parent-UUID 来计算 long 类型的 Child-Id。

我现在有这个实现：

你怎么看这个想法？欢迎任何建议。

我已经读过这个问题： How to generate unique Long using UUID

我被困在尝试使用 Cormen 的每个级别的通用散列来实现完美的散列技术。具体来说，使用压缩方法（至少，我认为这是我的问题）。

我正在研究字符串，我认为是短字符串（8 到 150 之间），为此，我使用 64 位密钥（对于那些像 spookyhash 这样的散列函数我得到的是较低的 64 位），问题是在 9 个存储桶中存在只有三个唯一字符串（10 个字符中的两个和 11 个字符中的一个）的冲突。

为此，我正在使用 Cormen 的哈希压缩方法：

h_ab(k) = ((ak+b)mod p) mod m

与a = 3，p = 4294967291（最大的 32 位素数），b = 5和m = 9（因为 m_j 应该是 n_j 的平方）。作为“k”，我使用的是散列函数返回的散列值（如杂音）。

例如，如果我使用像 murmur2（64 位版本）这样的哈希函数，p数应该是最大的 64 素数？这样一来，我就涵盖了所有可能的杂音可能返回的哈希值，对吗？

存在哪些其他哈希压缩技术（除除法之外），您推荐吗？

任何参考、提示、书籍、论文、帮助都非常受欢迎。抱歉这个愚蠢的问题，我是哈希函数和哈希表的新手。

提前致谢。

我有 64 位机器，由于它的速度（ https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cppMurmurHash3_x64_128中的函数） ，我想使用 128 位 murmurhash3 。

但问题是我对这个哈希函数的输入不会超过 30 个字节长，在这种情况下for，该函数中的循环MurmurHash3_x64_128只会迭代一次，然后尾部部分就会完成。在这样的方案中，似乎混合不会那么好。我对吗？如果不是，您能否详细说明原因？如果是的话，你会建议128位murmurhash3的输入密钥的合理最小长度是多少，这样散列是好的？

第二件事是关于输出位的截断。据我从答案https://stackoverflow.com/a/11488383/7056851中了解到，虽然由于输出范围较小会导致更高的冲突率，但如果原始哈希函数为“随机”足够了。那么我的问题是 128 位 murmurhash3 是否是输出截断的良好候选者。我问这个的原因是我想使用MurmurHash3_x64_128它的速度性能，但我只需要 32 位哈希值，所以我计划将 128 位分离为 32 位，并为给定的获取 4 个 32 位哈希值钥匙。但我怀疑得到的哈希值有多好。

最后一个问题是关于字节序的。如果您查看源代码链接中第 52 行的注释，它会说：

块读取 - 如果您的平台需要进行字节序交换或只能处理对齐读取，请在此处进行转换

为什么平台是小端还是大端很重要？毕竟，所有的位都与一些常数相乘、旋转和异或等，而我们想要从哈希函数中得到的基本上是将输入键映射到输出范围，并均匀分布。字节序如何改变图片？即使它改变了图片，如果输入是一个char数组怎么办？至少对于字符数组之类的键来说，字节序不应该是重要的，不是吗？

如您所见，我不太擅长分析哈希函数。任何明确的解释表示赞赏。

编辑：查看正确答案的评论。

大家好，这是我在安装 NLP 程序 SpaCY 时遇到的问题。

我尝试了两个pip install -U spacy和pip install spacy，但我似乎得到了同样的错误。我在三台不同的计算机上试过这个。我正在尝试通过 Visual Studio 2017 Preview 安装。

似乎一切都很好，直到我收到以下错误：

错误：需要 Microsoft Visual C++ 14.0。使用“Microsoft Visual C++ 构建工具”获取它： http: //landinghub.visualstudio.com/visual-cpp-build-tools 命令“C:\Users\kevin\Anaconda3\python.exe -u -c”导入 setuptools，标记化；file ='C:\Users\kevin\AppData\Local\Temp\pip-build-jy_zc2z4\murmurhash\setup.py';f=getattr(tokenize, 'open', open)( file );code=f.read ().replace('\r\n', '\n');f.close();exec(compile(code, file , 'exec'))" install --record C:\Users\kevin\AppData \Local\Temp\pip-xagjck4j-record\install-record.txt --single-version-externally-managed --compile" 在 C:\Users\kevin\AppData\Local\Temp\pip- 中出现错误代码 1 失败构建-jy_zc2z4\murmurhash\

所以我去了错误中列出的网站，我需要安装的内容非常模糊，所以我只是回到 Visual Studio 2017 Preview Installer 并单击“修改”。我已经安装了许多 C++ 工具，但我只是单击了尽可能多的 C++ 未选中框。然后我再次尝试，我仍然得到同样的错误。我不确定下一步该尝试什么。我还尝试在运行 linux 的计算机上安装，但我仍然得到了 murmurhash 部分。有没有人有任何想法？我曾经喜欢 pip，但现在它总是让我发疯。

我检查了其他 SpaCy 安装错误帖子。有几对和我的很相似，但不一样。

谢谢

我最近发现MurmurHash是最快的之一，而 MurmurHash3 是 MurmurHash 的新版本。我还在Ian Boyd的图表中找到了 MurmurHash
的完整解释。 这张图看起来真的很棒，但我只了解一点，因为我还是个新手并且对散列很感兴趣。

如果有人可以用一个简单的 MurmurHash3 Flowchart帮助我，那将非常有帮助。

由于我是新手，仍然无法在那里添加任何评论，我也不知道如何联系 Ian Boyd，我想在这里问它..

更新 我制作了自己的 MurmurHash3 流程图。稍后上传

我很抱歉我的菜鸟和英语不好。谢谢

我正在尝试将 MurmurHash 改编为为一个类构建的程序，但我似乎无法找到关于变量代表什么的明确确认。

我使用以下内容作为参考：

据我了解，哈希函数将获取一些值并将其放入哈希表中。“len”是散列表的大小，“key”是要散列的值吗？

我正在尝试使用 Avalanche 混合器来散列整数坐标。我一直在使用Murmur3 的32 位和 64 位雪崩混合器来这样做（而不是实际的总哈希函数）。对于我的应用程序，不需要整个哈希函数，只需要这里看到的 Avalanche Mixer：

这些在我的机器上看起来很快，我将两个 uint32_ts 混合到这些函数中以产生雪崩结果，这会产生我喜欢的伪随机分布。

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

murmur3 似乎没有比 64 更大的雪崩混合器。我查看了这个网站和这个网站以获得一些关于一些替代雪崩哈希的线索：

• 詹金斯查找3

• Hsieh SuperFastHash

• 诡异的哈希

• 城市哈希

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

在 CityHash 中，他们有一个“杂音灵感”的混音器：

这对于两个 64 位数字来说似乎相当快。我对他们如何从 Murmur 中获得他们自己的“灵感”哈希感到困惑。如何创建自己的 2^n 位杂音雪崩混频器？