精华内容
下载资源
问答
  • 哈希算法的定义和原理非常简单,基本上一句话就可以概括:将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 但是,要想设计一...

    什么是哈希算法?

    哈希算法的定义和原理非常简单,基本上一句话就可以概括:将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。

    但是,要想设计一个优秀的哈希算法并不容易,根据我的经验,我总结了需要满足的几点要求:

    • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法);
    • 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同;
    • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
    • 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。

    应用一:安全加密

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

    前面讲到的哈希算法四点要求,对用于加密的哈希算法来说,有两点格外重要:

    • 第一点是很难根据哈希值反向推导出原始数据
    • 第二点是散列冲突的概率要很小

    第一点很好理解,加密的目的就是防止原始数据泄露,所以很难通过哈希值反向推导原始数据,这是一个最基本的要求。

    第二点,实际上,不管是什么哈希算法,只能尽量减少碰撞冲突的概率,理论上是没办法做到完全不冲突的。为什么这么说呢?

    这里就基于组合数学中一个非常基础的理论,鸽巢原理(也叫抽屉原理)。这个原理本身很简单,它是说,如果有 10 个鸽巢,有 11 只鸽子,那肯定有 1 个鸽巢中的鸽子数量多于 1 个,换句话说就是,肯定有 2 只鸽子在 1 个鸽巢内。

    有了鸽巢原理的铺垫之后,我们再来看,为什么哈希算法无法做到零冲突?

    我们知道,哈希算法产生的哈希值的长度是固定且有限的。比如前面举的 MD5 的例子,哈希值是固定的 128 位二进制串,能表示的数据是有限的,最多能表示 21282^{128}个数据,而我们要哈希的数据是无穷的。基于鸽巢原理,如果我们对 2^128+1 个数据求哈希值,就必然会存在哈希值相同的情况。这里你应该能想到,一般情况下,哈希值越长的哈希算法,散列冲突的概率越低。

    2^128=340282366920938463463374607431768211456
    

    不过,即便哈希算法存在散列冲突的情况,但是因为哈希值的范围很大,冲突的概率极低,所以相对来说还是很难破解的。像 MD5,有 21282^{128}个不同的哈希值,这已经是一个天文数字了,所以散列冲突的概率要小于1/2128{1/2}^{128}

    除此之外,没有绝对安全的加密。越复杂、越难破解的加密算法,需要的计算时间也越长。比如 SHA-256 比 SHA-1 要更复杂、更安全,相应的计算时间就会比较长。密码学界也一直致力于找到一种快速并且很难被破解的哈希算法。我们在实际的开发过程中,也需要权衡破解难度和计算时间,来决定究竟使用哪种加密算法。

    应用二:唯一标识

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

    我们知道,任何文件在计算中都可以表示成二进制码串,所以,比较笨的办法就是,拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同,则说明图片在图库中存在。但是,每个图片小则几十 KB、大则几 MB,转化成二进制是一个非常长的串,比对起来非常耗时。有没有比较快的方法呢?

    我们可以给每一个图片取一个唯一标识,或者说信息摘要。比如,我们从图片的二进制码串开头取 100 个字节,从中间取 100 个字节,从最后再取 100 个字节,然后将这 300 个字节放到一块,通过哈希算法(比如 MD5),得到一个哈希字符串,用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中,这样就可以减少很多工作量。

    如果还想继续提高效率,可以把每个图片的唯一标识,和相应的图片文件在图库中的路径信息,都存储在散列表中。当要查看某个图片是不是在图库中的时候,先通过哈希算法对这个图片取唯一标识,然后在散列表中查找是否存在这个唯一标识。

    如果不存在,那就说明这个图片不在图库中;如果存在,我们再通过散列表中存储的文件路径,获取到这个已经存在的图片,跟现在要插入的图片做全量的比对,看是否完全一样。如果一样,就说明已经存在;如果不一样,说明两张图片尽管唯一标识相同,但是并不是相同的图片。

    应用三:数据校验

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

    我们知道,网络传输是不安全的,下载的文件块有可能是被宿主机器恶意修改过的,又或者下载过程中出现了错误,所以下载的文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错,就会导致最终合并后的电影无法观看,甚至导致电脑中毒。现在的问题是,如何来校验文件块的安全、正确、完整呢?

    具体的 BT 协议很复杂,校验方法也有很多,我来说其中的一种思路。

    我们通过哈希算法,对 100 个文件块分别取哈希值,并且保存在种子文件中。我们在前面讲过,哈希算法有一个特点,对数据很敏感。只要文件块的内容有一丁点儿的改变,最后计算出的哈希值就会完全不同。所以,当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。如果不同,说明这个文件块不完整或者被篡改了,需要再重新从其他宿主机器上下载这个文件块。

    应用四:散列函数

    实际上,散列函数也是哈希算法的一种应用。

    我们前两节讲到,散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过,相对哈希算法的其他应用,散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突,只要不是过于严重,我们都可以通过开放寻址法或者链表法解决。

    不仅如此,散列函数对于散列算法计算得到的值,是否能反向解密也并不关心。散列函数中用到的散列算法,更加关注散列后的值是否能平均分布,也就是,一组数据是否能均匀地散列在各个槽中。除此之外,散列函数执行的快慢,也会影响散列表的性能,所以,散列函数用的散列算法一般都比较简单,比较追求效率。

    解答开篇

    课后思考

    现在,区块链是一个很火的领域,它被很多人神秘化,不过其底层的实现原理并不复杂。其中,哈希算法就是它的一个非常重要的理论基础。你能讲一讲区块链使用的是哪种哈希算法吗?是为了解决什么问题而使用的呢?

    区块链是一块块区块组成的,每个区块分为两部分:区块头和区块体。

    区块头保存着 自己区块体 和 上一个区块头 的哈希值。

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

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

    展开全文
  • 算法与数据结构之美—哈希算法哈希算法应用安全加密唯一标识数据校验散列函数负载均衡数据分片1、如何统计“搜素关键词”的出现次数2、如何快速判断图片是否再图库中分布式存储一致性哈希算法 哈希算法 哈希算法地...

    哈希算法

    哈希算法地原理就是将任意长度地二进制值串映射为固定长度地二进制值串,映射规则就是哈希算法;

    哈希算法需要满足地要求:

    • 从哈希值不能反向推导出原始数据;
    • 对于输入数据敏感,哪怕只改变了一个bit,最后得到的哈希值也不大相同;
    • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
    • 哈希算法的执行效率要高效,针对于长文本,也能进行快速哈希计算;

    应用

    安全加密

    常用于加密的哈希算法是MD5(MD5:Message-Digest Algorithm,消息摘要算法)和SHA(Secure Hash Algorithm,安全散列算法),除此之外还有很多其它加密算法,比如DESData Encryption Standard,数据加密标准)、AESAdvanced Encryption Standard,高级加密标准;

    对于安全加密来说,很难根据哈希值反向推导出原始数据和散列冲突的概率要很小,这两点特性很重要;

    像MD5,有2^128个不同的哈希值,所以散列冲突的概率是很小的;

    唯一标识

    在海量的图片中,搜索一张图片是否存在,不可能仅仅只靠图片的名称等信息来比对;那就可以通过哈希算法给每张图片

    取一个唯一标识,例如:对于一张图片,可以从图片的二进制码串分别在开头 中间 结尾各取100个字节,将300个字节放在一起,采用哈希算法生成一个哈希字符串,用来作为图片的唯一标识;

    可以把图片的唯一标识和相应的图像文件在图库中的路径信息,都存储在散列表中,极大的提高了查找的效率。

    数据校验

    BT下载的原理是基于P2P的,从很多机器上并行下载一个几个G的大文件,这个文件会被划分为许多文件块,下载完之后在组成一个完整的文件即可。

    但是网络传输不安全也不稳定,如何确定自己下载的文件块是否经过恶意修改的呢?

    可以采用哈希算法进行数据校验,对划分为许多块的文件分别取哈希值,哈希值对数据很敏感,只要文件块的内容篡改一点,得到的哈希值就会完全不同;在对于下载好的文件计算哈希值,在与种子文件中保存的哈希值进行比对,如果不同则说明数据已被篡改,需要重新下载。

    散列函数

    散列函数是设计一个散列表的关键,直接决定了散列冲突的概率和散列表的性能
    ,散列函数的设计追求简单高效;

    负载均衡

    我们如何在对于同一个客户端,在一次会话中的所有请求都路由到同一个服务器中;
    最简单的方法就是维护一张映射表,保存客户端IP地址与服务器编号之间的映射关系;

    弊端:

    • 客户端很多,映射表很大,占内存;
    • 客户端的上线、下线、服务器扩容、缩容都会导致映射的失效,维护映射表的成本就会变大;

    借助哈希算法,对于客户端IP地址或者会话ID计算哈希值,将取出的哈希值与服务器列表大小进行取模运算,最终得到的值就是被路由到的服务器编号;这样就可以把同一个IP过来的所有请求,都路由到同一个后端服务器上;

    数据分片

    1、如何统计“搜素关键词”的出现次数

    日志文件中包含许多搜索关键词,没法放到一台机器的内存中。同时,一台计算机处理时间会很长;

    为此可以先进行数据分片,然后采用多台机器处理,提高处理速度;思路:
    采用n台机器并行处理,从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数来计算哈希值,然后再跟n取模,得到的值就是应该被分配到的机器编号;

    那么哈希值相同的搜索关键词就会被分配到同一台机器上,每个机器会分别计算出关键词出现的次数,然后合并起来就是最终得到的结果。

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

    对于海量的图库,同样可以先对数据进行分片,采用多机处理。准备n台机器,让每台机器只维护某一部分图片对应的散列表。我们从图库中读取一个图片,计算出唯一标识,然后与机器个数n求余取模,得到的值就是机器编号,将这个图片的唯一标识和图片路径发往对应的机器构建散列表;

    当判断一张图片是否再图库中时,采用同样的哈希算法,计算出唯一标识,在与机器个数n取模,假设得到的值为k,那就去编号为k的机器构建的散列表中查找;

    分布式存储

    面对海量的数据,为了提升对于数据的读写能力,一般都采用分布式的方式来存储数据,分布式缓存;

    那么如何决定将哪个数据放到哪台机器上?
    我们可以借助前面数据分片的方式,通过哈希算法对数据取哈希值,然后在对机器个数取模,最终得到应该缓存的机器编号;

    随着数据量的增大,原来的10台机器已经无法承受了,就需要进行扩容,但不仅仅是简单增加机器就可以的,原先是与10取模计算编号,现在是与11取模进行编号计算;

    如果所有的数据都要重新计算哈希值,然后再重新将数据搬移到正确的机器中;这个时候数据库中的所有数据一下子都失效了,就会穿透缓存,直接去请求数据库,就会发生雪崩效应,压垮数据库;

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

    一致性哈希算法

    三言两语说不完,回头我在补充!

    展开全文
  • 数据结构哈希算法

    千次阅读 2019-01-22 13:53:11
    此文是数据结构和算法之美学习笔记 哈希算法就是将任意长度的二进制值映射为固定长度的二进制串,这个映射的规则就是哈希算法,原始数据映射之后得到的二进制哈希值。 一般哈希算法的要求: 不能通过哈希值反向推导...

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

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

    一般哈希算法的要求:

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

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

    安全加密

    常用于加密的哈希算法是
    MD5(Message-Digest-Algorihm 消息摘要算法)
    SHA(Secure Hash Algorihm 安全散列算法)
    DES(Data Encryption Standard 数据加密标准)
    AES(Advanced Encryption Standard 高级加密标准)

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

    有一个数学理论:鸽巢原理(也叫抽屉原理)就是说如果有10个鸽巢,有11个格子,那么肯定有一个鸽巢中有两个鸽子。

    哈希算法产生的哈希值的长度也是有限的,比如MD5的哈希值固定是128位的二进制串,最多能表示2128个数据。而我们需要表示的哈希数是无穷的,当数据大于2128的时候,就必然会出现哈希值相同的情况。

    不过由于2128这个数组已经很大了,出现散列冲突的概率要小于1/2128,相对来说很难破解。

    没有绝对的安全加密,越复杂越难破解的加密算法,需要的计算时间也越长,就想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个结点上都有一台小机器了,取模之后就可以直接放到这些小机器上了。这样就解决了不均匀的问题了。

    展开全文
  • 1.从哈希值不能反向推导出原始数据(因此哈希算法也叫单向哈希算法)。 2.对输入数据非常敏感,哪怕原始数据只修改了一个Bit,最后得到的哈希值也大不相同。 3.散列冲突的概率要很小,对于不同的原始数据,哈希值...

    最近开始学习王争老师的《数据结构与算法之美》,通过总结再加上自己的思考的形式记录这门课程,文章主要作为学习历程的记录。

    哈希算法的定义是将任意长度的二进制值串映射为固定长度的二进制值串。这个映射规则就是哈希算法。通过原始数据映射后得到的二进制值串就是哈希值。设计一个优秀的哈希算法应满足几点要求:

    1.从哈希值不能反向推导出原始数据(因此哈希算法也叫单向哈希算法)。

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

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

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

    举个例子,

    MD5(“今天我来讲哈希算法”) = bb4767201ad42c74e650c1b6c03d78fa

    MD5(“jiajia”) = cd611a31ea969b908932d44d126d195b

    可以看出,无论哈希的文本有多长,多短,通过MD5哈希之后,得到的哈希值长度是相同的,而且得到的哈希值看起来像是一堆随机数,毫无规律,也很难根据哈希值反推回对应的文本。

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

    应用一:安全加密

    最常用于加密的哈希算法是MD5(MD5消息摘要算法)和SHA(安全散列算法)。除此之外,还有其他加密算法,比如DES(数据加密算法)、AES(高级加密算法)。

    对于加密的哈希算法,有两点格外重要。第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要很小。第一点容易理解,为了防止原始数据泄露。第二点需要对为什么哈希算法无法做到零冲突进行解释一下:哈希算法产生的哈希值的长度是固定且有限的。以MD5为例,哈希值是固定的128位二进制串,能表示的数据是有限的,最多表示2128个数据,而我们要哈希的数据是无穷的。如果对2128+1个数据求哈希值,就必然存在哈希值相同的情况。一般情况下,哈希值越长的哈希算法,散列冲突的概率越低。

    没有绝对安全的加密。越复杂、越难破解的加密算法,需要的计算时间也越长。在实际开发过程中,也需权衡破解难度和计算时间,来决定究竟使用哪种加密算法。

    应用二:唯一标识

    以图片为例,如果要在图库中搜索一张图是否存在,不能单纯地用图片的元信息来比对。比较笨的办法就是拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对,但这种比对非常耗时。我们可以给每一个图片取一个唯一标识,或者说信息摘要。比如,我们可以从图片的二进制码串开头取100个字节,从中间取100个字节,从最后再取100个字节。然后将这300个字节放在一起,通过哈希算法(如MD5),得到一个哈希字符串,用它作为图片的唯一标识,这样可以减少很多工作量。

    应用三:数据校验

    以电驴BT下载软件为例,其下载原理是基于P2P协议。从很多机器并行下载一个2GB的电影,这个电影文件可能会被分割成很多文件块。等所有的文件块都下载完成后,再组装成一个完整的电影文件就行了。

    但是网络传输是不安全的,下载过程中可能出现错误,因此需要校验文件块的安全,正确以及完整。具体的BT协议很复杂,校验方法也很多。就说一下其中的一种思路:通过哈希算法,对100个文件块分别取哈希值,并且保存在种子文件中。哈希算法对数据很敏感,只要文件块内容有一些变化,最后计算出的哈希值完全不同。所以,当文件块下载完成后,可以通过相同的哈希算法,对下载好的文件块逐一求哈希值。然后再跟种子文件中保存的哈希值比对。如果不同,则说明文件块在下载过程中出现错误。

    应用四:散列函数

    散列函数也是哈希算法的一种应用。散列函数是设计一个散列表的关键,直接决定了散列冲突的概率和散列表的性能。但相比于哈希表其他应用,散列函数对于散列算法冲突的要求要低很多。即使出现了个别散列冲突,只要不是过于严重,都可以通过开放寻址法或链表法。

    散列函数对于能否反向解密并不关心。它更关注散列后的值能否平均分布。此外,散列函数执行的快慢,也会影响散列表的性能。故散列函数用的散列算法一般都比较简单,比较追求效率。

    应用五:负载均衡

    如何实现一个会话沾滞的负载均衡算法?也就是说,我们需要在同一个客户端上,在一次会话中所有请求都路由到同一个服务器上。

    最直接的方法就是维护一张映射关系表,内容是客户端IP地址或会话ID与服务器编号的映射关系。客户端发出的每次请求,都要先在映射表中查找应该路由到服务器的编号,然后再请求编号对应的服务器,但有几个弊端:

    1、如果客户端很多,映射表可能会很大,比较浪费内存空间。

    2、客户端下线,上线,服务器扩容、缩容都会导致映射失效,这样维护映射表的成本就会很大。

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

    应用六:数据分片

    哈希算法可以用于数据的分片,举两个例子:

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

    假如有1T的日志文件,记录了用户的搜索关键词,我们想要快速统计出每个关键词被搜索的次数。这个问题有两个难点:第一个是搜索日志过大,没办法放到一台机器的内存中。第二个是如果只用一台机器来处理这么巨大的数据,处理时间会很长。

    针对这两个难点,我们可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。具体的思路:为了提高处理的速度,我们用n台机器并行处理。我们从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟n取模,最终得到的值,就是应该被分配的机器编号。

    这样,哈希值相同的搜索关键词就分配到同一个机器上,每一个机器分别计算关键词出现的次数,合并起来就是最终结果。

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

    同样对数据进行分片,采用多机处理。每次从图库中读取一个图片,计算唯一标识,然后与机器个数n求余取模,得到的值就对应要分配的机器编号,然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

    当判断一个图片是否在图库中时,同样通过哈希算法,计算这个图片的唯一标识,然后与机器个数n求余取模。假设得到的值是k,那就去编号k的机器构建的散列表中查找。

    估算一下,1亿个图片构建散列表大约需要多少台机器?假设采用MD5来计算哈希值,那长度为128比特,也就是16字节。文件路径长度上限是256字节,我们假设平均长度是128字节。如果用链表法解决冲突,还需要存储指针,指针只占用8个字节。假设一台机器的内存大小为2GB,散列表装载因子为0.75,故大约1000万(2GB0.75/1522GB*0.75/152)张图片构建散列表。

    针对这种海量数据的处理问题,都可以采用多机分布式处理。

    应用七:分布式存储

    为了提高数据的读取、写入能力,一般都采用分布式的方式来存储数据,比如分布式缓存。如果有大量数据需要缓存,需要将数据分布在多台机器上。借用数据分片的思想,即通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应存储的缓存机器编号。

    但如果数据增多,原来的10个机器已经无法承受,就需要扩容了。比如扩容到11个机器,这时候麻烦就来了。所有的数据都需要重新计算哈希值。然后重新搬移到正确的机器上,这就相当于缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存,直接去请求数据库,这样就可能压垮数据库。

    因此,需要一种方法,使得在新加入一个机器后,并不需要做大量的数据搬移——一致性哈希算法。

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

    参考资料:王争《数据结构与算法之美》

    展开全文
  • 目录什么是hash算法应用一:安全加密应用二:唯一标识应用三:数据校验应用四:...从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到
  • 将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 2.如何设计一个优秀的哈希算法? ①单向哈希: 从哈希值不能反向推导出哈希...
  • Python实现哈希表,Python完成哈希数据结构
  • 前面我们已经讲到了数组和链表,数组能通过下标 O(1) 访问,但是删除一个中间元素却要移动其他元素,时间 O(n)。 循环双端链表倒是可以在知道一... 能不能给每个元素一种『逻辑下标』,然后直接找到它呢,哈希表就是...
  • 从哈希值不能反向推导出原始数据哈希算法也叫单向哈希算法) 对原始值非常敏感,即使只有一个bit不同,也会得到不同的哈希值 散列冲突的概率很小 哈希算法执行效率高,针对较长文本,也能很快算出哈希...
  • 哈希算法定义: 将 任意长度的二进制值串 映射成 固定长度的二进制值串。映射规则即哈希算法哈希算法应用: 安全加密 常用于安全加密的哈希算法有:MD5、SHA。还有DES、AES 唯一标识 如:哈希值用作数据库主键 ...
  • 什么是哈希算法 前面我们学习了散列表,散列...通过原始数据映射成的规定固定长度的二级制串就是哈希值一个优秀的哈希算法应该满足以下几个要求: 一 哈希值不能反向推导出原始数据 二 对输入数据非常敏感,哪怕原...
  • 将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 2. 如何设计一个优秀的哈希算法? 单向哈希: 从哈希值不能反向推导出哈希...
  • 数据结构哈希表的实现,很值得初学者的学习与应用,看完代买能够掌握基本哈希表的应用
  • 哈希算法 简介 将任意长度的二进制值串映射为固定长度的二进制值串的映射规则就是哈希算法 得到的二进制值串就是哈希值 优秀的哈希算法包括 从哈希值不能反推出原始数据 对输入数据非常敏感, 哪怕一点小修改, 结果...
  • 学习笔记|数据结构——哈希算法 哈希算法 将任意长度的二进制值串映射为固定长度的二进制值串,映射规则是哈希算法 通过原始数据映射之后得到的二进制值码就是哈希值 哈希算法要求: 1、从哈希值不能反向推导出原始...
  • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 散列冲突的概率要很小,对于不同的原始数据,哈希值相同.....
  • 计算与数据结构篇 - 哈希算法 (Hash)

    万次阅读 多人点赞 2020-01-21 14:02:00
    计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单,基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二...
  • 数据结构与算法之美 - 22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用? 上一节,我讲了哈希算法的四个应用,它们分别是:安全加密、数据校验、唯一标识、散列函数。今天,我们再来看剩余三种应用:负载...
  • 将任意长度的二进制串映射为固定长度的二进制串,这个映射法则就是哈希算法。映射之后的二进制串就是哈希值。 二、应用场景 1、安全加密 2、唯一标识 3、数据校验 4、散列函数 5、负载均衡 6、数据分片 7、...
  • 哈希算法历史悠久,业界著名的哈希算法也有很多,比如MD5、SHA等。那么在实际的开发中,我们该如何用哈希算法解决问题。 二、什么是哈希算法 将任意长度的二进制值映射为固定长度的二进制值串,这个映...
  • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的...
  • 1、从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 2、对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 3、散列冲突的概率要很小,对于不同的原始数据,哈希...
  • 哈希算法的定义:将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 一个优秀的哈希算法需要满足的以下几点要求: 从哈希值不...
  • 需要插入到哈希表里的数据在第一次被哈希化的时候,保证是除以质数,这个是可以避免同余数。之后再哈希化。 否则会出现步长为0的情况,或者总是相同的情况。 这样的理解是是否正确,但是为什么再往上的解释上出现...
  • 2.网上数据结构算法的课程不少,但存在两个问题:1)授课方式单一,大多是照着代码念一遍,数据结构算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了2)说是讲数据...
  • 将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 哈希算法特点 单向哈希:从哈希值不能反向推导出原始数据(所以哈希算法也...
  • 将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。但是,要想设计一个优秀的哈希算法并不容易,根据经验,需要满足以下几点要求...
  • 哈希算法是将不同长度二进制串转换为固定长度二进制串的算法,在加密,唯一性校验,数据分片等方面都有应用 该叫散列函数还是哈希函数 看到哈希函数时心中总是会泛起疑问,哈希算法需要单独列出,那散列函数又是...
  • 一、什么是哈希算法? 不管 “ 散列” 还是 “哈希” ,这都是中文翻译的差别,英文其实就是 “ Hash” 。所以常听到有人把 “散列表” 叫做 “哈希表”,“Hash表”,把 “哈希算法” ,叫做 “Hash算法” 或者 ...
  • 什么的哈希算法? 将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法。而通过原始数据映射后得到的二进制值串就是哈希值。 一个优秀的哈希算法应该满足哪几点? 从原始数据计算...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,136
精华内容 2,454
关键字:

哈希算法数据结构

数据结构 订阅