哈希算法详解
本文详细介绍哈希算法的定义、原理及其广泛的应用场景。
1. 哈希算法基础
1.1 定义
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。
2. 哈希算法应用
2.1 安全加密
哈希算法有很多，但对于用于加密的哈希算法来说，有两点格外重要：
- 很难逆推原始数据
- hash冲突概率小
常见的加密算法
- MD5 消息摘要算法
- SHA 安全散列算法
- DES 数据加密标准
- AES 高级加密标准
鸽巢原理
没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。
哈希算法因哈希值长度有限而无法避免冲突，但因其冲突概率极低在有限资源下很难破解，且实际开发中要权衡加密算法的破解难度和计算时间来选择合适算法。
2.2 唯一标识
如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的元信息（比如图片名称）来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。
任何文件在计算中都可以表示成二进制码串，所以，比较笨的办法就是，拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。
以给每一个图片取一个唯一标识，或者说信息摘要。
比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。
通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
2.3 数据检验
网络传输文件的时候往往会分片成一个个文件块，等所有文件快下载完成后，在合成一个完整的文件，如何检验文件块的安全、正确、完整？
传输前对每个文件块分别取哈希值，传输完成后用同一个哈希算法计算，对比两次哈希值。
2.4 分布式问题：负载均衡
负载均衡算法有很多，比如轮询、随机、加权轮询等。
我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。
通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
2.5 数据分片
如何统计"关键词"出现的次数？
在1TB的日志文件里记录了用户的搜索关键词，快速统计每个关键字被搜索的次数。
两个难点，第一个是文件大，没有办法一次性放入一台机器的内存中处理；第二个是如果只用一台机器来处理这么巨大的数据，时间久。
针对这两个难点，可以先对数据进行分片，然后采用多台机器处理，提高处理速度。
具体思路：
- 在整个数据处理的前期准备阶段，就已经规划好通过某种方式让每台机器都能获取到一部分分片后的日志数据。
- 每台机器都会从分配给自己的那部分日志数据中依次读取每个搜索关键词，然后各自在本机上对读取到的关键词进行哈希函数运算，得到哈希值后再与 n 取模，以此确定这个关键词应该在本机进行后续处理还是要发送给其他机器。
- 一台机器确定某个关键词是要在自己这里处理（也就是取模结果对应的是本机编号）时，它就会对收到的这个关键词进行计数统计。如果之前没出现过，就初始化为 1 次；如果已经出现过了，就把对应的计数加 1。
- 在每台机器都完成了对各自所负责的那部分数据中的关键词的统计处理之后，再通过特定的机制将每台机器统计出来的结果进行合并汇总，最终得到整个 1T 日志文件中每个关键词被搜索的总次数。
如何快速判断图片是否在图库中？
这个问题可以通过哈希算法给每张图片生成唯一标识，然后通过分布式存储系统快速检索。
2.6 分布式存储
分布式缓存。我们有海量的数据需要缓存，所以一个缓存机器肯定是不够的。于是，我们就需要将数据分布在多台机器上。
该如何决定将哪个数据放到哪个机器上呢？我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
一致性哈希算法
一致性哈希算法是解决分布式系统中数据分布问题的一种重要方法，特别适用于节点动态变化的场景。