哈希表的定义

“散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

用来：可以根据一个key值来直接访问数据，因此查找速度快

在最基本的几个数据结构中，数组肯定是查询效率是最高的。因为它可以直接通过数组下标来访问数据

其实哈希表的本质上就是一个数组，它之所以叫哈希表，只能说它的底层实现是用到了数组，稍微加工，自立门户成了哈希表

散列技术既是一种存储方法， 也是一种查找方法，散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到置上。

这里我们把这种对应关系f称为散列函数，又称为哈希(Hash) 函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们称为散列地址。

存储位置=f(关键字)

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素的个数无关。

散列函数的构造方法

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

1.散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。

2.散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。

3.散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。

1、直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为

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

式中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

举例：0~100岁的人口数字统计表，可以吧年龄数值直接当做散列地址。

2、数字分析法

例如当手机号码为关键字时，其11位数字是有规则的，此时是无需把11位数值全部当做散列地址，这时我们给关键词抽取， 抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

3、平方取中法

这个方法计算很简单，假设关键字是1234，那么它的平方就是，再抽取中间的3位就是227，用做散列地址。再比如关键字是4321，那么它的平方就是，抽取中间的3位就可以是671，也可以是710，用做散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

4、除留余数法

这是一种最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为

讯享网

H(key)=key%p (p<=m)

事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

5、随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是

H(key)=random(key)

这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

处理散列冲突

1.开放地址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

它的公式是：

Hi(key)=(f(key)+di)%m (di=1,2,3,...,m−1)

式中，H(key)为散列函数；i=0,1,2,...,k (k<=m−1)；m表示散列列表表长；di 为增量序列。

取定某一增量序列后，对应的处理方法就是确定的。通常有以下4种取法：

1.线性探测法。当di=0,1,2,...,m−1时，称为线性探测法。这种方法的特点是:冲突发生时，顺序查看表中下一个单元(探测到表尾地址m−1时，下一个探测地址是表首地址0)，直到找出一个空闲单元(当表未填满时一定能找到一个空闲单元)或查遍全表。

线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址，从而造成大量元素在相邻的散列地址上堆积，大大降低了查找效率。

2.平方探测法。当di=0^2,1^2,−1^2,2^2,−2^2,..,k^2,−k^2 时，称为平方探测法，其中k<m/2，散列表长度m必须是一个可以表示成4k+3的素数，又称二次探测法。

平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

3.再散列法。当di=Hash2(key)时，称为再散列法，又称双散列法。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量。它的具体散列函数形式如下：

Hi=(H(key)+i∗Hash2(key))%m初始探测位置H0=H(key)。i是冲突的次数，初始为0。在再散列法中，最多经过m−1次探测就会遍历表中所有位置，回到H0位置。

4.伪随机序列法。当di=伪随机数序列时，称为伪随机序列法。

注意:在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

2、链地址法（拉链法）

不换地方。

转换一下思路，为什么非得有冲突就要换地方呢，如果不换地方该怎么处理？于是我们就有了链地址法。

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

例如，关键字序列为{12,67,56,16,25,37,22,29,15,47,48,34}，我们用除留余数法构造散列函数H(key)=key%12，用拉链法处理冲突，建立的表如下图所示。