数据结构之哈希算法

此文是数据结构和算法之美学习笔记

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

一般哈希算法的要求：

• 不能通过哈希值反向推导出原始数据（哈希算法也叫单向哈希算法）
• 对输入的数据非常敏感，哪怕原始数据只是修改了一个bit，最后得到的哈希值也大不形同
• 对不同的原始数据，哈希值相同的概率要非常小，散列冲突的概率要很小。
• 哈希算法的执行效率要尽量的高效，即使较长的文本也能很快的计算出哈希值

哈希算法的应用非常多最常见的有安全加密，唯一标识，数据校验，散列函数，负载均衡，数据分片，分布式存储。

安全加密

常用于加密的哈希算法是

MD5（Message-Digest-Algorihm 消息摘要算法）

SHA(Secure Hash Algorihm 安全散列算法)

DES(Data Encryption Standard 数据加密标准)

AES(Advanced Encryption Standard 高级加密标准)

为什么哈希算法无法做到零冲突？

有一个数学理论：鸽巢原理（也叫抽屉原理）就是说如果有10个鸽巢，有11个格子，那么肯定有一个鸽巢中有两个鸽子。

哈希算法产生的哈希值的长度也是有限的，比如MD5的哈希值固定是128位的二进制串，最多能表示2

128个数据。而我们需要表示的哈希数是无穷的，当数据大于2

不过由于2

128这个数组已经很大了，出现散列冲突的概率要小于1/2

没有绝对的安全加密，越复杂越难破解的加密算法，需要的计算时间也越长，就想SHA-256比SHA-1要更加复杂也就更安全，相应的计算时间就会更长。

唯一标识

比如在海量的图库中怎么搜索一张图片是否存在？

（1）使用图片名字肯定不行，因为可能有的图片名字不一样但是都是一样的图片

（2）对比图片的二进制码，这种办法可行，但是比较笨，因为图片很多都很大几MB都是常事，转化成二进制后会很大，对比起来也非常耗时

（3）可以给每一张图片取一个唯一标识，比如可以从二进制码的开头取100字节，中间取100字节，结尾再取100字节，把这300字节放到一块通过哈希算法比如MD5得到一个哈希字符串，用这个作为图片的唯一标识来判断库中是否有该图片

当我们向库中插入一个图片的时候，先去散列表中查找唯一标识，如果不存在就说明这个图片不在图库中，如果存在就拿出这个图片和将要插入的图片做全量对比，看是否完全一样。如果一样说明已经存在，如果不一样说明两张图片虽然唯一标识一样但不是相同的图片。

数据校验

比如BT下载，一个电影可能会被分割成很多块（比如100块）分别下载，等所有文件都下载完成之后在组装成一个完整的电影文件。

由于网络传输是不安全的，下载的文件快可能会被宿主几区恶意修改或者下载过程出现了错误导致下载的文件是不完整的。如果下载完不能检测是否出错，就会导致最后合并完的电影无法观看甚至中毒。

一种校验的思路就是，把这100个快分别取哈希值并且保存在种子文件中，由于哈希算法对原始数据非常敏感，只要文件中有一点点改变最后的哈希值就完全不同，当文件块下载完成后，我们可以通过同样的哈希算法对下载好的文件快一一求哈希值跟种子文件中的哈希值对比。如果不一样说明文件快不完整或者被篡改了，需要重新下载。

散列函数

散列表中的散列函数也需要哈希算法，不过相对于其他的应用，它对哈希算法的要求不高，即使出现散列冲突，也可以通过开放寻址法和链表法来解决

散列函数对哈希算法的要求主要散列后的值能否平均分布，散列函数是否执行很快。

如何防止数据库中信息被脱库

可以通过哈希算法，对用户密码进行加密之后在存储不过最好选择相对安全的加密算法比如SHA(MD5据说被破解了)

不过如果用户的密码设置的很简单比如000000，,13456等简单的数组，黑客可以通过字典攻击很容易的猜中

针对字典攻击可以引入一个盐（salt）跟用户的密码组合在一起增加其复杂度然后在通过哈希算法加密。比如原始密码是123456，可以在其头部或者尾部加上个字符串bxt变成bxt123456或者123456bxt也可以在中间加。

区块链现很火，其实其底层也是通过哈希算法

区块链是一块块的区块组成，每个区块分成区块头和区块体，区块头保存着自己区块体和上一个区块头的哈希值。

因为这种链式关系和哈希值的唯一性，只要区块链上的任意一个区块被修改过，后面的所有的区块保存的哈希值就不对了。

区块链使用的是SHA256这种哈希算法，计算哈希值是很耗时的，如果要篡改一个区块，就必须重新计算该区块后面的所有的区块的哈希值，短时间内几乎做不到。

负载均衡

负载均衡算法有很多，比如轮训，随机，加权轮询等等。怎么才能实现一个会话粘滞（同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上）的负载均衡呢

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

不过当客户端很多的时候，映射表会很大，浪费空间。客户端的上线下线服务器的扩容都会导致映射失效，维护成本很大。

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

数据分片

1、如何统计某个关键词出现的次数

如果我们有1T的数据，里面记录了用户搜索的关键词，怎么快速的统计出每个关键词被搜索的次数。

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

为了提高处理速度，我们使用n台机器并行处理，从搜索日志中一次读取出每个搜索关键词，通过哈希函数计算哈希值，然后n取模，得到的值就是应该分配到的机器编号

这样哈希值相同的关键字就会被分配到同一台机器上，每个机器分别计算出关键词的次数，最后合并起来就是最后结果。

2、如何快速判断图片是否存在图库中

假如又一亿张图片，一台机器是无法装下的，这时候就可以给数据分片，然后多机处理。准备n台机器，每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数,取模，得到的值就是对应分配的机器标号，然后将这个图片唯一标识和图片路径发往对应的机器构建散列表。

查找的时候，通过同样的哈希算法计算图片的唯一标识，然后机器个数n取模，得到的值就是对应机器的编号，然后去该机器中寻找。

分布式存储

如今的互联网的数据都是海量的，只能分布式的存储在不同的机器上，怎么决定放在哪个机器上呢，跟数据分片一样，通过哈希算法对数据取哈希值，然后对机器取模，值就是对应机器的编号。

问题：当数据增多，原来的机器无法存储的时候，就需要加机器了。但是这个时候不仅仅是加机器这么简单。

因为比如原来有10台机器，原来的值是通过10来取模的，当加了一台机器之后，就是按11取模了，最后分配到的机器是不一样的。因此所有的数据都要从新计算哈希值，然后从新搬移到正确的机器上，相当于缓存中的数据全部失效，假如以前是直接请求缓存，现在就是直接去请求数据库，数据库就会被压垮、

怎么解决这个问题呢，可以使用 一致性哈希算法

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

注意取模的时候不是根据机台的个数k而是跟m取。当然取到的数也许不是机台的编号，这时候就按照顺时针来寻找，把数据放到第一个找到的机器上。

当然这样做也有可能某台机器上存储的东西太多，不够均匀，怎么办呢，可以引入虚拟结点的概念，每台机器分成m/k份，这样相当于这m个结点上都有一台小机器了，取模之后就可以直接放到这些小机器上了。这样就解决了不均匀的问题了。