王朝网络
分享
 
 
 

看看Md5自然产生重复的概率

王朝other·作者佚名  2006-01-10
宽屏版  字体: |||超大  

问题:假设有十万个不同的文件,每个文件对应于一个MD5。这十万个MD5中,存在两个相同的MD5的概率是多大?

答:

MD5是128位hash码(4个整数,每个整数4个字节)。我们假设它的计算结果是足够随机和足够分散的。因此,一个文件的MD5码,有2的128次方(用2e128表示,下面都用这种方式表示)个可能。进而

我们知道,随意找出来的两个文件的MD5码相等的可能性,是2e128分之一。下面讨论中,我们用r来表示这个概率(即r=2e-128)。

假设这十万

个MD5是一条条插入到数据库中的。第二个MD5插入时,它跟第一条重复的概率是r。第三条url插入时,它有可能跟第一条重复,也有可能跟第二条重复,

因此总发生重复的概率是2×r。同理,第四条插入时发生重复的概率是3×r...第n条插入时发生重复的概率是(n-1)×r。n个MD5码,其中有两个重复的概率是上面那么多个可能的加和。

因此,n个md5码,自然产生重复的概率是

(1+2+3+...+(n-1))×r = (1/2)×n×(n-1)×r

以n=10e4,r=1/2e128 代入,得到重复的概率为:

(1/2)×10e4×(10e4-1)×(1/2e128)

10e4-1约等于10e4,上式可以简化:

(1/2)×10e8×(1/2e128)

=10e8/(2×2e128)

我们使用近似2e10 = 1024 = 10e3,那么

=10e8/(10e9*2e89)

=1/(10*2e89)

=1/(10*10e27)

=1/(10e28)

这个数字小得可怜,到底有多小,我们来算一下:一般福利彩票的中头奖的机会,约一百万份之一,即1/10e6。而上面的数字,相当1/10e22个一百万份之一。也就是说:相当于某人买了一亿亿亿次福彩,每次都中头奖的概率。

结论:对于十万条数据,发生MD5冲突的概率非常小,可以忽略不计。

那么,大约要多少个文件才能产生自然重复呢?

根据上面的计算,对于N个MD5码的集合,存在重复的概率是

(1/2)*(N/2e64)e2

因此,只有N大到可以与2e64比拟,才需要考虑它的冲突问题。

2e64是怎样的一个数字?

2e64是4G个4G。目前32位系统的内存寻址范围才是区区4G。

形象地说就是:如果一台电脑上可以存放四十亿(4G)个文件,而系统中有四十亿台这样的电脑。那么,这么多的文件数才会令到系统自然产生重复。

所以MD5码作为系统的索引是非常可靠的。

补充:上面对于MD5的计算,并未考虑到人为制造的MD5冲突(现在已经有方法可以制造有冲突的MD5码了),也未考虑到计算MD5码时,因数据补零而造成的MD5冲突。事实上,在一般的系统中,并没有必要考虑这两种情况。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
>>返回首页<<
推荐阅读
 
 
频道精选
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有