在
实用密码学工具——编码与解码中说到了编码解码的本质是信息相同的两个空间之间的映射关系，今天谈论的Hash则是把信息从任意大小的空间向指定大小的空间映射的一个工具。
在我刚学完C的语法的那个时候，看过某本（国产二手）数据结构书。书上谈论的哈希表让我整整一天没有弄明白，这个奇怪的名词到底说的是什么。其他的数据结构都可以顾名思义，链表就是一个个节点用指针等方式串起来，数组就是一组元素能够按数字编号做索引随时查改。哈希是个啥？在看了几个例子，稀里糊涂地反复看了几遍“碰撞解决”后，我打算放弃这部分内容。
现在回头来看，国产二手货真是害人不浅，就和应试教育一样只教会了答案，有没有懂全凭悟性。于是在写这篇时，我在一开始就给Hash一个直接的定义。编码解码处理的是完全相同的信息，不管映射前后空间如何变化，编码和解码保存的信息是相同的，处理前后的空间大小至少要能存放下原有的信息。相比较而言，Hash是映射到指定大小的空间，不论这个空间是否足够容纳原信息，也完全不考虑逆向操作的可能，Hash要做到的，只是提取一些原信息的特征，使得映射后空间中的信息能够一定程度上用于区别映射前的信息。
生活中，我们常常做一些可以被认为是Hash的事情。我们会说”那个戴眼镜的男的，那个穿红衣服的女的“之类，把一个人用简单的性别（男/女）+衣着（有限的几个形容词）就给“代表”了。Hash出场的场合正是这个，用简单的方式，去区别原信息。
网上下载了一个可执行程序文件，怎么才能知道下载过程中没有错误，下载的东西没有被掉包，没有被安插木马？算一个Hash值，然后和网站上给出的Hash值对比一下，如果你信任那个网站上的值，则你就（基本上）可以信任你手上的这个文件（当然，这里其实有很多细节）。这类Hash的应用叫做Checksum，比较两段信息，并不需要每次都完整地从头对比到尾，只需要预先各算一次Hash值作为各自的Digest，以后只要比较Digest即可判断是否（很可能）是同一个文件。当然，从这个意义上来说，其实文件大小就是一个Hash值。
设计用来处理固定长度内容的，对抗随机错误的CRC和设计用来处理不固定长度内容的，对抗人为修改的密码学安全的MD系列（MD4、MD5、MD6），SHA系列（SHA-1、SHA-2、SHA-3）Hash有着不同的目标，自然也会有不同的属性。所谓的密码学安全是指，Hash运算是单方向的，难以从Hash值知晓原数据的属性，包括：
给定Hash值H，难以找到其对应的数据（但从数据到H相对很简单）给定数据A的Hash值为H，难以构造出Hash值同为H但内容不同的数据B
给定hash值H，难以找出其对应得一对数据A和B（碰撞）
这里所说的“难以”，不仅仅是映射前数据量大于映射后空间容量的这种“理论上不可能”，还包括映射前数据量小于映射后空间容量，但不经过Hash计算这个单向的过程，“实际上无法区别”哪个映射前数据会对应与映射后的Hash值。
这类Hash函数有这样两个特点：
一个是设计的Hash值一般比较长，最常用的MD5是128-bit，SHA-1是160bit，推荐使用的SHA-2至少是224bit，最多到512bit。这是因为，他们面对的输入空间是无穷的，输出空间要足够大才能保证足够的强度不足以被暴力穷举法破解，同时也可以显著减少不同的输入产生相同输出的情况（碰撞）。
另一个是Hash值看起来非常随机，不论输入信息如何挑选，输出的Hash值每一位是0还是1的概率都相同。这也是开始设计时决定的，如果看起来不随机，那么就表示可以由某种规律构造输入信息，得到某些位的概率比另外一种构造的输入要大，也就是依照某种规律就能大大降低了找到另一个会“碰撞”的输入信息的难度，就不符合“密码学安全”的假设了。
很不幸的是，目前MD4、MD5、SHA-1均已经被“攻破”，即“难以”的难度可以通过某些方法大大简化（实际上相比于计算Hash值依然非常困难，依然是单向的）。但是，这并不意味这日常不能使用这些Hash算法。事实上，MD4广泛用于电驴（eDonkey2000）网络的文件标识，MD5也被广泛用于储存密码。仅仅表示，这些算法得到的Hash已经不如设计之初的安全，有被“破解”的风险。很多不需要安全，但可以利用到这些Hash算法其他方面属性的地方，依然可以使用。安全，仅仅是密码相关Hash函数所需要的属性。目前推荐使用的是密码学安全Hash算法是SHA-2。SHA-3采用了和SHA-2不同的设计理念，防止未来SHA-2被“破解”时没有安全的方法可以使用。
另一类Hash的应用则是之前提到的“哈希表”Hash Table，同样是用简单的方式去区别原信息。Hash Table是储存Key-Value Pair的一种数据结构，计算Value的Hash值作为Key，在这个Key相关的位置保存这个Value；以后要找修改这个Value时，只需要再次计算Key，就能直接找到它的储存位置，而不用考虑访问表中的其他KVP。每次操作的计算复杂度是O(1)——不随着Hash Table储存的元素的数量而变化。
当然，上面所描述的Hash Table是perfect hash table，即不会发生碰撞——两个不同的Value算出的一定是不同的Key；而实际应用时，需要储存的KVP的数量常常会大于Hash Key空间的容量；即便Hash Key的空间足够大，依然可能存在一定概率的碰撞，在使用Hash Table时，需要考虑到碰撞后的策略，从性能出发，也要选择更好的Hash算法和更合适的Hash值空间大小。一些碰撞少的Hash算法，还用来产生UUID，使得在一个分布式系统中绝大部分时候都不需要需要统一分配ID。
最后，稍稍提一下Bloom Filter。Hash值相同的信息不一定相同（碰撞），Hash值不同的信息一定不相同。Bloom Filter就是把很多信息的Hash值按位“或”的方式合并起来，这样，如果某个信息的Hash值不在Bloom Filter里，则该信息一定是第一次经过Bloom Filter；反之，一个信息的的Hash值在Bloom Filter里，则有一定概率该信息已经经过了Bloom Filter。
P.S. Hash还用来隐藏密码，实际上是密码学安全Hash应用的一个特例，日后谈论KDF的时候会说到。
