哈希算法

哈希算法的应用：唯一标识，任意可二进制数据做信息摘要；校验数据的完整性和准确；安全加密；散列函数。

在负载均衡中，用哈希算法替代映射表以实现负载均衡策略；在数据分片中，用哈希算法对海量数据进行分片，多机分布式处理；在分布式存储应用中，用一致性哈希算法解决缓存等分布式系统中的扩容、缩容等导致大数据搬移问题。

什么是hash算法：

将任意长度的二进制值串按规则映射为固定长度的二进制值串，哈希算法就是这儿映射规则，生成的这个固定长度的二进制值串叫做hash值。

设计哈希算法需要满足要求：

• 单向的，不能从哈希值推出原始数据；
• 输入数据敏感，修改了一个bit后哈希值将大不同；
• 发生散列冲突的概率小，：鸽笼原理
• 算法高效；

// MD5哈希算法生成128bit长度
MD5("我今天讲哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb
MD5("我今天讲哈希算法") = a1fb91ac128e6aa37fe42c663971ac3d

应用

安全加密

常见的加密哈希算法：MD5：MD5 message-digest algorithm、SHA：secure hash algorithm、DES：data encryption standard、AEA：advanced encryption standard。

1. 难用hash值反推原始数据==》

2. 散列冲突概率小：哈希值的长度是固定有限的：如MD5哈希值的长度为128bit，有2^128 个不同的哈希值，虽然这个值足够大，但仍有冲突的可能性。

3. SHA-256看256可以了解其哈希值更长，更复杂安全。

4. 所以，选择时需要权衡破解难度、计算效率等

唯一标识

也称为信息摘要，可以想象在BT中下载文件是，会提供若干哈希加密算法生成的值，以供校验，这个值就是官方对官方文件做的唯一标识，如果有人修改了，该唯一标识值就会发生变化。

以比对图片为例，

1. 给每一张图片取唯一的标识：将图片的二进制码串取开头、中间、最后各100个字节=》通过哈希算法（MD5)生成哈希值字符串；
2. 将图片的唯一标识+文件路径，存在散列表中，
3. 判定时，提要对比的图片唯一标识，在散列表中找到的话，再做全量图片对比。

数据校验

对下载的BT文件（2GB电影），100个文件块分别取哈希值，对比服务端和客户端的值。

散列函数

散列函数的要求简单些，对冲突的处理要求不高，对hash值反向解密也不关心。

散列函数更需要关注散列值能否平均分布，均匀地散列在槽中。

追求简单高效。

针对字典攻击做法：

盐salt+用户密码，再做哈希加密算法以增加密码复杂度，我觉得也可以减少撞库风险。

针对时序攻击：

将计算hash的时间固定，或采用慢算法：PBKDF2WithHmac SHA1

Hash algorithm在分布式系统中的应用

负载均衡

有轮询、随机、加权轮询、会话黏滞session sticky等方法

会话黏滞：将同一客户端上的一次会话的所有请求路由到同一服务器。可以想象腾讯视频会议这样的服务可以将一场会议的所有人的链接路由到同一服务器上，或者一场和平精英游戏也是这样。

方法1：将用户的IP、会话ID、服务器编号组成一张关系表。

• 若客户端很多这个映射表将很大，客户上下线，以及服务器扩容缩容，均需维护映射表。

方法2：由客户端IP地址或会话ID计算哈希值，将取得的哈希值与服务器列表的大小做取模，得到的值为服务器编号。

数据分片

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

快速统计1t日志文件中的xx，使用n台机器做并行处理。

从搜索记录的日志文件中依次读出每个关键词，由哈希函数计算哈希值，该值与n取模，得到的值为机器编号。

这样相同搜索关键词（哈希值）被分到同一台机器上,每个机器计算该词出现次数。

2.判断图片是否在图库中

类似的，对1亿张图片，每次读取1张，计算唯一标识，与机器个数n取模，得到分配的机器号。将唯一标识与图片路径发到分配的机器上，这些信息构成散列表。

当检索一张图片是否在图库中时，做类似计算、查找即可。

估计需要的机器数量：存储图片信息的散列表 ：

hash值	图片路径	链表指针
128bit=16字节	最大256字节,平均128字节	8字节

假设一台机器内存2GB，装载因子0.75，大概该机器可存储1千万图片，1亿张图片需要十几台机器。

分布式存储

如何决定数据分布在多台机器上呢？？

若使用数据分片，在扩容后取模会变。==》扩容后编号会乱，全部需要重新计算。

为此，在新加入机器后不能做大量数据搬移，即要采用一致性哈希算法：

对K个机器，数据的hash范围为[0, MAX]；划分为m个小区间，每个机器负责m/k个小区间。

当新机器加入时，将部分小区间交给新机器（数据从原来机器中搬移到新机器中），这样不用全部重新哈希或搬移数据。

扩展：虚拟的环、结点：一致性哈希算法 consistent hashing