数据结构与算法(15)-哈希算法

数据结构与算法哈希算法

创建时间:2020-02-10 02:30

字数:1.2k 阅读:

评论:

1. 什么是哈希算法
2. 哈希算法的应用

1. 什么是哈希算法

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

哈希算法的要求
- 从哈希值无法反向推导出原始数据
- 对输入数据非常敏感，哪怕原始数据只修改一个bit，最后得到的哈希值也会大不相同
- 散列冲突的概率很小，对于不同的原始数据，哈希值相同的概率非常小
- 哈希算法的效率要足够高，针对较长文本，也能快速计算出哈希值

2. 哈希算法的应用

2.1 安全加密

常用de加密算法
- MD5
  - MD5 Message-Digest Algorithm
  - MD5信息摘要算法
- SHA
  - Secure Hash Algorithm 安全散列算法
- DES
  - Data Encryption Standard 数据加密标准
- AES
  - Advanced Encryption Standard 高级加密标准

2.2 唯一标识

图片的标识，从图片的二进制串码的前中后各取出100字节，通过哈希算法得到一个哈希字符串，用它作为图片的唯一标识。然后通过这个唯一标识来判定图片是否在图库当中，通过这种方式来减少工作量。

2.3 数据校验

BT协议的数据校验，对每个文件块取哈希值，保存在种子文件当中。当文件块下载完成之后，我们通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值进行比对。如果不同，就说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

2.4 散列函数

哈希表的散列函数，关注的是在做完哈希以后，是否能够平均的分布。一组数据能否均匀散列在各个槽中。

另外一个点是其执行速度，散列函数对执行速度的要求会比较高一些。

2.5 负载均衡

分布式系统当中需要解决的问题

负载均衡的算法
- 轮询
- 随机
- 加权轮询

但是我们需要实现一个会话粘滞的负载均衡算法(session sticky)。即我们需要在一个客户端上，在一次会话上的所有请求都路由到同一个服务器上。

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

2.6 数据分片

2.6.1 如何统计关键词搜索的次数

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

数据量太大的问题
处理时间太长的问题

对数据进行分片，然后多台机器进行处理。用哈希算法，将哈希值相同的搜索关键词放到同一台机器上。然后最后做汇总

2.6.2 如何快速判断图片是否在图库当中

为每个图片取唯一标识，然后构建散列表，但是当图片量很大的时候，在单台机器上构建散列表是行不通的。

因为在存储的时候，我们还是需要根据哈希算法取模来进行存储，然后在进行判断的时候，也是用同样的哈希算法，然后与机器个数n求余取模。然后根据得到的值到对应的机器上去进行查找。

2.7 分布式存储

分布式存储需要解决的问题是，当我们已经在各个host上按照哈希算法保存了数据以后，再增减host的时候，我们不希望还需要对原先的host里面的数据做迁移。如果说缓存当中的数据会一下子全都失效的话，那么所有数据请求都要从数据库走，直接就压垮数据库了。

因此在分布式存储当中，我们需要采用一致性哈希算法

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

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com