哈希算法：如何利用哈希算法解决实际问题？

        哈希算法的定义和原理：将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则，就是哈希算法。而通过原始数据映射之后得到的二进制值串就是哈希值。

        设计一个优秀的哈希算法，需要满足下面几点要求： 

       哈希算法的应用非常多，选择常见的七个进行说明。分别是：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

        最常用于加密的哈希算法是MD5（MD5 Message-Digest Algorithm,MD5消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。除此之外，还有很多其他加密算法，比如DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）等。

        对于用于加密的哈希算法来说，前面讲的四点要求中有两点格外重要：1.很难根据哈希值反向推导出原始数据；2.散列冲突的概率要很小。对于第一点，这是加密的目的，对于第二点，理论上没法做到完全不冲突。

        鸽巢原理：如果有10个鸽巢，有11只鸽子，那肯定有1个鸽巢中的鸽子数量超过1，换句话说，肯定有2只鸽子在一个个鸽巢里。

       【为什么哈希算法无法做到零冲突？】哈希算法产生的哈希值的长度是固定且有限的。比如MD5算法，哈希值是固定128位的二进制串，能表示的数据有限，最多是2^128个数据，当对2^128+1个数据计算哈希值的时候，必然会存在哈希值相同的情况。

        虽然哈希算法存在散列冲突的情况，但是哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。对于有2^128个不同哈希值的MD5算法，散列冲突的概率要小于1/2^128。

        所以，当拿到一个MD5哈希值，希望通过毫无规律的穷举方法找到跟这个MD5值相同的另一个数据，耗费的时间应该是个天文数字。所以即便哈希算法存在冲突，但是在有限的时间和资源下，哈希算法还是很难被破解的。但是，没有绝对安全的加密，越是复杂、越难破解的加密算法，需要的计算时间也越长。在实际的开发过程中，也需要权衡破解难度和计算时间，来决定究竟使用哪一种加密算法。

        问题：想在海量的图库中，搜索一张图片是否存在？

       方法一：拿图片文件在计算机中的二进制码串，与要找的图片的二进制码串进行一一对比，如果相同，则说明图片在图库中存在。但是因为每个图片，小则几十KB，大则几MB，转化为二进制是一个非常长的串，对比起来非常耗时。

       方法二：给每个图片取一个唯一标识，或者说信息摘要。比如可以从图片的二进制码串开头，中间，结尾分别取100个字节，然后将这组合以后的300个字节的码串，通过哈希算法，得到一个哈希字串，用它作为图片的唯一标识。通过这个唯一标识来判断图片是否在词库中，这样就可以减少很多工作量。

       如果还想继续提高效率，可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中，可以先通过哈希算法对这个图取唯一标识，然后在散列表中查找是否存在这个唯一标识。如果不存在，就说明图片不在图库里；如果存在，通过散列表中存储的文件路径，获取已经存在的图片，跟现在的图片做全量比较，看是否完全一样。如果一样，说明存在，如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。

       我们从多个机器上并行下载一个2GB的电影，这个电影文件可能会被分割成很多文件快（比如100块，每一块大约20MB）。等所有文件都下载完成之后，再组成一个完整的电影文件就行了。

       但是网络传输的不完全，下载的文件块有可能被宿主机器恶意修改过，又或者下载过程中出现了错误，所以下载的文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错，就会导致最终合并的电影无法观看，甚至导致电脑中毒。那么，如何来检验文件块的安全、正确、完整呢？

       解决方法：通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中，当文件块下载以后，可以用相同的哈希算法对下载好的文件块逐一求哈希值，然后跟种子文件中的哈希值对比。如果不同，说明这个文件块不完整或是被篡改了，需要重新在其他宿主机器上下载这个文件块。这其中就是利用，哈希算法对数据敏感的特点，只要文件块的内容有一丁点的改变，最后计算得到的哈希值就会很不同。

       散列函数也是哈希算法的一种应用。相对于哈希算法的其他应用，散列函数对于哈希算法散列冲突要求低很多。即使出现个别散列冲突，只要不是过于严重，都可以通过开放寻址法或是链表法进行解决。

       散列函数对于哈希算法计算得到的值，不关注能否反向解密，更加关注的是值能否平均分布。也就是说，一组数据能否均匀地散列在各个槽中。

        问题：需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上？

        方法一：维护一张映射关系表，这张表的内容是客户端IP地址或者会话ID，与服务器编号的映射关系。客户端每发一次请求，都在映射关系表中查找应该路由到的服务器编号，然后请求编号对应的服务器。这种方法很直观，但是也有几个缺点：

       方法二：通过哈希算法，对客户端IP或者会话地址ID计算哈希值，将取得的哈希值与服务器列表大小进行取模运算，最终得到的值就是应该别路由到的服务器编号。这样，就可以把同一个IP过来的所有请求，都路由到同一个后端服务器上。

        问题：假如我们有1T的日志文件，这里记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？

      【分析】1.搜索日志很大，没办法在一台机器上存储；2.如果只用一台机器处理数据，处理时间会很长

        解决办法：先对数据进行分片，然后采用多台机器处理的方法，来提高处理的速度。用n台机器并行处理，从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希算法计算得到哈希值，跟n取模，得到最终的值就是应该被分配的机器编号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。每个机器分别计算关键词出现的次数，然后合并起来就是最终的结果。

        互联网中的海量数据，为了方便数据的读取、写入能力，一般采用分布式的方式来存储数据，比如分布式缓存。海量的数据需要缓存，一个缓存器肯定不够。于是，就需要将数据分布在多台机器上。那么该如何决定哪个数据放到哪个机器上呢？这个可以借助前面已经讲到过的数据分片思想。对数据取哈希值，然后与机器个数取模，得到的值就是数据应该存储的机器编号。

        扩容1个机器，会带来麻烦。假如原来的数据与10取模，现在与11取模，那么所有的数据都需要重新计算哈希值，然后重新搬移到正确的机器上。这样就相当于，缓存中的数据都一下子失效了，所有数据请求都会穿透缓存，直接去请求数据库，这样就会发生雪崩效应，压垮数据库。

        我们需要一种方法，在增加一台机器以后，不需要做大量的数据搬移。这时候，一致性哈希算法能解决这个问题。

        假设有k台机器，哈希值的范围是[0,Max]。我们将整个范围划分为m个小区间，m远大于k，每个机器负责m/k个小区间。当有新的机器加入，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中，这样，既不需要全部重新哈希、搬移数据，也保持了各个机器上数据量的均衡。（具体如何操作实现，还是有点模糊）