16.哈希算法
1.定义
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。
哈希算法的要求:
- 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
- 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
- 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。
2.用途
2.1 安全加密
MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）；
基于鸽巢理论，哈希算法无法做到零冲突；
字典攻击:黑客维护常用的密码表，与加密后的密码进行逐一匹配；
针对字典攻击，我们可以引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。我们拿组合之后的字符串来做哈希算法加密，将它存储到数据库中，进一步增加破解的难度。
2.2 唯一标识
哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。
场景:图库中搜索是否存在相同的图片
由于任何文件都是以二进制的形式存储的，我们可以给每一个图片取一个唯一标识，或者说信息摘要，比如可以在图片的二进制信息的前、中、后三部分各取100个字节，总计300个字节进行哈希算法(比如MD5)加密，得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
如果为了进一步的提高效率，可以使用散列表存储图片的信息。<唯一标识，图库中的路径>
2.3 数据校验
比如电驴等基于P2P协议的下载工具，将文件拆分为100块，分别下载，如何保证下载的文件正确呢？
分别对这100块文件求哈希值，存放在种子文件中，下载完成后，对文件块依次比较哈希值来判断文件的正确性
2.4 散列函数
散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。
3.分布式系统的运用
3.1 负载均衡
- 那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。
方案一:维护一张映射表
维护一张用户ip或者session ID与服务器的映射表，弊端: - 如果客户端很多，映射表可能会很大，比较浪费内存空间；
- 当客户端上线、下线或者服务器扩容缩容这张表都需要更新，维护成本高；
方案二:使用哈希算法
对用户ip或者session ID进行哈希求值，然后对服务器进行取模，确定服务器
但是对于服务器的扩容或者缩容其实也没有办法很好的解决，这时候就看是否需要维护一张散列表，当服务器发生变化的时候，实时更新散列表；
3.2 数据分片
- 如何统计“搜索关键词”出现的次数？
假如我们有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？我们来分析一下。这个问题有两个难点，第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。
解决办法:先对数据进行分片，然后采用多台机器进行并行处理，从而提高处理速度；
为了提高处理速率，我们采用n台机器进行处理，依次遍历日志文件，对搜索关键词进行哈希求职，然后对n取模，这样哈希值相同的数据在同一台机器上面，这样关键词相同的日志也在同一台机器上，分别计算每一台机器上面的关键词出现的次数，最后汇总就是所有关键词出现的次数。
这也是MapReduce的基本思想；
- 如何快速判断图片是否在图库中？
对于1亿张图片如何处理？
根据图片的摘要信息，先用哈希算法，将一亿张图片分散在不同服务器上，每台服务器各自维护对应的散列表；
查找时，先根据哈希算法确定服务器，然后去服务器维护的散列表中查找；
从而突破单个CPU、服务器的限制。
3.3 一致性哈希
场景:对于数据库缓存，当机器个数发生变化的时候，可能造成缓存全部失效，造成雪崩效应；
解决办法:一致性哈希
假设我们有 k 个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。
