15. 算法篇：哈希算法
哈希算法
哈希算法和原理：将任意二进制值串映射为固定长度的二进制值串，这个映射规则就是哈希算法。
哈希算法需要满足一下几点要求：
- 从哈希值不能反向推导出原始数据，也就是说，哈希算法是不可逆的。
- 对输入数据敏感，哪怕原始数据只修改一个 Bit，最后得到的哈希值也大不相同。
- 散列冲突的概率要小，对于不同的原始数据，哈希值相同的概率非常小。
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算出哈希值。
哈希算法的应用
安全加密
最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法），和 SHA（Secure Hash Algorithm，安全散列算法）。
此外还有许多其他加密算法，如 DES(Data Encryption Standard，数据加密标准)、AES(Advanced Encryption Standard，高级加密标准)。
哈希算法无法做到零冲突。MD5 的哈希值是固定的二进制串，能表示的数据是有限的，最多只能表示 2^128 个数据，而我们要表示的数据是无穷的，如果对 2^128 + 1 个数据求哈希值，必然会存在哈希值相同的情况。不过 2^128=340282366920938463463374607431768211456 ，这是一个天文数字了，冲突的概率会小于 1/2^128。
散列加密无法做到绝对的安全，如果用户信息被”脱库”，黑客想要破解密文，可以通过字典攻击的方式，也就是常说的“彩虹表”，通过维护一个常用密码的字典表，把每个密码用哈希值计算哈希值，然后跟密文比对，如果相同，基本上可以认为密文对应的明文就是字典表的这个密码。
针对字典攻击，可以对数据“加盐”(salt) 的方式，增加加密的复杂度，如果黑客不知道”盐值”，那么就无法通过字典表攻击拿到明文。
唯一标识
如何在海量的图库中搜索一张图是否存在？
图片文件其实可以转成一串二进制码，但是一张图片可能有十几M，转成二进制会非常长，因此通过一一比较二进制串的方式可能会非常耗时。
我们可以给每个图片取一个唯一标识，或者说信息摘要。比如从图片的二进制串开头取 100 个字节，中间取 100 个字节，从最后再取 100 个字节，最后将这 300 个字节放到一块，通过哈希算法，得到一个哈希字符串，用它作为图片的唯一标识。
为了提高查找效率，还可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。
数据校验
在网络上下载文件有可能带来电脑病毒，通常是由于网络传输不安全，下载的文件块被恶意修改过导致的。如下载电影的时候通常用到 BT 下载，BT 下载是基于 P2P 协议的，下载电影的时候，电影文件会被分割成很多文件块，等所有的文件块都下载完成之后，再组装成一个完整的电影文件。但如何校验文件块的安全、正确、完整呢？
可以通过哈希算法，对 每个文件块取哈希值，并且保存到种子文件中。当文件块下载完成后，我们可以通过相同的哈希算法，对下载好的文件块逐一求解哈希值，然后跟种子文件保存的哈希值比对，如果不同，说明这个文件块被篡改了，需要重新从其他宿主机器上下载这个文件块。
散列函数
散列函数是设计一个散列表的关键，它直接决定散列冲突的概率和散列表的性能。但是散列函数对散列冲突的要求会低很多，因为可以通过开放寻址法和链表法解决，而且散列函数对计算的值能否逆向也要求不高。
只要散列算法计算的值能较平均的分布，并且执行的效率较高，就符合一个散列函数的标准了。
负载均衡
负载均衡的算法有很多，轮询、加权、随机等。如果要实现一个会话粘滞(session sticky)的负载均衡算法，即同一个客户端，在一次会话中的所有请求都路由到同一台服务器上。
这时，可以通过哈希算法，对客户端的 IP 地址，或设备号计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是被路由的服务器编号。
这种是针对服务器数量不变的情况下，如果服务器扩容或缩容，那么所有的会话将失效。针对这种情况，可以使用一致性哈希算法。
数据分片
在分布式计算中，通常会先对数据进行分片，然后分布到 n 台机器中分别计算。数据分片可以使用范围分片，也可以使用哈希分片。
案例一：在 1 T 的日志文件中，统计用户的搜索关键词出现的次数。
使用 n 台机器并行处理，可以提高计算处理的速度。首先从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后对机器数量 n 取模，得到机器编号。
这样同一个搜索关键词都被分配到了同一台机器上，每个机器会分别计算关键词出现的次数，最后合并起来的数据就是最终结果。
这是处理过程也是 MapReduce 的基本思想。
案例二：在 1 亿张图片中快速判断图片是否存在图库中。
首先要给每个图片取唯一标识，然后构建散列表。但是 1 亿张图片在单台机器上是行不通的，远远超过了单台机器的内存上限。
这时候同样可以对数据进行分片，然后使用多机并行处理。我们准备 n 台机器，让每台机器只维护某一部分图片对应的散列表，具体分片思路：每次从图库中读取一张图片，计算唯一标识，然后与机器数据 n 取模，得到的值就是对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。当判断一个图片是否在图库中时，我们通过同样的哈希算法，计算这个图片的唯一标识，然后对 n 取模得到 k，那么就是编号 k 的机器构建的散列表中查找。
一亿张图片构建散列表需要多少台机器？
假设通过 MD5 来计算哈希值，长度为 128 bit，即 16 字节，文件路径长度上限为 256 字节，可以假设平均长度为 128 字节。如果用链表法来解决冲突，还需要指针，指针只占用 8 字节。所以一个散列表数据单元占用 152 字节。
假设一台机器内存大小为 2 Gb，散列表的装载因子为 0.75，那么一台机器可以给 大约 1000万(2GB*0.75/152)张图片构建散列表。对 1 亿张图片构建散列表，大概需要十几台机器。
分布式存储
对海量数据的分布式存储可以用数据分片的思想，对数据哈希运算，然后对机器数据 n 取模得到机器编号，来决定数据存储到哪台机器上。但是随着数据的增加，原来的机器已经无法承受，这时候需要对机器扩容，那么原来存储的数据的查找就比较麻烦了。比如存储的是分布式的缓存数据，增加一台机器之后，n 变成了 n+1，取模之后的机器编号就不是原来的编号了，那么所有的数据都会穿透缓存，直接去请求数据库，从而发生雪崩效应。
针对分布式存储的扩容/缩容情况，最常用到的就是一致性哈希算法了。
假设有 k 个机器，数据的哈希值范围是[0, MAX]，通常 MAX=232，并且将数值范围构成一个虚拟的哈希环，k 个机器构成虚拟的结点。我们将整个范围分成 m 个小区间(m 远大于 k)，每个机器负责 m/k 个小区间。当有新机器加入时，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，即不用全部重新哈希、搬移数据，也保持了各个机器上数据量的均衡。
关注微信公众账号「曹当家的」，订阅最新文章推送