散列冲突:随着多次散列而增长的机会
取决于你的意思。
如果由于重新散列造成散列发生变化,那么是的,如果没有,那么没有。
如果对象没有改变,而你重新哈哈哈哈,它会保持相同的散列。例如,字符串teststring
的md5散列将始终为D67C5CBF5B01C9F91932E3B8DEF5E5F8
。
但是,如果对象发生变化并因此重新哈希,您将得到一个新的哈希值。
现在,如果您重新刷新发生更改的对象,则碰撞可能性会更高。
举个例子,你有一个非常简单的对象,它只包含一个整数值和一个非常简单的散列算法,它只需要这个值,并对它做一个modulo 20
。这只是针对这个例子的一个故意的散列算法。
现在说你有两个包含随机数的对象。这两个值的哈希碰撞的机会是1/20
,因为哈希算法中有20个存储桶。
如果您现在重新组合,您将再次有机会碰撞或碰撞的几率为19/20
。
因此n
rehashes之后没有碰撞的机会是(19/20)^(n+1)
。所以在第一次重新散列之后(所以你有你的原始值,并且在它改变之后重新刷新其中的一个值),你有没有碰撞的90.25%
机会。在第二次重新刷新之后,你有可能不会碰到任何碰撞的85.76%
。经过100次重新编译后,你只有一个不会碰撞的机会。
这完全取决于在每次重新散列之前,这些值会变为新值。
另一种方式来证明是这样的:
- 散列算法给你的桶数量有限(=不同的可能哈希值)
- 你可以用不同的值 无限量喂你的哈希算法
- 每个值都需要映射到存储桶
- 如果您将无限量的值映射到有限数量的存储桶,则某些时候会出现冲突。
你是什么意思“改变因为改变”?结果哈希? –
是的。如果以相同的方式重新提供相同的值,则始终会得到相同的散列值。如果你在对象改变后重新哈希,你会得到一个不同的散列,然后它会改变散列。我会将其添加到答案中。 – Dakkaron
我的意思是:当我散列一个对象然后散列散列(多次)时,与其他对象散列冲突的机会是否以相同的方式散列(多次),变得更高? –
为什么downvote? –