哈希表

哈希表的概念:

  哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。

哈希函数的构造方法:

常见的构造哈希函数的方法有:直接定址法、数字分析法、平均取中法、折叠法、除留余数法、随机数法。

1.直接定址法

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

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

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

2.数字分析法

分析一组数据,比如一组员工的出生年月,这时我们发现出生年月的前几位数字一般都相同,因此,出现冲突的概率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果利用后面的几位数字来构造散列地址,则冲突的几率则会明显降低.因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址.

3.平方取中法

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

4.折叠法

将关键字分隔成位数相同的几部分(最后一分部的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这种方法称为折叠法。关键字位数很多,而且关键字中每一位上数字分布大致均匀时,可以采用折叠法得到哈希地址。

5.除留余数法

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

H(key) = key MOD p, p ≤ m

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

6.随机数法

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

 

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

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

②:关键字的长度

③:哈希表的大小

④:关键字的分布情况

⑤:记录的查找频率

 

处理冲突的方法:

通常用的处理冲突的方法有:开放定址法、再哈希法、链地址法、建立一个公共溢出区。

1.开放地址法

这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:Hi=(H(key)+di)%m   i=1,2,…,n,其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

(1) 线性探测再散列

di=1,2,3,…,m-1

这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

(2)二次探测再散列

   di=12,-12,22,-22,…,k2,-k2    ( k<=m/2)

    这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

(3)伪随机探测再散列

    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冲突。如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元。如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 – 12)% 11 = 2,此时不再冲突,将69填入2号单元。如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,……..,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元。

从上述例子可以看出,线性探测再散列容易产生“二次聚集”,即在处理同义词的冲突时又导致非同义词的冲突。例如,当表中i, i+1 ,i+2三个单元已满时,下一个哈希地址为i, 或i+1 ,或i+2,或i+3的元素,都将填入i+3这同一个单元,而这四个元素并非同义词。线性探测再散列的优点是:只要哈希表不满,就一定能找到一个不冲突的哈希地址,而二次探测再散列和伪随机探测再散列则不一定。

2.再哈希法

这种方法是同时构造多个不同的哈希函数:

        Hi=RH1(key),i=1,2,3,…,n.

        当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间

3.链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。

例:已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79)则按哈希函数H(key)=key MOD 13 和链地址法处理冲突构造所得的哈希表如图:

28、哈希表(Hash)的查找 - 墨涵 - 墨涵天地

拉链法的优点

与开放定址法相比,拉链法有如下几个优点:

(1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

(2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

(3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

(4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。 因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

拉链法的缺点

 拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

4、建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表.

(注意:在这个方法里面是把元素分开两个表来存储)

 

哈希表的查找分析:

哈希表的查找过程基本上和造表过程相同。一些关键码可通过哈希函数转换的地址直接找到,另一些关键码在哈希函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对哈希表查找效率的量度,依然用平均查找长度来衡量。
  查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
1.哈希函数是否均匀; 
2.处理冲突的方法; 
3.哈希表的装填因子。

α = 表中填入的记录数/哈希表的长度

α是哈希表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。
  实际上,哈希表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。以下给出几种不同处理冲突方法的平均查找长度:

哈希表及其查找

 哈希方法存取速度快、节省空间,静态查找、动态查找均适用,但由于存取是随机的,因此,不便于顺序查找。

本文链接:http://www.blogfshare.com/hash-table.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>