第 16 章：信息指纹及其应用

信息指纹的用途远不止网址的消重，信息指纹的一个特征是其不可逆性，无法根据信息指纹推出原有信息。

集合相同的判定

• 集合中的元素一一做比较，时间复杂度是 O(N2)
• 先排序后比较，时间复杂度是 O(NlogN)
• 将第一个集合放在散列表中，然后把第二个集合一一和散列表汇总的元素作对比，时间复杂度是 O(N)，空间复杂度 O(N)
• 完美的方法是计算两个集合的指纹，然后直接进行比较。

判定集合基本相同

image.png image.png

信息指纹，可以简单理解为将一段信息（文字、图片、音频、视频等）随机地映射到一个多维二进制空间中的一个点（一个二进制数字）。只要这个随机函数做得好，那么不同信息对应的这些点就不会重合。因此，这些二进制的数字就成了原来的信息所具有的独一无二的指纹。

第 17 章：谈谈密码学的数学原理

算法的共同点：

• 它们都有两个完全不同的样式，一个用于加密，一个用于解密。
• 这两个看上去无关的钥匙，在数学上是关联的。