【软考】哈希表

一、概念

1.1 定义

• 1.一般存储结构由于记录在存储结构中的相对位置是随机的，查找时通过一系列与关键字的比较才能确定被查记录在表中的位置。
• 2.哈希表则通过计算一个以记录的关键字为自变量的函数（称为哈希函数）来得到该记录的存储地址。
• 3.哈希表中进行查找时，需用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。
• 4.根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
• 5.对于某个哈希函数H和两个关键字K₁和K₂，如果K₁≠K₂，而H(K₁)=H(K₂)，则称为冲突。
• 6.具有相同哈希函数值的关键字对该哈希函数来说称为同义词。
• 7.冲突只能尽可能减少而不能完全避免，因为哈希函数是从关键字集合到地址集合的映像。
• 8.通常关键字集合比较大，它的元素包含所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。
• 9.一般情况下，哈希函数是一个压缩映像，冲突是不可避免的。

二、哈希函数的构造方法

2.1 说明

• 1.常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。

2.2 特性

• 1.哈希函数应是一个压缩映像函数，它应具有较大的压缩性，以节省存储空间。
• 2.哈希函数应具有较好的散列性，虽然冲突是不可避免的，但应尽量减少。
• 3.要减少冲突，就要设法使哈希函数尽可能均匀地把关键字映射到存储区的各个存储单元，这样就可以提高査找效率。
• 4.在构造哈希函数时，一般都要对关键字进行计算，且尽可能使关键字的所有组成部分都能起作用。

三、处理冲突的方法

3.1 说明

• 1.解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。在处理冲突的过程中，可能得到一个地址序列 H(i=1,2,…,k)。

3.2 开放定址法

3.2.1 说明

• 1.H_i=(H(key)+d_i)%m i=1,2,…,k (k ≤ m-1)其中，H(key)为哈希函数，m为哈希表表长
• 2.常见的增量序列有：线性探测再散列d_i=1,2,3,…,m-1；二次探测再散列d_i=1²,-1²,2²,-2²,…,±k²(k≤m/2)；随机探测再散列d_i=伪随机数序列

3.2.2 线性探测

• 1.最简单的产生探测序列的方法是进行线性探测，也就是发生冲突时，顺序地到存储区的下个单元进行探测。
• 2.例如，某记录的关键字为 key，哈希函数值 H(key)。若在哈希地址j发生了冲突(即此位置已存放了其他记录)，则对哈希地址j+1进行探测，若仍然有冲突，再对地址 j+2 进行探测，依此类推，直到找到一个“空”的单元并将元素存入哈希表。
• 3.线性探测法可能使第i个哈希地址的同义词存入第 i+1 个哈希地址，这样本应存入第 i+1个哈希地址的元素变成了第 i+2个哈希地址元素的同义词
• 4.线性探测法的优点：思路清楚，算法简单
• 5.线性探测法的缺点：① 溢出处理需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。实现溢出表最简单的结构是顺序表，查找方法可用顺序查找。② 线性探测法很容易产生聚集现象。所谓聚集现象，就是存入哈希表的记录在表中连成一片。当哈希函数不能把关键字很均匀地散列到哈希表中时，尤其容易产生聚集现象，这种情况下会增加探测的次数，从而降低了查找效率。
• 6.用户可以采取多种方法减少聚集现象的产生，二次探测再散列和随机探测再散列是两种有效的方法。

3.3 链地址法

• 1.也叫拉链法。
• 2.在查找表的每个记录中增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。
• 3.利用链域把发生冲突的记录链接在一个链表中
• 4.当链域的值为null，表示已没有后继记录
• 5.对于发生冲突时的查找和插入操作和线性表一样

3.4 再哈希法

• 1.H_i=RH_i(key)(i=1,2,…,k)
• 2.RH_i均是不同的哈希函数，即在同义词发生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生聚集现象，但增加了计算时间。

3.5 建立公共溢出区

• 1.发生冲突，都填入到公共溢出区中。

四、哈希表的查找

4.1 查找过程

• 1.在哈希表中进行查找操作时，用与存入元素时相同的哈希函数和冲突处理方法计算得到待查记录的存储地址，然后到相应的存储单元获得有关信息再判定查找是否成功。

4.2 查找特点

• 1.哈希表在关键字与记录的存储位置之间建立了直接映像，由于冲突，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。所以需要以平均查找长度衡量哈希表的查找效率。
• 2.在查找过程中需要和给定值进行比较的关键字的个数取决于三个因素：哈希函数、处理冲突的方法和哈希表的装填因子。

4.3 装填因子

• 1.装填因子的定义
  
• 2.α标志着哈希表的装满程度。
• 3.α越小，发生冲突的可能性越小；α越大，表中已填入的记录越多，再装填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也越多。