仅供个人记录和复习

Hash函数：数字摘要

我关于Hash函数和Hash值的知识还是在Minecraft里学的。

数字摘要技术就是用Hash函数（散列函数，或者哈希函数，我习惯叫哈希）将任意长度的数据变成固定长度的数据的技术。关于哈希函数是怎么做到这一点的（也就是算法），我不会仔细记录（不过是一些很简单的办法，比如分成一些小段之后加起来，除一个数后取余数之类的）。注意，哈希函数与其说是一个函数，不如说是一种方法：它没有特定的算法，只要能起到作用就可以了，最知名的算法如MD5和SHA-1。

容易看出，哈希函数一定是一种压缩映射，输入的空间远大于输出的空间，值域比定义域小很多。哈希函数的性质：

1. 不同的输入值可能得到相同的输出值（这并不是绝对的，例如线段上的点数量和直线上的点数量相等）；

2. 输出值不同，输入值一定不同，但输入值不同，输出值可能相同；

3. 哈希函数缺乏逆向规律，无法通过输出倒推出输入，对数据本身的保密性很好。

哈希函数到底有什么用？想象一堆数据被保存在我这里，我收到一些数据，希望找到这些数据是不是在我这里存过，如果存过的话存在哪里。唯一的办法就是把这些收到的数据和我存着的数据一个个对比一下了，效率低得要命。

这就是最开始设计哈希函数的目的。存储的记录内容和记录的位置没有关系，所以必须得挨个比对。假如记录内容和所在位置是有关的，只需要按照事先制作的表，就能不对比记录的具体内容而直接找到它们的存储地址。

具体来说，在一个表中存在一个函数，可以根据输入的关键字得到包括该关键字的记录在表中的地址，这个函数就是哈希函数（散列函数），这个表就是哈希表Hash Table，哈希函数得到的值（地址Address）就是哈希值（地址）。哈希函数在设计时是用来加快查找速度的，而当在把不定长度的数据变成一定长度的“摘要Digest”时也可以用哈希函数，这个时候输出的哈希值叫做数据摘要。

上文我们提到过，不同的输入可以有相同的输出，这叫做冲突Collision，这要通过开放寻址或者链式地址法来解决，在此不详细记录。