哈希函数为何需单射？碰撞为何是哈希表的问题？

关于哈希函数单向性与哈希表“逆推”的误解 #

你混淆了密码学哈希函数和哈希表用的散列函数的特性：

• 密码学哈希（比如MD5、SHA-256）确实是单向的，核心需求是防篡改、难逆推，用于加密、签名场景。
• 哈希表的散列函数不需要单向，它的核心作用是把任意键映射到一个有限范围的整数（数组索引），目的是快速定位存储位置。哈希表中根本不需要“对哈希函数求逆”——我们存储的是完整的(key, val)对，哈希值只是用来找到该键值对应该存在的数组位置，之后直接对比原始键就能确认匹配，完全不需要从哈希值反推键。

为什么碰撞会导致旧键覆盖？f和g的操作差异 #

哈希表的底层是一个数组，默认情况下（不处理碰撞），数组的每个索引位置只能存储一个键值对：

• 对于单射函数g，每个键的哈希值唯一，插入时直接把(key, val)放到对应索引位置，查找时计算哈希值直接定位到该位置，删除同理，所有操作都是O(1)。
• 对于f这种多对一的函数，当插入"a"时，它被放到索引1；再插入"b"，哈希值也是1，此时如果不处理碰撞，就会直接把索引1位置的"a"替换成"b"，旧键"a"就被覆盖丢失了。如果用链地址法处理碰撞，索引1位置会变成一个链表，插入时需要先遍历链表确认键是否已存在（避免重复），查找时要遍历链表逐个对比键，删除也要遍历找到对应节点——这些操作的复杂度会从O(1)退化到O(n)（n是链表长度），自然比g难处理。

为什么判断键存在的复杂度不同？ #

• 对于g：每个键对应唯一哈希值，计算哈希值后直接访问数组对应位置。因为没有碰撞，这个位置要么是空（键不存在），要么就是目标键的键值对（直接对比键即可），整个过程只需要一次数组访问和一次键对比，时间复杂度是O(1)。
• 对于f：所有键的哈希值都是1，它们都存在数组索引1的链表中。要判断某个字母是否存在，必须遍历链表的每一个节点，逐个对比键，直到找到匹配项或遍历结束。链表长度是n（26个字母），所以时间复杂度是O(n)。

内容的提问来源于stack exchange，提问作者NovicePatience