管理进化

hash算法有哪些


hash算法有以下5种:1. MD4;2. MD5;3. SHA-1及其他;4. 一致性hash算法;5. hash碰撞及避免碰撞策略。hash算法,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。

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相同原理,并且模仿了该算法。

4. 一致性hash算法

为了减少碰撞,按照一定的物理规律模拟出来一个环,将自己的有限资源分布在环上,然后每当一个请求寻址过来时,按照计算给予分配环上的资源。以上这句话是本人自己总结的,里面有几个问题:1.环的构造方式是什么?2.怎样将有限的资源在环上分配?3.怎样合理有效的分配资源?4.怎样判断构造的环的优缺?..

5. Hash碰撞及避免碰撞策略

对象Hash的前提是实现equals()和hashCode()两个方法,那么HashCode()的作用就是保证对象返回唯一hash值,但当两个对象计算值一样时,这就发生了碰撞冲突。如下将介绍如何处理冲突,当然其前提是一致性hash。

开放地址法(再散列法)

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k

其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2),称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

再哈希法Rehash

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止.这种方法不易产生聚集,但增加了计算时间。

链地址法(拉链法)

将所有关键字为同义词的记录存储在同一线性链表中.基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。对比JDK 1.7 hashMap的存储结构是不是很好理解。

智齿客服