HASH GAME - Online Skill Game GET 300

　　这个问题在数学上早有原型，叫做（birthday problem）：一个班级需要有多少人，才能保证每个同学的生日都不一样？ 答案很出人意料。如果至少两个同学生日相同的概率不超过5%，那么这个班只能有7个人。事实上，一个23人的班级有50%的概率，至少两 个同学生日相同；50人班级有97%的概率，70人的班级则是99.9%的概率（计算方法见后文）。 这意味着，如果哈希值的取值空间是365，只要计算23个哈希值，就有50%的可能产生碰撞。也就是说，哈希碰撞的可能性，远比想象的 高。实际上，有一个近似的公式。

　　防止哈希碰撞的最有效方法，就是扩大哈希值的取值空间。 16个二进制位的哈希值，产生碰撞的可能性是 65536 分之一。也就是说，如果有65537个用户，就一定会产生碰撞。哈希值的长度扩大到 32个二进制位，碰撞的可能性就会下降到 4,294,967,296 分之一。 更长的哈希值意味着更大的存储空间、更多的计算，将影响性能和成本。开发者必须做出抉择，在安全与成本之间找到平衡。 下面就介绍，如何在满足安全要求的前提下，找出哈希值的最短长度。

　　62 ^ 3 = 238,328 ，那么10000次计算导致的哈希碰撞概率是100%。 哈希值的长度增加到5个字符（比如 abcde ），碰撞的概率就下降到5.3%。 现在有一家公司，它的 API 每秒会收到100万个请求，每个请求都会生成一个哈希值，假定这个 API 会使用10年。那么，大约一共会计算 300万亿次哈希。能够接受的哈希碰撞概率是1000亿分之一（即每天发生一次哈希碰撞），请问哈希字符串最少需要多少个字符？ 根据上面的公式倒推，就会知道哈希值的最短长度是22个字符（比如 BwQ1W6soXkA1PU120r0yMA ），计算过程略。 22个字符的哈希值，就能保证300万亿次计算里面，只有1000亿分之一的概率发生碰撞。常用的 SHA256 哈希函数产生的是64个字符的哈 希值，每个字符的取值范围是0~9和 a~f，发生碰撞的概率还要低得多。