长度如何影响碰撞
这只是一个排列组合的问题。
如果我使用小的哈希值(7-8位),那么就会有一些碰撞。
好的,让我们来分析一下。使用8位,对于任何给定的输入,可以生成2^8
个可能的二进制序列。也就是说,可以生成256个可能的哈希值,这意味着理论上每256
个生成的消息摘要值都保证会发生碰撞。这被称为生日问题。
如果我将哈希值中的位数增加到31位,那么就不会有碰撞-所有ngrams都映射到不同的哈希值。
好的,让我们应用相同的逻辑。使用31位精度,我们有2^31
种可能的组合。这是2147483648
个可能的组合。我们可以概括为:
Let N denote the amount of bits we use.
Amount of different hash values we can generate (X) = 2^N
Assuming repetition of values is allowed (which it is in this case!)
这是一种指数增长,这就是为什么使用8位时会发现很多碰撞,而使用31位时则会发现很少的碰撞。
这对碰撞有什么影响?
嗯,由于值的数量很少,并且每个值被映射到输入的机会相等,因此您可以得出结论:
Let A denote the number of different values already generated.
Chance of a collision is: A / X
Where X is the possible number of outputs the hashing algorithm can generate.
当
X
等于
256
时,第一次出现冲突的概率为
1/256
。然后,在生成不同值时,第二次出现冲突的概率为
2/256
。最终,您已经生成了255个不同的值,并且出现冲突的概率为
255/256
。下一次,显然成为
256/256
的概率,即
1
,这是一种概率上的确定性。显然,通常不会达到这个点。发生冲突的频率很可能比每个
256
周期要高得多。实际上,生日悖论告诉我们,在生成
2^N/2
个消息摘要值之后,我们可以开始期望出现冲突。因此,按照我们的例子,那是在我们创建了
16
个唯一哈希之后。但是,我们确实知道,它必须发生,
至少每个
256
个周期。这不好!
从数学角度来看,这意味着发生冲突的概率与输出的可能数量成
反比例,这就是为什么我们需要将消息摘要的长度增加到合理的长度。
关于哈希算法的说明 冲突是完全无法避免的。这是因为有极大数量的可能输入(2^所有可能字符代码),而只有有限数量的可能输出(如上所示)。