md5是128位hash码(4个整数,每个整数4个字节)。我们假设它的计算结果是足够随机和足够分散的。因此,一个文件的md5码,有2的 128次方(用2e128表示,下面都用这种方式表示)个可能。进而我们知道,随意找出来的两个文件的md5码相等的可能性,是2e128分之一。下面讨论中,我们用r来表示这个概率(即r=2e-12。
假设这十万个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/2e12
10e4-1约等于10e4,上式可以简化:
(1/2)×10e8×(1/2e12
=10e8/(2×2e128)
我们使用近似2e10 = 1024 = 10e3,那么
=10e8/(10e9*2e89)
=1/(10*2e89)
=1/(10*10e27)
=1/(10e2
这个数字小得可怜,到底有多小,我们来算一下:一般福利彩票的中头奖的机会,约一百万份之一,即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冲突。事实上,在一般的系统中,并没有必要考虑这两种情况。
分享到:
相关推荐
(1)用带表头的链表存放输入的数据,每...假设有两个进程同时存在于一个应用程序中,第一个进程连续在屏幕上显示字符“X”,第二个进程不断检查键盘上是否有输入,若有则读入用户键入的字符,将其保存到键盘缓冲区中。
ISO文件标准化样本文件适用于一阶文件二阶文件三阶文件.pdf
此仓库中的每个目录对应于一个不同的课程。 其中的每一个都可能包含课程中提出的项目,或者仅包含课程中少量的代码示例 另外,这里还将提供有关在HackerRank和其他挑战平台上发现的问题的解决方案的文件。 每个都在...
matlab开发-计算和声和声速垂直于一个文件。给定垂直声速剖面,计算某一深度的谐波平均声速。
捷克共和国警方通常每月定期收集和发布有关全国交通事故的详细数据。该数据集涵盖了地理位置、天气状况、...pedestrian.csv:文件中的每一行都对应于一个不同的涉及行人的交通事件,并将各种与事件相关的属性捕获为列。
但是,如果你有多个文件,想要同时替换它们里面的一些相同内容,显然不是其简单的替换功能就能够达到的。要想批处理完成N个文件的文本同时替换,我给大家推荐一个小工具——Replace Plus。它是一款绿色小软件,并不...
有两个进程同时存在于一个程序中。其中第一个进程在屏幕上连续显示‘A’字符,与此同时,程序不断检测是否有键盘输入,如果有,就读如用户键入的字符并保存到输入缓冲区中。在用户输入时键入的字符不立即显示在屏幕...
一个扩展让 UIImageView能够聚焦于一个图片中的人脸,当使用AspectFill时
附件十 系统/用户测试计划 附件十一 系统/用户测试报告 附件十二 试运行计划 附件十三 数据迁移计划 附件十四 数据迁移报告 附件十五 试运行报告 附件十六 系统验收报告 附件十七 系统上线计划 附件十八 系统验收...
近日,据外媒报道,微软申请了一项新的专利。这份专利的内容是将红外传感器和可见光传感器集成于一个摄像头中。
假设(i)导致至少一个无质量的中微子,并且如果假设其他两个中微子是大块的,则在具有对角线S½的基础上仅允许中微子质量矩阵具有四个纹理。 这些纹理中的两个包含一对简并的中微子。 假设(ii)可用于确定中微子...
ChangViewInFrameAn android demo,通过Button控制切换View。每个View以LinearLayout为单位,平行存在于一个activity的同一个FrameLayout中。
windows服务程序和桌面程序集成于一个EXE的源代码(双模程序) 1. 参考系列文章:https://blog.csdn.net/sensor_WU/article/details/131149795(共7篇) 2. 总共包括4个程序,分别是: 1)VCL桌面程序 2)windows...
102种花卉图片数据集 ...随着标签从1到102的进展,每个数字对应于一个不同的花卉类别,提供了丰富的花卉种类。该数据集是训练机器学习模型以准确分类和识别各种花型的绝佳资源。(该数据集共有8198张照片)
在间隙方程包含两个贡献的模型中研究了夸克在基本和伴随表示中的手性对称断裂跃迁,其中间隙方程包含两个贡献,一个包含约束传播子,另一个对应于一次穿戴的动态大质量胶子的交换。 当夸克在基本表示中时,限制作用...
动态加载指定目录下的groovy脚本,并将其注册为groovy bean,放置于ApplicationContext容器中,并使用命名空间进行分类区分(一个namespace对应于一个ApplicationContext)。同时能够动态感知到groovy脚本的新增、修改...
网络游戏-用来在分布于一个智能网络中的业务节点间部署业务模块的方法和设备.zip
文本到Sql 基于文本文件创建 SQL CREATE 脚本。 默认使用当前目录下的所有 sql 文件。 运行TxtToSql.exe --help以获取选项。 需要 .Net Framework (Windows) 或 Mono (Mac/Linux)。... 假设您有一个看起
然而,分布式计算尚未完全落实,只存在于一个概念证明型版本中。 JDMP主要的优点在于一致的数据表示。对于Linux来说,一切事物均是文件,而对于JDMP来说,一切事物均是矩阵!例如,可以将几个矩阵组合成一个变量,如...
每个铜公放一个层,每个铜公都可以给它命名一个名称,这个名称在操作铜公的过程中发挥不同作用,如在查找铜公过程中,开料过程中,出放电数过程中,后处理过程中都有不同的作用。下面就对这套电极模块的必要介绍项...