怎样区分两个人？用服装、相貌、身材、声音，还是DNA？
没那么复杂，只需要用指纹就可以了。
宇宙万物都有一个唯一标识的特征，比如人类的指纹，老虎和斑马的条纹，豹子的斑点。
信息也是如此，任何一段信息（文本、语音，图片、视频），都能对应一个不长的随机数，用来区分其他信息。这个随机数就叫这段信息的指纹。只要算法设计的好，不同的指纹就很难重复。
信息指纹的关键就是伪随机数生成器算法，将任何一段信息生成等长的伪随机数。常见的算法有MD5,SHA-1，但它们都是有漏洞的。
信息指纹在字节的江湖可以举重若轻地解决问题。
一 查重
在爬虫系统中，要防止重复下载同一个网页。可以把下载过的网页的URL存储在哈希表中。但是现在的URL会很长，而哈希表的存储效率只有50%，导致空间复杂度会很高。怎样能减少存储成本呢？可以使用信息指纹，把URL映射成一个128位的字符串（数字）。
二 加密
生成伪随机数的过程是不可逆的，这对保密很有用途，比如cookie就是用户信息的指纹。
三 权鉴
一些重要的接口，比如支付系统的接口，是需要对请求进行权鉴的。
这样在请求参数里，加一个sign=md5，接收方就不怕收到被篡改的请求了。
不过MD5并不是安全的算法，可以被破解。
破解的方法有：暴力穷举，查字典，彩虹桥法。
四 判断两个集合是否相等
- 暴力穷举法，O(N^2)
- 排序法 ，O(NlgN)
- 哈希，时间和空间复杂度都是O(N)
- 指纹求和。定义一个集合的指纹是每个元素的指纹之和，如果两个集合相等，那么集合的指纹必定相等。当然会有一个绩效绩效的误差，在工程中可以忽略。
五 判断集合是否基本相同
判断两个邮件地址清单，是否基本相同。按照相同的规则（比如尾号相同），随机抽取几个邮件地址，如果其指纹相同，可判断两个清单基本相同。
指纹也可以判断网页是否相同。从网页中找出一组特征词（可以用IDF最大的几个词），这样可以组成一个特征集合。这样只需要判断两个集合是否相等就可以。
Google发明了一种特定的信息指纹——相似哈希（Simhash）,如果两个网页的相似哈希的差别越小，那么其相似度越高。比如指纹有64位，如果有一两位不同，那么网页内容重复的可能性可能大于80%。
判断两个网页是否相似，对搜索引擎非常重要，可以避免建立多余的索引。
Youtube怎样判断视频的原版和盗版？
视频的是由一个一个的帧组成的，一秒钟有几十个帧，但是这些帧的相似度很高。所以只需要抽取关键帧即可，非关键帧只需要存储和关键帧的差异值即可。找到关键帧，就可以组成一个关键帧集合，只需要比较这两个集合是否相等即可。
常见的生成信息指纹算法有MD5和SHA1，确保信息传输的完成性，比如下载，文件传输，IO等
MD5 :Message-Digest Algorithm 5（信息-摘要算法 5）
命令：md5sum file 生成32位16进制数
SHA1：Secure Hash Algorithm 安全散列算法
命令：sha1sum file 生成40位16进制数
参考：《数学之美》， MD5算法
网友评论