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

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的日志文件,里面记录了用户的关键词,我们想快速统计出来每个关键词被搜索的次数,该怎么做呢?

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

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

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

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

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

2.7 分布式存储

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

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

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


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

文章标题:数据结构与算法(15)-哈希算法

文章字数:1.2k

本文作者:Leilei Chen

发布时间:2020-02-09, 10:30:23

最后更新:2020-02-09, 10:30:43

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-15-%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏