hash算法有哪些

by Worktile 项目协作工具

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的存储结构是不是很好理解。