哈希表—学习笔记

根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的联系的联系的地址集(区间)上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表。这一映像过程称为哈希造表或散列。所得存储位置称哈希地址或散列地址。

构造哈希函数的目标是使得到得哈希尽可能地均匀分布在n个连续内存单元地址上，同时使计算过程尽可能简单，以达到尽可能高的时间效率。

 

哈希函数的构造方法

1、直接定址法

取关键字或关键字的某个线性函数值为哈希地址，即：

                   H(key)=key或H(key)=a.key+b

其中a和b为常数(这种哈希函数叫自身函数)。

2、数字分析法

假设关键字是以r为基数(如以10为基数的十进制数)并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

3、平方取中法

取关键字平方后的中间几位为哈希地址。是一种较常用的构造哈希函数的方法。

4、折叠法

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

5、除留余数法

取关键字被某个不大于哈希表长m的数p除后所得的余数为哈希地址。即：

                    H(key)=key MOD p，p<=m

这是一种最简单也是最常用的构造哈希函数的方法，它不仅可以对关键字直接取模(MOD)也可在折叠，平方取中等运算之后取模。

6、随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址。即H(key)=random(key)，其中random为随机函数，通常为关键字长度不等时采用此法构造哈希函数较恰当。

实际工作中需视不同的情况采用不同的哈希函数。通常考虑的因素有：

（1）    计算哈希函数所需时间(包括硬件指令的因素)

（2）    关键字的长度

（3）    哈希表的大小

（4）    关键字的分布情况

（5）    记录的查找频率

处理冲突的方法

1、开放地址法

                  H_i=(H(key)+d_i)MODm i=1,2,…,k (k<=m-1)

其中：H(key)为哈希函数；m为哈希表长；d_i为增量序列，可能有下列3种取法：

（1）  di=1,2,3,…,m-1，称线性探测再散列；

（2）  d_i=1²,-1²,2²,-2²,3²,…,±k²(k<=m/2)称二次探测再散列；

（3）  d_i=伪随机数序列，称伪随机探测再散列。

2、再哈希法

H_i=RH_i(key)   i=1,2,3,…,k

RH_i均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。

3、链地址法

将所有关键字为同义词的记录存储在同一线性表中。假设某哈希函数产生的哈希地址在区间[0，m-1]上，则设定一个指针型向量：

                       Chain ChainHash[m]

其每个分量的初始化状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在链表中的插入位置可以再表头或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。

4、建立一个公共溢出区

假设哈希函数的值域为[0，m-1]，则设向量HashTable[0…m-1]为基本表，每个分量存放一个记录，另设向量VoerTable[0…v]为溢出表，所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

哈希表查找的性能分析

哈希表的装填因子定义为：

         a=表中装入的记录数/哈希表的长度

装填因子a表示哈希表的装满程度，直观的看，a越小，发生冲突的可能性越小；反之，a越大，发生冲突的可能性越大。

 

平均查找长度：

成功时：

（1）    线性表探测再散列的哈希表查找成功的平均查找长度为1/2(1+1/(1-a))。

（2）    随机探测再散列，二次探测在散列的哈希表查找成功的平均查找长度为

-(1/a*log₂(1-a))。

（3）    链地址法的哈希表查找成功的平均查找长度为1+a/2。

不成功时：

（1）    线性表探测再散列的哈希表查找不成功的平均查找长度为1/2(1+1/(1-a)²)。

（2）    随机探测再散列，二次探测在散列的哈希表查找不成功的平均查找长度为

1/(1-a)

链地址法的哈希表查找不成功的平均查找长度为a+e^-a。