大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章主要讲解了“Hash冲突常用的解决方案有哪些”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Hash冲突常用的解决方案有哪些”吧!
在招远等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供做网站、成都做网站 网站设计制作按需设计网站,公司网站建设,企业网站建设,成都品牌网站建设,全网整合营销推广,外贸网站建设,招远网站建设费用合理。
散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。
哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。
Hash算法可以将一个数据转换为一个标志,这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点,就是很难找到逆向规律。
Hash算法也被称为散列算法,Hash算法虽然被称为算法,但实际上它更像是一种思想。Hash算法没有一个固定的公式,只要符合散列思想的算法都可以被称为是Hash算法。
常见Hash算法介绍:
1)MD4
MD4(RFC 1320)是 MIT 的Ronald L. Rivest在 1990 年设计的,MD 是 Message Digest(消息摘要) 的缩写。它适用在32位字长的处理器上用高速软件实现——它是基于 32位操作数地位操作来实现的。
2)MD5
MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,其输出是4个32位字的级联,与 MD4 相同。MD5比MD4来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好。
3)SHA-1及其他
SHA1是由NIST NSA设计为同DSA一起使用的,它对长度小于264的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计师基于和MD4相同原理,并且模仿了该算法。
所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数。
散列表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。
比如我们存储70个元素,但我们可能为这70个元素申请了100个元素的空间。70/100=0.7,这个数字称为负载因子。
我们之所以这样做,也是为了“快速存取”的目的。
我们基于一种结果尽可能随机平均分布的固定函数H为每个元素安排存储位置,这样就可以避免遍历性质的线性搜索,以达到快速存取。
这类似于70个人去一个有100个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址,每个存储单位称为“桶”。设一个散列表有m个桶,则散列函数的值域应为[0,m-1]。
如果不同的输入经哈希映射得到了同一个哈希值,就发生了"哈希碰撞"(collision)。
假设hash表的大小为11(即有11个槽),现在要把一串数据存到表里:1,2,3,4,5,6...
简单计算一下:hash(1) = 5, 即数据1应该放在hash表的第5个槽里;hash(2)=1,所以数据2应该放在hash表的第1个槽里;hash(3)=1,也就是说,数据3也应该放在hash表的第1个槽里——于是就造成了碰撞(也称为冲突)。
常用的Hash冲突解决方法有以下几种:
这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:
Hi=(H(key)+di)% m i=1,2,…,n
其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:
线性探测再散列
dii=1,2,3,…,m-1
这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。
二次探测再散列
di=12,-12,22,-22,…,k2,-k2 ( k<=m/2 )
这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。
伪随机探测再散列
di=伪随机数序列。
具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。
举个实际应用例子
例如,已知哈希表长度m=11,哈希函数为:
H(key)= key % 11
则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,则H(69)=3,与47冲突。
case1:如果用线性探测再散列处理冲突
下一个哈希地址为
H1=(3 + 1)% 11 = 4
仍然冲突,再找下一个哈希地址为
H2=(3 + 2)% 11 = 5
还是冲突,继续找下一个哈希地址为
H3=(3 + 3)% 11 = 6
此时不再冲突,将69填入5号单元。
case2:二次探测再散列处理冲突
下一个哈希地址为:
H1=(3 + 12)% 11 = 4
仍然冲突,再找下一个哈希地址为
H2=(3 - 12)% 11 = 2
此时不再冲突,将69填入2号单元。
case3:用伪随机探测再散列处理冲突
且伪随机数序列为:2,5,9,……..,则下一个哈希地址为
H1=(3 + 2)% 11 = 5
仍然冲突,再找下一个哈希地址为
H2=(3 + 5)% 11 = 8
此时不再冲突,将69填入8号单元。
这种方法是同时构造多个不同的哈希函数:
Hi=RH1(key) i=1,2,…,k
当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
链地址法优缺点分析:
优点
1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
而对开放地址法构造的散列表,空地址单元(即开放地址)都是查找失败的条件,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填入散列表的同义词结点的查找路径。只能在被删结点上做删除标记,而不能真正删除结点。
缺点
拉链法的缺点是:
指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。
上面说到的md5就是其中的一个, 好像还有一个什么SHA, 不过我不知道, 也就不展开探讨了.
md5可以将一个文件经过计算转换成一个指定长度的字符串, 可以防止文件被篡改, 但是通过加密后的字符串很难逆向推出原文.
前面那个例子可以看到, 即使文件被修改了一点点, 也会导致计算后的值发生很大变化.
比如说, 现在有十万个文件, 给你一个文件, 要你在这十万个文件中查找是否存在. 一个很笨的办法就是把每一文件都拿出来, 然后按照二进制串一一进行对比. 但是这个操作注定是比较费时的.
可以用哈希算法对文件进行计算, 然后比较哈希值是否相同. 因为存在哈希冲突的情况, 你可以在相同哈希值的文件再进行二进制串比较.
在哈希表中使用哈希函数已经并不陌生了, 在此不再赘述。
比如说, 现在又多台服务器, 来了一个请求, 如何确定这个请求应该路由到哪个路由器呢?当然, 必须确保相同的请求经过路由到达同一个服务器. 一种办法就是保存一张路由关系的表, 比如客户端IP和服务器编号的映射, 但是如果客户端很多, 势必查找的时间会很长. 这时, 可以将客户端的唯一标识信息(如:IP、username等)进行哈希计算, 然后与服务器个数取模, 得到的就是服务器的编号.
当我们有大量数据时, 一般会选择将数据存储到多个服务器, 为了提高读取与写入的速度嘛. 决定将文件存储到哪台服务器, 就可以通过哈希算法取模的操作来得到。
感谢各位的阅读,以上就是“Hash冲突常用的解决方案有哪些”的内容了,经过本文的学习后,相信大家对Hash冲突常用的解决方案有哪些这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!