哈希算法

哈希算法即为将任意长度的二进制值串映射为固定长度的二进制值串。

哈希算法的一些要求：

从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法)；
对输入数据非常敏感，哪怕原始数据只修改了一个Bit,最后得到的哈希值也大不相同;
散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小;
哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

哈希算法的应用场景

应用一:安全加密

常见的加密算法MD5(MD5消息摘要算法)，SHA(安全散列算法)，DES(数据加密标准)，AES(高级加密标准)。

对于加密算法中四点要求中的两点格外重要，一是很难根据哈希值反向推导出原始数据，第二是散列冲突的概率要很小。

哈希算法无法做到零冲突，如MD5，能表示的数据是有限的，最多表示2^128个数据。所以散列冲突的概率要小于1/ 2^128。即便哈希算法存在冲突，在有限的时间和资源下，哈希算法还是很难破解的。

没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。比如SHA- 256比SHA-1要更复杂、更安全，相应的计算时间就会比较长。密码学界也一直致力于找到一种快速并且很难被破解的哈希算法。在实际的开发过程中，也需要权衡破解难度和计算时间，来决定究竟使用哪种加密算法。

应用二:唯一标识

在海量图库中搜索一张图是否存在时，可以给每个图片取唯一标识比如信息摘要，可以在图片的二进制码串开头取100字节，中间100字节，结尾100字节，然后300个字节放在一起，通过哈希算法得到一个哈希字符串，用作图片的唯一标识符。通过这个来判定是否在图库中可以减少很多工作量。

如果还想继续提高效率,我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识。

如果不存在，那就说明这个图片不在图库中;如果存在，我们再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在;如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。

应用三:数据校验

哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再下载这个文件块。

应用四:散列函数

散列函数也是哈希算法的一种应用。相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，都可以通过开放寻址法或者链表法解决。散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。

应用五:负载均衡

负载均衡算法有很多，比如轮询、随机、加权轮询等。实现一个会话粘滞(session sticky)的负载均衡算法。也就是同一个客户端在一次会话中的所有请求都路由到同一个服务器上。需要借助哈希算法高效解决：

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

应用六：数据分片

1.统计“搜索关键词”出现次数

假设有1T日志文件记录了用户搜索关键词，需要快速统计每个词的搜索次数。两个难点，一是搜索日志很大，没法放到一台机器内存中，二是只用一台机器处理，处理时间很长。

可以对数据进行分片，然后采用多态机器并行处理。从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到了同-个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

这就是MapReduce的基本设计思想。