哈希表总结

素颜马尾好姑娘i 2022-08-18 02:37 182阅读 0赞

**哈希表的概念**

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

**散列存储的基本思路**

以数据中每个元素的关键字K为自变量，通过散列函数H（k）计算出函数值，以该函数值作为一块**连续**存储空间的的单元地址，将该元素存储到函数值对应的单元中。

**哈希表查找的时间复杂度**

哈希表存储的是键值对，其查找的时间复杂度与元素数量多少无关，哈希表在查找元素时是**通过计算哈希码值来定位元素的位置**从而直接访问元素的，因此，哈希表查找的时间复杂度为O（1）。

**哈希函数的构造方法**

哈希表处理冲突主要有开房寻址法、再散列法、链地址法（拉链法）和建立一个公共溢出区四种方法。

**1. 直接寻址法**

取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a\*Key+b(a,b为整数),这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,知道找到H(Key)的位置没有值了就把元素放进去.

**2. 数字分析法**

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

**3. 平方取中法**

**取关键字平方后的中间几位作为散列地址.**

**4. 折叠法**

折叠法即将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址.数位叠加可以有移位叠加和间界叠加两种方法.移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加.

**5. 随机数法**

选择一个随机数,去关键字的随机值作为散列地址,通常用于关键字长度不同的场合.

**6. 除留余数法**

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选得不好，则很容易产生冲突。

**哈希表如何处理冲突**

哈希表处理冲突主要有开放寻址法、再散列法、链地址法（拉链法）和建立一个公共溢出区四种方法。

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

**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中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。

例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突的结果如图8.27所示：

图8.27 链地址法处理冲突时的哈希表

本例的平均查找长度 ASL=(1\*7+2\*4+3\*1)/12=1.5

拉链法的优点

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

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

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

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

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

拉链法的缺点

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

**4、建立公共溢出区**

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表.(**注意：在这个方法里面是把元素分开两个表来存储**)

**冲突太多了怎么办?**

当冲突太多的时候,我们一般采用的方法时拉链法,采用拉链法的原因是动态申请空间,至于优点在上面已经阐述了.冲突太多的时候会产生堆积状态,我们将H(key)相同的关键字都统一放到一个链里,当出现冲突的时候我们就把该元素接在链表后面,这样可以避免产生堆积现象,缩短平均查找长度.

**当数据表太小,而数据太多的时候怎么办?**

当数据表太小数据太多可以通过建立一个溢出表,专门用来存放哈希表中放不下的记录.