算法学习-哈希表

定义

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

优缺点

  • 优点:哈希表可以提供快速的操作。
  • 缺点:哈希表通常是基于数组的,数组创建后难于扩展。
    也没有一种简便的方法可以以任何一种顺序〔例如从小到大)遍历表中的数据项。

综上,如果不需要有序遍历数据,井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

哈希查找

  • 使用哈希函数将被查找的键转换为数组的索引。
  • 处理哈希碰撞冲突。

散列函数

若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。

若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个”随机的地址”,从而减少碰撞。

散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。

一个好的散列函数一般应该考虑下列因素:

  • 计算简单,以便提高转换速度。
  • 关键词对应的地址空间分布均匀,以尽量减少冲突。

常见的散列函数

  • 直接定址法:取关键字key的某个线性函数为散列地址,如Hash(key) = key 或 Hash(key) = A*key+B;A,B为常数
  • 除留取余法:关键值除以比散列表长度小的素数所得的余数作为散列地址。Hash(key) = key % p;
  • 平均取中法:先计算构成关键码的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址。
  • 折叠法:把关键码自左到右分为位数相等的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。把这些部分的数据叠加起来,就可以得到具有关键码的记录的散列地址。分为移位法和分界法。
  • 随机数法:选择一个随机函数,取关键字的随机函数作为它的哈希地址。
  • 数学分析法:设有N个d位数,每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布均匀些,每种符号出现的机会均等;在某些位上分布不均匀,只有某几种符号经常出现。可根据散列表的大小,选取其中各种符号分布均匀的若干位作为散列地址。

处理冲突

对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。

通过构造性能良好的散列函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突的方法应该一致。

开放定址法

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

线性探测再散列
di=1,2,3,…,m-1
这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

二次探测再散列
di=12,-12,22,-22,…,k2,-k2( k<=m/2 )
这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

伪随机探测再散列
di=伪随机数序列。
线性探测再散列的优点是:只要哈希表不满,就一定能找到一个不冲突的哈希地址,而二次探测再散列和伪随机探测再散列则不一定。线性探测再散列容易产生“二次聚集”,即在处理同义词的冲突时又导致非同义词的冲突。

再哈希法

这种方法是同时构造多个不同的哈希函数:Hi=RHi(key),i=1,2,3,…,n。
当哈希地址H1=RH1(key)发生冲突时,再计算H2=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

链地址法(拉链法)

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

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

  • 拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
  • 由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
  • 开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中理论上可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;(散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度)
  • 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放定址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放定址法中,空地址单元都被理解没有查找到元素。 因此在用开放定址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

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

建立公共溢出区

将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表(在这个方法里面是把元素分开两个表来存储)。

查找性能

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。

查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。

影响产生冲突多少有以下三个因素:

  • 散列函数是否均匀;
  • 处理冲突的方法;
  • 散列表的装填因子。