哈希算法历史悠久，比如最常用的哈希算法： MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和SHA （Secure Hash Algorithm，安全散列算法），还有DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。但是现在一般用SHA 等（因为 MD5 已经号称被破解了）。

概念

实际上，不管是“散列”还是“哈希”，这都是中文翻译的差别，英文其实就是“Hash”。所以，我们常听到有人把“散列表”叫作“哈希表”“Hash 表”，把“哈希算法”叫作“Hash 算法”或者“散列算法”。

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法。而通过原始数据映射之后得到的二进制值串就是哈希值。
一个优秀的哈希算法需要满足以下几点要求：

  • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
  • 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
  • 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也不同；
  • 哈希算法的执行效率要高效，针对较长的文本，也能快速地计算出哈希值。 ```bash // 无论要哈希的文本有多长、多短，最后得到的哈希值的长度都是相同的，像一堆随机数，完全没有规律。 MD5(“ 今天我来讲哈希算法 “) = bb4767201ad42c74e650c1b6c03d78fa MD5(“jiajia”) = cd611a31ea969b908932d44d126d195b

// 一字之差，哈希值也是完全不同的。 MD5(“ 我今天讲哈希算法！”) = 425f0d5a917188d2c3c3dc85b5e4f2cb MD5(“ 我今天讲哈希算法 “) = a1fb91ac128e6aa37fe42c663971ac3d ```

应用

安全加密

对用于加密的哈希算法有两点很重要：

  1. 很难根据哈希值反向推导出原始数据：目的就是防止原始数据泄露
  2. 散列冲突的概率要很小。

MD5 的哈希值是固定的 128 位二进制串，最多能表示 2128 个数据，如果对 2128+1 个数据求哈希值，就必然会存在哈希值相同的情况。但一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。MD5散列冲突的概率要小于 1/2128。
除此之外，没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。比如 SHA-256 比 SHA-1 要更复杂、更安全，相应的计算时间就会比较长。

唯一标识

在海量的图库中，可以给每一个图片取一个唯一标识，或者说信息摘要。比如，可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。

数据校验

BT 下载的原理是基于 P2P 协议的。从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分割成很多文件块（比如 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。
但是网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的，又或者下载过程中出现了错误，所以下载的文件块可能不是完整的。如果不能检测这种恶意修改或者文件下载出错，就会导致最终合并后的电影无法观看，甚至导致电脑中毒。那么如何来校验文件块的安全、正确、完整呢？
通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。哈希算法的一个特点是对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

散列函数

散列函数也是哈希算法的一种应用。散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。
散列函数对于散列算法要求：

  1. 对冲突的要求不高。即便出现个别散列冲突，只要不是过于严重，都可以通过开放寻址法或者链表法解决。
  2. 散列算法计算得到的值，不关注是否能反向解密。
  3. 更关注散列后的值是否能平均分布；以及散列函数执行的快慢，追求效率。

    负载均衡

    负载均衡算法有很多，比如轮询、随机、加权轮询等。
    实现一个会话粘滞（session sticky）的负载均衡算法：利用哈希算法替代映射表，通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。 这样，就可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。

    数据分片

    数据分片的思想：通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。

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

    假如有 1T 的日志文件，这里面记录了用户的搜索关键词，想要快速统计出每个关键词被搜索的次数，该怎么做呢？这个问题有两个难点，第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。
    针对这两个难点，先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路：用 n 台机器并行处理。从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。
    这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。
    实际上，这里的处理过程也是 MapReduce 的基本设计思想。

    快速判断图片是否在图库中

    假设图库中有 1 亿张图片，同样可以对数据进行分片，然后采用多机处理。 具体的思路：n 台机器，让每台机器只维护某一部分图片对应的散列表。每次从图库中读取一个图片，计算唯一标识，然后与机器个数 n 求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。
    当判断一个图片是否在图库中的时候，通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数 n 求余取模。假设得到的值是 k，那就去编号 k 的机器构建的散列表中查找。
    散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设通过 MD5 来计算哈希值，那长度就是 128 比特，也就是 16 字节。文件路径长度的上限是 256 字节，假设平均长度是 128 字节。如果用链表法来解决冲突，那还需要存储指针，指针只占用 8 字节。所以，散列表中每个数据单元就占用 大约152 字节。假设一台机器的内存大小为 2GB，散列表的装载因子为 0.75，那一台机器可以给大约 1000 万（2GB0.75/152）张图片构建散列表。所以，如果要对 1 亿张图片构建索引，需要大约十几台机器。
    *实际上，针对海量数据的处理问题，都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制。

    分布式存储

    概述：分布式存储应用中，利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。
    现在互联网面对的都是海量的数据、海量的用户。为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。可以借用数据分片的思想，但如果数据增多，需要扩容，就并不是简单地加个机器那么简单了。
    原来的数据是通过与 10 来取模的。比如 13 这个数据，存储在编号为 3 这台机器上。但是新加了一台机器中，对数据按照 11 取模，原来 13 这个数据就被分配到 2 号这台机器上了。因此，所有的数据都要重新计算哈希值，然后重新搬移到正确的机器上。这样就相当于，缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。
    所以需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移。这时候，一致性哈希算法就要登场了。
    假设有 k 个机器，数据的哈希值的范围是 [0, MAX]。将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。
    一致性哈希算法的基本思想就是这么简单。除此之外，它还会借助一个虚拟的环和虚拟结点，更加优美地实现出来。