1. 概述

1.1 什么是哈希算法

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

1.2 如何设计优秀的哈希算法

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

  哈希算法是计算机科学的伟大发明，它的实际应用很多，不同应用对哈希算法的要求侧重点不同，下边主要介绍7中应用。

2. 安全加密

  加密的哈希算法，有两点要求格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。
  鸽巢原理导致哈希算法无法在理论上做到0冲突，但是由于哈希值范围很大，因此实际产生冲突概率极低。
  常用于加密的哈希算法：

1. MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法
2. SHA：Secure Hash Algorithm，安全散列算法
3. DES：Data Encryption Standard，数据加密标准
4. AES：Advanced Encryption Standard，高级加密标准

  在实际开发中要权衡**难度和计算时间来决定究竟使用哪种加密算法。

3. 唯一标识

  唯一标识主要利用哈希算法的不可逆且唯一的特性。
  举个例子：如果要在海量图库中，搜索一张图是否存在，不能单纯地用图片的元信息（比如：图片的名称）来对比，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的状况。那么该如何搜索呢？
  验证两个图片是否相同的办法本质上是比较两个图片转化的二进制数据是否完全一致。

1. 利用哈希算法，截取图片数据片段生成哈希值，将哈希值与图片路径对应存储在库表中，当要查找某张图片时将传入图片进行相同的数据截取，并且生成哈希值。
2. 利用哈希值查找相应图片路径，再将路径下的图片与传入图片转换为二进制比对（这一步避免散列冲突），这样可以极大提高图片查找的执行效率。

4. 数据校验

  数据校验利用哈希算法对输入数据敏感的特点，对数据取哈希值，从而高效校验数据是否被篡改过。
  举个例子：迅雷下载，对于一个大文件，往往需要分块传输，然后组成一个完整电影。但是网络并不安全，怎么判定文件的安全、正确和完整性。
  通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。前面讲过，哈希算法对数据特别敏感。只要文件块的内容有变化，计算出的哈希值就会完全不同。所以，当文件块下载完成，可以通过哈希算法，对下载好的文件块逐一求哈希值，然后跟保存的哈希值对比。如果不同，说明这个文件块不完整或者被篡改了，需要重新从其他宿主机器上下载。

5. 散列函数

  散列函数利用哈希算法更加关注散列后的值能不能平均分布，以及散列函数的执行快慢。
  上一篇讲散列表的博客中已经说明，散列函数的设计是散列表的关键，它直接决定了散列冲突概率和散列性能。
  相对于其他应用，散列函数对散列算法要求低得多，即使出现散列冲突，还有开放寻址和链表法进行解决。

6. 负载均衡

  需求：如何实现一个会话粘滞（session sticky）的负载均衡算法？也就是说，在一次会话中的所有请求都路由到同一个服务器上。
  直接的解决办法：维护一张映射关系表，记录客户端IP地址或者会话ID与服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找对应的服务器编号，然后路由过去。这种方法很简单，但是也有几个弊端：

1. 如果客户端很多，映射表可能会很大，比较浪费内存空间；
2. 客户端下线，上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就很大；

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

7. 数据分片

  需求：假如有1T的日志文件记录了用户的搜索关键词，想要快速统计出每个关键词被搜索的次数，该怎么做呢？
  这个问题有两个难点：第一个是搜索的日志很大，没办法放到一台机器的内存中。第二个是只用一台机器来处理这么巨大的数据，处理时间会很长。
  解决方案：先对数据进行分片，然后采用多台（比如n台）机器进行处理。

1. 从搜索记录的日志文件中依次读取每个关键词，并通过哈希函数计算其哈希值。
2. 哈希值对机器的台数n取模，最终得到值就是该关键词应该被分到的机器编号，保证相同的关键词分配到同一台机器上。
3. 数据分配完成后，由多台机器并行进行统计，最后合并起来就是最终结果。

  实际上，这里的处理过程也是 MapReduce 的基本设计思想。

  需求：如何快速判断图片是否在图库中？
  解决方案：唯一标识应用中已经讲过，对每张图片取唯一标识，构建散列表。但是如果1亿张图片，一台机器肯定无法完成存储。因此需要使用数据分片+唯一标识。

1. 每次从图库中读取一张图片，计算唯一标识，然后与机器个数n求余取模，得到的值就对应要分配的机器编号，然后将该图片的唯一标识和图片路径发往对应的机器构建散列表。
2. 要判断一个图片是否在图库中，通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数n求余取模。假设得到的值为k，那就去编号k的机器构建的散列表中查找。

  如何估算给1亿张图片构建散列表大约需要多少台机器？

1. 散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设通过 MD5 来计算哈希值，长度就是 128 比特，也就是 16 字节。文件路径长度的上限是 256 字节，可以假设平均长度是 128 字节。如果用链表法来解决冲突，那还需要存储指针，指针只占用 8 字节。所以，散列表中每个数据单元就占用 152 字节（这里只是估算，并不准确）。
2. 假设一台机器的内存大小为 2GB，散列表的装载因子为 0.75，那一台机器可以给大约 1000 万（2GB*0.75/152）张图片构建散列表。所以，如果要对 1 亿张图片构建索引，需要大约十几台机器。

  在工程中，这种估算还是很重要的，能让事先对需要投入的资源、资金有个大概的了解，能更好地评估解决方案的可行性。
  实际上，针对这种海量数据的处理问题，都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制。

8. 分布式存储

  互联网面对的都是海量数据、海量的用户。为了提高数据的读取、写入能力，一般都采用分布式的方式来存取数据，比如分布式缓存，需要将数据分布在多台机器上。
  该如何决定将哪个数据放到哪个机器上呢？可以借助前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
  但是，如果数据增多，原来的10台机器已经无法承受了，就需要扩容了，比如扩容到11台机器，这时候麻烦就来了。因为，这并不是简单地加台机器就可以了。原来的数据是通过10来取模的，如果新增了一台机器，就需要对11取模。
  因此，所有的数据都需要重新计算哈希值，然后重新搬移到正确的机器上。这样就相当于，缓存中的数据一下子都失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。如下图所示：

  这时就需要一种方法，使得在新加入一台机器后，不需要做大量的数据搬移操作。这个时候一致性哈希算法就要登场了。参考文章：https://zhuanlan.zhihu.com/p/34985026

9. 思考解答

1.如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？

1. 使用MD5进行加密
2. 字典攻击：如果用户信息被“脱库”，黑客虽然拿到的是加密之后的密文，但可以通过“猜”的方式来**密码，这是因为，有些用户的密码太简单。
3. 针对字典攻击，我们可以引入一个盐（salt），跟用户密码组合在一起，增加密码的复杂度。

2.区块链是一个很火的领域，它被很多人神秘化，不过其底层的实现原理并不复杂。其中，哈希算法就是它的一个非常重要的理论基础。你能讲一讲区块链使用的是哪种哈希算法吗？是为了解决什么问题而使用的呢？

1. 区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体。
2. 区块头保存着自己区块体和上一个区块头的哈希值。这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。
3. 区块链使用的是 SHA256 哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。