带着问题来学习：

  1. 如何防止数据库中的用户信息被脱库？
  2. 你会如何存储用户密码这么重要的数据吗？仅仅 MD5 加密一下存储就够了吗？
  3. 在实际开发中，我们应该如何用哈希算法解决问题？

###一、什么是哈希算法？

  1. 定义
    将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。
  2. 如何设计一个优秀的哈希算法？
    1. 单向哈希：
      从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。
    2. 篡改无效：
      对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。
    3. 散列冲突：
      散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。
    4. 执行效率：
      哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈希值。

二、哈希算法的常见应用有哪些？

7个常见应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

  1. 安全加密
    1. 常用于加密的哈希算法：
      • MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法
      • SHA：Secure Hash Algorithm，安全散列算法
      • DES：Data Encryption Standard，数据加密标准
      • AES：Advanced Encryption Standard，高级加密标准
    2. 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。
    3. 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。
  2. 唯一标识
    通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。
  3. 数据校验
    利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。
  4. 散列函数
    散列函数中用到的哈希算法更加关注散列后的值能不能平均分布，以及散列函数的执行快慢。
  5. 负载均衡
    我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。最直接的方法就是，维护一张映射关系表，这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找应该路由到的服务器编号，然后再请求编号对应的服务器。这种方法简单直观，但也有几个弊端：
    • 如果客户端很多，映射表可能会很大，比较浪费内存空间
    • 客户端下线、上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就会很大
      通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
  6. 数据分片
    1. 如何统计“搜索关键词”出现的次数
      1. 有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数
      2. 我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的：为了提高处理的速度，我们用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果
      3. 这里的处理过程也是 MapReduce 的基本设计思想。
    2. 如何快速判断图片是否在图库中
      1. 图库中有 1 亿张图片
      2. 我们同样可以对数据进行分片，然后采用多机处理。我们准备 n 台机器，让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数 n 求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。当我们要判断一个图片是否在图库中的时候，我们通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数 n 求余取模。假设得到的值是 k，那就去编号 k 的机器构建的散列表中查找。
      3. 针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制
  7. 分布式存储
    1. 为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。我们有海量的数据需要缓存，所以一个缓存机器肯定是不够的。于是，我们就需要将数据分布在多台机器上。通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
    2. 问题：如果原来的 10 个机器已经无法承受了，我们就需要扩容了，比如扩到 11 个机器，这时候麻烦就来了。因为，这里并不是简单地加个机器就可以了
    3. 解决方案-一致性哈希算法
      假设我们有 k 个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

三、思考

  1. 如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？
    1. 使用MD5进行加密
    2. 字典攻击：如果用户信息被“脱库”，黑客虽然拿到的是加密之后的密文，但可以通过“猜”的方式来破解密码，这是因为，有些用户的密码太简单。
    3. 针对字典攻击，我们可以引入一个盐（salt），跟用户密码组合在一起，增加密码的复杂度。
  2. 现在，区块链是一个很火的领域，它被很多人神秘化，不过其底层的实现原理并不复杂。其中，哈希算法就是它的一个非常重要的理论基础。你能讲一讲区块链使用的是哪种哈希算法吗？是为了解决什么问题而使用的呢？
    区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体。区块头保存着 自己区块体 和 上一个区块头 的哈希值。因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。区块链使用的是 SHA256 哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。
  3. 有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢
    我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的：为了提高处理的速度，我们用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。