关于哈希表,HashMap的再次理解

哈希函数是一种对应关系,是一个映射,能将关键词转为哈希函数值,便于更快的查询。当然对不同的关键字可能得到同一哈希地址,即,key1!=key2,而f(key1)=f(key2)。这种现象称为冲突。一般情况下,冲突只能尽可能的少,而不能完全避免

对于关键词集合中任意一个关键词,经哈希函数映射到地址中任何一个地址的概率是相等的,称此类哈希函数为均匀哈希函数,这种算比好的哈希函数。一般而言,构造哈希函数的方法有以下几种:

1.直接地址法

取关键字或关键字的某个线性函数值为哈希地址。H(key)=key ,H(key)=a*key+b

2.数字分析法

以关键字中的若干数位组合成哈希地址。

3.平均取中法。

取关键字平方后中间几位为哈希地址

4.折叠法,取关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。

5.除留余数法。取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址,即H(key)=key MOD p ,p<=m

这是一种最简单,也是最常用的构造哈希函数的方法。

6.随机数发。

处理冲突的一些方法。如果又关键字得到的哈希地址为j的位置上已存有记录,则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。若得到的另一个哈希地址H1仍然发生冲突,则再求下一个地址H2,若H2任然冲突,再求H3,一次类推。

1.开放地址法

Hi=(H(key)+di) MOD m  i=1,2,3…k (k<=m-1)

m为哈希表表长;di为增量序列,可有下列三种取法:1>di=1,2,3…m-1 称为线性探测再散列;2>di=1^2,-1^2,2^2,-2^2,3^2…k^2(k<=m/2)二次探测再散列  3>di=伪随机数序列,伪随机探测再散列。

2.再哈希法

Hi=RHi(key)  i=1,2,3.。。k

3.链地址法

4.建立一个公共溢出区。

1.深入理解HashMap

2.HashMap存储结构浅析