数据结构与算法之美——哈希算法分析

java哥 阅读:188 2021-06-15 11:20:33 评论:0

一、前言

       如何防止数据库中的用户信息被脱库?如何存储用户密码这么重要的数据呢?仅仅MD5加密一下存储就够了吗?要想搞清楚这个问题,就要先弄明白哈希算法。

       哈希算法历史悠久,业界著名的哈希算法也有很多,比如MD5、SHA等。那么在实际的开发中,我们该如何用哈希算法解决问题

二、什么是哈希算法

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

        设计哈希算法的要求:

        1、从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法

        2、对输入的数据非常敏感,哪怕原始数据只修改1个Bit,最后得到的哈希值也不大相同

        3、散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小

        4、哈希算法的执行效率要尽量高效,针对较长的文本,也能快速计算出哈希值

三、哈希算法的应用

        哈希算法的应用非常多,最常见的7个,分别是安全加密、唯一标志、数据校验、散列函数、负载均衡、数据分片、分布式存储。

        1、安全加密

        说到哈希算法的应用,最先想到的应该就是安全加密。最常见用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm,MD5消息摘要算法)和SHA(Secure Hash Algorithm,安全散列算法)

        除了这两个,还有很多其他加密算法,比如DES(Data Encryption Standard,数据加密标准)、AES(Advanced Encryption Standard,高级加密标准)

        对于加密哈希算法来说,有两点格外重要。第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要很小。第一点很好理解,加密的目的就是防止原始数据泄露,所以很难通过哈希值反向推导出原始数据,这是一个基本的要求。重点说一下第二点。不管什么哈希算法,我们只能尽量减少碰撞冲突的概率

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

       哈希算法产生的哈希值的长度时固定且有限的。比如前面举的MD5的例子,哈希值是固定的128位二进制串,能表示的数据是有限的,最多能表示2^128个数据,而我们要哈希的数据是无穷的。如果我们对2^128+1个数据求哈希值,就必然会存在哈希值相同的情况。一般情况下,哈希值越长的哈希算法,散列冲突的概率越低。

       2、唯一标识

       举个栗子,要在海量的图库中,搜索一张图是否存在,不能单纯地用图片的元信息(比如图片名称)来比对,因为有可能存在名称相同但图片内容不同,或者名称不同但是图片内容相同的情况。

       我们可以通过哈希算法(比如MD5),得到一个哈希字符串,用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中,这样就可以减少很多工作量。

       3、数据校验

        电驴这样的BT下载软件肯定用过吧,BT下载的原理是基于P2P协议的。我们从多个机器上并行下载一个2GB的电影,这个电影文件可能会被分割成很多文件块(比如可以分成100块,每块大约20MB)等所有的文件块都下载完成之后,再组装成一个完整的电影文件就行了。

        我们通过哈希算法,对100个文件分别取哈希值,并且保存在种子文件中。哈希算法有一个特点,对数据很敏感。只要文件块有一点改变,最后计算出的哈希值就会完全不同。所以,当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一比对。

        4、散列函数

       散列函数也是哈希算法的一种应用。散列函数对于散列算法冲突的要求不高。即使出现个别散列冲突,只要不是过于严重,都可以通过开放寻址法或者链表法解决。

       散列函数对于散列算法计算得到的值,是否能反向解密也并不关心。散列函数中用到的散列算法,更加关注散列后的值是否能平均分布,也就是,一组数据是否能均匀地散列在各个槽中。

      接下来,我们再来看剩余三种应用:负载均衡、数据分片、分布式存储。这三个应用都跟分布式系统有关。

      5、负载均衡

       负载均衡算法有很多,比如轮训、随机、加权轮训等。那如何才能实现一个会话粘滞(session sticky)的负载均衡算法呢?也就是说,我们需要在同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上。

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

      6、数据分片

      ①如何统计“搜索关键词”出现的次数

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

      7、分布式存储

      一致性哈希算法

四、总结

       在负载均衡应用中,利用哈希算法替代映射表,可以实现一个会话粘滞的负载均衡策略。在数据分片应用中,通过哈希算法对处理的海量数据进行分片,多机分布式处理,可以突破单机资源的限制。在分布式存储应用中,利用一致性哈希算法,可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号