碰撞 (计算机科学)

在计算机科学中，碰撞或冲突是指两个不同的元素具有相同的哈希值、校验和，数字指纹时发生的情况。当数据量足够多（例如将所有可能的人名和计算机文件名映射到一段字符上）时，碰撞是不可避免的。这仅仅是鸽巢原理的一个实例。

哈希碰撞是指两个不同的输入值经过哈希函数处理后得到相同的输出值。 这种情况在哈希表数据结构中尤为重要，因为它可能影响查找和存储的效率。

哈希碰撞的发生是不可避免的，主要原因如下：

1. 输入空间通常大于输出空间：哈希函数将任意长度的输入映射到固定长度的输出，必然会有多个输入对应同一个输出.
2. 生日悖论：根据概率论，即使在相对较小的样本空间中，也有较高的概率出现重复.

处理哈希碰撞的主要方法有两种：

1. 开放寻址法：当发生碰撞时，继续探测散列表的下一个位置，直到找到空槽.
2. 链接法：在每个散列表槽位使用链表存储发生碰撞的元素

一个优秀的哈希函数应该满足以下条件：

1. 单向性：难以从哈希值反推原始输入。
2. 弱无碰撞性：给定一个输入，难以找到另一个输入产生相同的哈希值。
3. 强无碰撞性：难以找到任意两个不同输入产生相同的哈希值.

在实际应用中，哈希碰撞可能被恶意利用。例如，攻击者可能通过制造大量碰撞来增加服务器查询哈希表的时间，从而导致性能下降或服务瘫痪.为了减少哈希碰撞的影响，可以采取以下措施：

1. 选择高质量的哈希函数。
2. 使用足够大的哈希表以减少碰撞概率。
3. 实现有效的碰撞解决策略，如链接法或开放寻址法。
4. 在必要时动态调整哈希表大小。

总之，虽然哈希碰撞无法完全避免，但通过合理的设计和实现，可以最大限度地减少其对系统性能的影响。

碰撞的影响依程序而异。当散列函数和数字指纹用于标识相似数据时，程序被设计成尽可能增加相似但不同的数据发生碰撞的可能性；校验和则不同，要求尽可能使得相似的数据输出不同，而不考虑不同数据输出相同的情况。

参见

• 生日攻击

外部链接

• http://permabit.wordpress.com/2008/07/18/what-do-hash-collisions-really-mean/ （页面存档备份，存于互联网档案馆）