哈希算法

May 16, 2022 1992

哈希算法

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

优秀的哈希算法需要满足的几点要求：

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

哈希算法的应用

  1. 应用一：安全加密

    最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）、 SHA（Secure Hash Algorithm，安全散列算法）、DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。

    没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长

  2. 应用二：唯一标识

  3. 应用三：数据校验

  4. 应用四：散列函数

    散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。

    散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。

  5. 应用五：负载均衡

    负载均衡算法有很多，比如轮询、随机、加权轮询等。

    如何实现一个会话粘滞（session sticky）的负载均衡算法？

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

    最直接的方法就是，维护一张映射关系表，这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找应该路由到的服务器编号，然后再请求编号对应的服务器。

    弊端：

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

    可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。

  6. 应用六：数据分片

    1. 如何统计“搜索关键词”出现的次数？

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

      可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。

      具体思路：为了提高处理的速度，我们用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。

      哈希值相同的搜索关键词就被分配到了同一个机器上,每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

    2. 如何快速判断图片是否在有1 亿张图片的图库中？

      可以对数据进行分片，然后采用多机处理。

      具体思路：准备 n 台机器，让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数 n 求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

      当要判断一个图片是否在图库中的时候，通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数 n 求余取模。假设得到的值是 k，那就去编号 k 的机器构建的散列表中查找。

  7. 应用七：分布式存储

    现在互联网面对的都是海量的数据、海量的用户。为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。

    该如何决定将哪个数据放到哪个机器上呢？可以借用数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。

    如果数据增多，原来的 10 个机器已经无法承受了，就需要扩容，比如扩到 11 个机器，但这里并不是简单地加个机器就可以了。

    所有的数据都要重新计算哈希值，然后重新搬移到正确的机器上。这样就相当于，缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。

    一致性哈希算法：假设有 k 个机器，数据的哈希值的范围是[0, MAX]。将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡

查看评论