哈希碰撞是什么？
所谓哈希（hash），就是将不同的输出映射成举世无双的、固定长度的值（又称 ” 哈希值 ”）。它是最常见的软件运算之一。
如果不同的输出失去了同一个哈希值，就产生了 ” 哈希碰撞 ”（collision）。
举例来说，很多网络服务会应用哈希函数，产生一个 token，标识用户的身份和权限。
AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8下面这个字符串就是一个哈希值。如果两个不同的用户，失去了同样的 token，就产生了哈希碰撞。服务器将把这两个用户视为同一个人，这意味着，用户 B 能够读取和更改用户 A 的信息，这无疑带来了很大的安全隐患。
黑客攻击的一种办法，就是设法制作 ” 哈希碰撞 ”，而后入侵零碎，窃取信息。
如何避免哈希碰撞？
避免哈希碰撞的最无效办法，就是扩充哈希值的取值空间。
16 个二进制位的哈希值，产生碰撞的可能性是 65536 分之一。也就是说，如果有 65537 个用户，就肯定会产生碰撞。哈希值的长度扩充到 32 个二进制位，碰撞的可能性就会降落到 4,294,967,296 分之一。
更长的哈希值意味着更大的存储空间、更多的计算，将影响性能和老本。开发者必须做出抉择，在平安与老本之间找到均衡。
上面就介绍，如何在满足平安要求的前提下，找出哈希值的最短长度。
生日攻打
哈希碰撞的概率取决于两个因素（假如哈希函数是牢靠的，每个值的生成概率都雷同）。
- 取值空间的大小（即哈希值的长度）
- 整个生命周期中，哈希值的计算次数
这个问题在数学上早有原型，叫做 ” 生日问题 ”（birthday problem）：一个班级须要有多少人，能力保障每个同学的生日都不一样？
答案很出乎意料。如果至多两个同学生日雷同的概率不超过 5%，那么这个班只能有 7 集体。事实上，一个 23 人的班级有 50% 的概率，至多两个同学生日雷同；50 人班级有 97% 的概率，70 人的班级则是 99.9% 的概率（计算方法见后文）。
这意味着，如果哈希值的取值空间是 365，只有计算 23 个哈希值，就有 50% 的可能产生碰撞。也就是说，哈希碰撞的可能性，远比设想的高。实际上，有一个近似的公式。
下面公式能够算出，50% 的哈希碰撞概率所须要的计算次数，N 示意哈希的取值空间。生日问题的 N 就是 365，算进去是 23.9。这个公式通知咱们，哈希碰撞所需消耗的计算次数，跟取值空间的平方根是一个数量级。
这种利用哈希空间不足够大，而制作碰撞的攻打办法，就被称为生日攻打（birthday attack）。
数学推导
这一节给出生日攻打的数学推导。
至多两个人生日雷同的概率，能够先算出所有人生日互不雷同的概率，再用 1 减去这个概率。
咱们把这个问题构想成，每个人排队顺次进入一个房间。第一个进入房间的人，与房间里已有的人（0 人），生日都不雷同的概率是 365/365；第二个进入房间的人，生日举世无双的概率是 364/365；第三个人是 363/365，以此类推。
因而，所有人的生日都不雷同的概率，就是上面的公式。
下面公式的 n 示意进入房间的人数。能够看出，进入房间的人越多，生日互不雷同的概率就越小。
这个公式能够推导成上面的模式。
那么，至多有两个人生日雷同的概率，就是 1 减去下面的公式。
哈希碰撞的公式
下面的公式，能够进一步推导成一般性的、便于计算的模式。
依据泰勒公式，指数函数 ex 能够用多项式开展。
如果 x 是一个极小的值，那么下面的公式近似等于上面的模式。
当初把生日问题的 1 /365 代入。
因而，生日问题的概率公式，变成上面这样。
假如 d 为取值空间（生日问题里是 365），就失去了一般化公式。
下面就是哈希碰撞概率的公式。
利用
下面的公式写成函数。
const calculate = (d, n) => {const exponent = (-n * (n - 1)) / (2 * d)
return 1 - Math.E ** exponent;
}
calculate(365, 23) // 0.5000017521827107
calculate(365, 50) // 0.9651312540863107
calculate(365, 70) // 0.9986618113807388一般来说，哈希值由大小写字母和阿拉伯数字形成，一共 62 个字符（10 + 26 + 26）。如果哈希值只有三个字符的长度（比方 abc），取值空间就是 62 ^ 3 = 238,328，那么 10000 次计算导致的哈希碰撞概率是 100%。
calculate(62 ** 3, 10000) // 1哈希值的长度减少到 5 个字符（比方 abcde），碰撞的概率就降落到 5.3%。
calculate(62 ** 5, 10000) // 0.05310946204730993当初有一家公司，它的 API 每秒会收到 100 万个申请，每个申请都会生成一个哈希值，假设这个 API 会应用 10 年。那么，大概一共会计算 300 万亿次哈希。可能承受的哈希碰撞概率是 1000 亿分之一（即每天产生一次哈希碰撞），请问哈希字符串起码须要多少个字符？
依据下面的公式倒推，就会晓得哈希值的最短长度是 22 个字符（比方 BwQ1W6soXkA1PU120r0yMA），计算过程略。
22 个字符的哈希值，就能保障 300 万亿次计算外面，只有 1000 亿分之一的概率产生碰撞。罕用的 SHA256 哈希函数产生的是 64 个字符的哈希值，每个字符的取值范畴是 0~9 和 a~f，产生碰撞的概率还要低得多。