一个32位哈希和两个16位哈希之间有碰撞率差异吗？

Question

一个32位哈希和两个16位哈希之间有碰撞率差异吗？

7

我正在处理一个可能会出现哈希碰撞问题的系统。基本上，该系统引用哈希表+树形结构中的项目。但是，所涉及的系统首先将包含结构路径的文本文件编译成包含散列值的二进制文件，以提高性能。然而，由于这个原因，碰撞非常严重，因为结构不能存储具有相同哈希值的2个项目；请求项目的部分将没有足够的信息来知道它需要哪一个。

我的初始想法是使用2个哈希，可以使用2个不同的算法或相同的算法两次，并使用2个盐来使其更加抗碰撞。对于不同哈希算法具有相同哈希的两个项目非常不可能。

我希望出于空间原因保持哈希值为32位，因此我认为可以使用两个16位算法而不是一个32位算法。但是，那样不会增加可能哈希值的范围...

我知道转换为两个32位哈希将更加抗碰撞，但我想知道转换为2个16位哈希是否比单个32位哈希至少有一些收益？我不是最擅长数学的人，所以我不知道如何开始检查答案，除了强制执行它...

关于系统的一些背景：

项目由人命名，它们不是随机字符串，通常由单词、字母和数字组成，没有空格。这是一个嵌套的哈希结构，所以如果你有像{a => {b => {c => 'blah'}}}这样的东西，你将通过获取a/b/c的值来获得'blah'的值，编译的请求将是3个哈希值在直接序列中，即a、b和c的哈希值。

只有在给定级别上出现碰撞时才会出现问题。顶层项目和较低级别之间的冲突是可以接受的。你可以有{a => {a => {...}}}，几乎保证在不同级别上发生碰撞（不是问题）。

实际上，任何给定级别可能只有少于100个需要散列的值，并且在同一级别上不会重复。

为了测试我采用的哈希算法（忘记了哪一个，但我没有发明它），我下载了整个CPAN Perl模块列表，将所有名称空间/模块拆分为唯一单词，最后对每个单词进行哈希搜索冲突，我遇到了0个冲突。这意味着算法对CPAN名称空间列表中的每个唯一单词具有不同的哈希值（或者我做错了）。这对我来说足够好，但它仍然在我的脑海中挥之不去。

- Exodist

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

如果您有两个产生不相关值的16位哈希，则刚刚编写了一个32位哈希算法。这将不会比任何其他32位哈希算法更好或更差。

如果您担心冲突，请确保使用良好的哈希算法对数据进行散列（有些仅是为了计算速度而编写，这不是您想要的），并增加哈希大小直到您感到舒适为止。

这引出了冲突概率的问题。事实证明，如果您的集合中有n个元素，则可能发生碰撞的n *（n-1）/ 2对元素。如果您使用k位哈希，则单个对碰撞的几率为2-k。如果您有很多东西，那么不同对之间发生碰撞的几率几乎是不相关的。这正是Poisson分布所描述的情况。

因此，您将看到的碰撞次数应该近似遵循泊松分布，其中λ = n * (n-1) * 2^-k-1。从中可以得知无哈希冲突的概率约为e^-λ。在32位和100个项目的情况下，在一个级别中发生冲突的几率约为一百万分之1.1525。如果您进行足够多次的操作，并使用足够多不同的数据集，那么这些一百万分之一的机会最终会累加起来。

但请注意，您有许多正常大小的级别和少数大型级别，大型级别将对您的碰撞风险产生不成比例的影响。这是因为您向集合中添加的每个内容都可能与之前的任何内容发生冲突 - 内容越多，冲突风险越高。例如，具有1000个数据项的单个级别失败的几率约为1/10,000 - 这与具有100个数据项的100个级别的风险相当。

如果哈希算法不能正常工作，则您的碰撞风险将迅速上升。这种上升速度非常取决于故障的性质。

使用这些事实和您对应用程序使用情况的预测，您应该能够决定是否接受32位哈希的风险，或者是否应该升级到更大的哈希。