2020数据结构-查找之散列表

一、散列表

1.基本概念

1. 线性表和树表的查找中，记录在表中的位置与记录的关键字之间不存在确定的关系，因此，在这些表中查找记录时需要一些关键字比较。这类查找建立在“比较”的基础上，查找的效率取决于比较的次数。
2. 散列函数：把查找表中的关键字映射成该关键字对应的地址的函数（这里的地址可以是数组下标、索引或内存地址等）。
3. 冲突：散列函数可能会把两个或两个以上的不同关键字映射到同一地址。
4. 同义词：上述发生碰撞的不同关键字。
5. 散列表：根据关键字而直接进行访问的数据结构；散列表建立了关键字和存储地址之间的一种直接映射关系。

2.构造方法

在构造散列函数时，必须注意以下几点：

1. 散列函数的定义域必须包含全部的需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
2. 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，尽量减少冲突的发生。
3. 散列函数应尽量简单，能够在较短时间内计算出任一关键字对应的散列地址。

常用的散列函数：

1. 直接定址法
   直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a*key+b
   a和b为常数，这种方法计算简单，且不会产生冲突，适合关键字的分布基本连续，若分布不连续，空位较多 ，则会造成存储空间的浪费。
2. 除留余数法
   最简单、最常用；假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字装换成散列地址。散列函数为：H(key) = key MOD p(取余)。
3. 数字分析法
   假设关键字集合中的每个关键字key都是由s位数字组成（k1,k2,……,kn）,分析key中的全体数据，并从中提取分布均匀的若干位或他们的组合构成全体。
   比如：我们知道身份证号是有规律的，现在我们要存储一个班级学生的身份证号码，假设这个班级的学生都出生在同一个地区，同一年，那么他们的身份证的前面数位都是相同的，那么我们可以截取后面不同的几位存储，假设有5位不同，那么就用这五位代表地址。
   H（key）=key%100000
   此种方法通常用于数字位数较长的情况，必须数字存在一定规律，其必须知道数字的分布情况，比如上面的例子，我们事先知道这个班级的学生出生在同一年，同一个地区。
4. 平房取中法
   如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。
   比如key=1234 1234^2=1522756 取227作hash地址
   比如key=4321 4321^2=18671041 取671作hash地址
   这种方法适合事先不知道数据并且数据长度较小的情况
5. 折叠法
   将关键字分割成位数相同的几部分（最后一部分的位数可以短一点），取他们的叠加和作为hash地址。
   比如key=123 456 789
   我们可以存储在61524，取末三位，存在524的位置
   该方法适用于数字位数较多且事先不知道数据分布的情况

3.处理冲突

任何设计出来的散列函数都不可能完全避免冲突，我们应该考虑如何处理发生的冲突，即为产生冲突的关键字寻找下一个“空”的hash地址；处理冲突主要有以下几种方法：

1. 开放定址法
   如果H(key1)=H(keyi)，那么keyi存储位置Hi=(H(key)+di) MOD m ；m为表长，di有三种取法：
   (1) 线性探测法：发生冲突时顺序查看下一个单元（当探测到表尾时，下一个单元在表首地址0），直到找出一个空闲单元或查遍全表；线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个的元素便去争夺i+2个元素的地址，造成大量元素在散列地址上聚集（或堆积起来）,大大降低了查找效率。
   (2)平方探测法：
   di = 11,-11,22,-22…kk,-kk(k<=m/2)，散列表的长度必须是一个可以表示成4k+3的素数，又称二次探测法。
   可以避免出现堆积，但是不能探测到散列表上的所有单元，不过至少能探测到一半。
   (3)再散列法：
   需要使用两个散列函数，当通过第一个散列函数时H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量，具体散列函数如下：Hi = (H(key)+iHash2(key))%m。
   初次探测位置H0 = H(key)%m。i是冲突次数，初始为0。在散列法中，最多经过m-1次探测就会遍历表中的所有位置，回到H0位置。
   示例如下：
   
   
2. 拉链法
   对不同的关键字可能通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。表示散列地址为i的同义词链表的头指针存放着散列表的第i个单元，因而查找、插入和删除主要在同义词链中进行。拉链法适合经常进行插入和删除的情况。
   

4.散列查找及性能分析

1. 散列查找
   查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
   对于给定的key，计算hash地址index = H（key）
   如果数组arr【index】的值为空 则查找不成功
   如果数组arr【index】== key 则查找成功
   否则 使用冲突解决方法求下一个地址，直到arr【index】== key或者 arr【index】==null
2. 性能分析
   决定hash表查找的ASL因素：
   1）选用的hash函数
   2）选用的处理冲突的方法
   3）hash表的饱和度，装载因子 α=n/m(n表示实际装载数据长度 m为表长)
   一般情况，假设hash函数是均匀的，则在讨论ASL时可以不考虑它的因素
   hash表的ASL是处理冲突方法和装载因子的函数
   前人已经证明，查找成功时如下结果：
   
   可以看到无论哪个函数，装载因子越大，平均查找长度越大，那么装载因子α越小越好？也不是，就像100的表长只存一个数据，α是小了，但是空间利用率不高啊，这里就是时间空间的取舍问题了。通常情况下，认为α=0.75是时间空间综合利用效率最高的情况。
   上面的这个表可是特别有用的。假设我现在有10个数据，想使用链地址法解决冲突，并要求平均查找长度<2
   那么有1+α/2 <2
   α<2
   即 n/m<2 (n=10)
   m>10/2
   m>5 即采用链地址法，使得平均查找长度< 2 那么m>5
   hash表是基于装载因子的函数，也就是说，当数据n增加时，我可以通过增加表长m，以维持装载因子不变，确保ASL不变。
   那么hash表的构造应该是这样的：