# 从生日悖论谈哈希碰撞

1. 哈希的映射压缩和冲突
2. 生日悖论
3. CRC32的冲突分析

## 4. CRC32的碰撞概率

CRC32的碰撞问题本质上可以从生日悖论的角度来分析，相当于计算在有N个输入的情况下出现碰撞的概率。假设现在有K个输入，不出现冲突的概率计算(将42亿用S表示)：

• 第一个输入 1/S
• 第二个输入 (S-1)/S
• 第三个输入 (S-2)/S
• ……
• 第k个输入 (S-k+1)/S

//http://www.backplane.com/matt/crc64.html
output.16 Count 18134464/18200000
output.17 Count 18068928/18200000
output.18 Count 17937856/18200000
output.19 Count 17675712/18200000
output.20 Count 17151424/18200000
output.21 Count 16103198/18200000
output.22 Count 14061250/18200000
output.23 Count 10770169/18200000
output.24 Count 7092360/18200000
output.25 Count 4153742/18200000
output.26 Count 2259269/18200000
output.27 Count 1179721/18200000
output.28 Count 603421/18200000
output.29 Count 305089/18200000
output.30 Count 153722/18200000
output.31 Count 77254/18200000
output.32 Count 38638/18200000
output.33 Count 19232/18200000
output.34 Count 9652/18200000
output.35 Count 4914/18200000
output.36 Count 2343/18200000
output.37 Count 1204/18200000
output.38 Count 637/18200000
output.39 Count 302/18200000
output.40 Count 152/18200000
output.41 Count 75/18200000
output.42 Count 52/18200000
output.43 Count 21/18200000
output.44 Count 13/18200000
output.45 Count 7/18200000
output.46 Count 1/18200000
output.47 Count 1/18200000
output.48 Count 1/18200000
output.49 Count 0/18200000
output.50 Count 0/18200000
output.51 Count 0/18200000
output.52 Count 0/18200000
output.53 Count 0/18200000
output.54 Count 0/18200000
output.55 Count 0/18200000
output.56 Count 0/18200000
output.57 Count 0/18200000
output.58 Count 0/18200000
output.59 Count 0/18200000
output.60 Count 0/18200000
output.61 Count 0/18200000
output.62 Count 0/18200000
output.63 Count 0/18200000
output.64 Count 0/18200000

• 维基百科-生日悖论
• CRC冲突测试报告