哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，得到的二进制值串就是哈希值。 一个hash算法需要满足几点要求：

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

哈希算法的应用

1. 安全加密

• MD5（消息摘要算法）、SHA（安全散列）、DES（数据加密标准）、AES（高级加密标准）等。
• 哈希算法无法做到零冲突（鸽巢原理）：哈希值是固定长度的数据串（如MD5：128bit）因此哈希值的数量也是有限的2^128。对于无限的数据进行哈希算法得到有限的哈希值，肯定会有冲突的。但如2^128已经是个很庞大的数据范围了，想破解非常之难了。
• 实际开发中选取加密算法，要衡量破解难度和计算时间。

2. 唯一标识

通过一个较短的二进制串表示一个很大的数据。

如果想从海量图库中查找一张图片。因为图片元数据（名称、地点等信息）可能会相同没办法唯一标识一张图片。因此我们可以从图片的二进制码串（任何文件在计算中都可以表示成二进制码串）前中后三个部位取100B数据，把这300Byte合并通过哈希算法（如MD5）得到一个哈希值作为图片的唯一标识。在根据前边学的查找相关的算法，可以把图片的唯一标识作为key，和相应图片文件在图库中的路径信息都存储在散列表中，在散列表中通过key可以在O(1)下查找到图片。

3. 数据校验 数据在网络中进行传输，很有可能被恶意修改，导致文件无法打开，甚至导致电脑中毒。如何检测数据是否被篡改呢？哈希算法对数据很敏感，只要数据有一点变化生成的哈希值就会变化，因此可以对数据进行哈希，得到哈希值。当收到文件时，再对文件进行相同哈希函数计算得到哈希值和原始哈希值进行比较，不同则说明数据被篡改了。

4. 散列函数 之前的散列函数也是哈希算法的一种应用，只不过它更关注散列后的值是否平均分布，散列函数执行的快慢，因此散列函数一般比较简单，追求效率。

对用户密码进行传输如何做更安全呢？ 仅对密码进行MD5/SHA加密还是有很大的可能被攻破，因为有的用户设置的密码太简单（如：654321等）攻击者可以进行字典攻击：字典中存储攻击者可能猜到的各种密码组合和对应加密后的数据串，这样拿到加密后的数据，在字典中查找，很可能就破解了。

针对字典攻击，可以引入一个盐，和用户密码组合在一起增加密码复杂度，在进行哈希算法加密，这样就提高了破解难度。

哈希算法解决分布式问题

5. 负载均衡 如何把同一个客户端上的所有请求都路由到同一个后端服务器上呢？

• 最简单的方法：维护一张客户端IP和服务器编号的映射关系表。客户端每次发请求，找到表中对应的服务器编号，请求。但是这种方式有几个弊端：
  • 客户端很多，表会很大，浪费内存空间；
  • 客户端上线下线、服务器扩容缩容都会导致映射关系失效，表的维护成本高。
• 哈希算法：对客户端的IP地址计算哈希值，再将哈希值与服务器编号列表的大小进行取模，得到的值加上服务器编号起始值就得到了服务器编号。这样就保证了同一个IP最终计算得到的编号值都是一样的（并不需要保证服务器一直都是同一个）。

6. 数据分片

如果有1T的日志文件，记录了用户的搜索关键字，如何快速统计出每个关键词被搜索的次数呢？

最开始想到了桶排序，把相同的数据放同一个桶中，最后统计桶中数据个数。但这样就有两个问题：

• 有1T的数据，一起取出来计算机内存根本放不下，而且还要为桶开辟空间。
• 如何把一个数据放到一个桶中呢？通过哪种映射关系呢？

结合上述问题的到的处理方法：一个计算机放不下，可以用多台计算机并发处理。这样我们可以把每台计算机看做一个桶。那么如何把数据放到对应的计算机中呢？想到了哈希算法：对每个数据计算哈希值，然后再根计算机编号列表大小n取模的计算机编号，数据就放到对应编号的计算机中。这样相同数据肯定放在同一个计算机中。在每个计算机在分别计算相同数据出现的次数，最后在合并结果即可。

这种思想（MapReduce）结合了桶（数据分片）、哈希算法、散列函数（取模对应列表index）。

如果再1亿张图片中找一张图片，也可以用上述的思想来解决。

针对这种海量数据问题的处理，都可以采用多机分布式处理，借助这种分片思路可以突破单机内存、CPU等资源的限制。

7. 分布式存储 数据分片时如果增加了一台计算机，那么原本散列函数得到的结果就都失效了，需要全部数据重新计算一次。需要一致性哈希算法。（待补充）