散列表（Hash表）

散列表使用直接寻址的思想，根据key计算地址，然后作为下表去操作元素。最简单的散列表是直接寻址表，它和数组类似，对于每个可能的key分配一个表项，但这种方法要求较大的存储空间为每一个key保留一个位置。因此，散列表往往将多个key映射到同一个表项，这个过程中就牵扯到了如何映射，以及如何解决冲突的问题。而对于散列表的实现，最重要的就是散列函数、冲突解决方法。<!--more-->

直接寻址表和散列表

当关键词的全域比较小时，即所有关键词的个数不大，可采用直接寻址表为每一个关键词预留一个位置，对于每个实际的关键词，只想一个元素。而对于没有出现的关键词，设置为NULL。这种方法要求较大的存储空间，但是方法简单，对于查找、插入和删除操作，也只需要O(1)的时间。

但是key的全域一般较大，而实际的key可能较小，为每个key都保留一个位置不太实际。因此，可以创建大小为m的散列表，使用散列函数h:U->{1,2,…m-1}，将所有的key都映射到m个散列表中，从而降低了空间开销。h(key)就是元素的存储位置。

散列函数

散列函数又称hash函数，是将key映射到地址的函数。

好的散列函数应该尽量满足简单一致散列的假设：每个关键词都等可能的散列到m个表项中的任意一个，与其他关键词已被散列到哪个表项无关。

在使用散列函数前，需要将非自然数的关键词解释为自然数。

常用的散列函数：

• 除法散列法：h(k)=k %m（最常用）
• 乘法散列法：h(k)=(向下取整)m(kA%1)
• 直接定址法：即直接寻址
• 数字分析法：
• 取平方法
• 随机数法：随机函数

解决冲突的方法

因为将|U|个关键字映射到大小为m的散列表中，肯定会出现两个关键字映射到同一表项。当现实中出现这种情况时，成为冲突。如何解决冲突，是散列表的另一个重要问题。

1链接法

散列表中存放指针，指向一个链表。将映射到这个散列表项的所有元素都用链表存起来。

2 开放寻址法

在开放寻址法中，所有的元素都存放在散列表中，当出现冲突的时候，就根据探查序列去寻找下一个地址，直至找到为空的地址。

开放寻址的散列函数有两个参数，第一个是关键字，第二个是探查号。h:U*{0,1,…m-1}->{0,1,…,m-1}

对每一个关键词k，探查序列为：<h(k,0), h(k,1), …,h(k,m-1)>

插入时，初始探查号为0，查看散列表表项是否为空，如果不为空，探查号增加直至找到为空的表项将元素插入。

查找时，初始探查号为0，查看表项是否为要查找的元素，探查号增加直至查找到为空的表项。

删除时，先通过查找找到元素，不能简单的将表项置为空，因为查找时需要使用空作为标识。因此将其置为一个特殊的值，比如为DELETE。

探查序列主要有三种：线性探查，二次探查及双重探查

1. 线性探查
   线性探查就是当发现这个表项不为空时，就去寻找下一个。当寻找到最后一个表项时，再从头查找。
2. 二次探查
   1^2, -1^2, 2^2,-2^2,3^2, …, ±k^2,(k<=m/2)称二次探查;
3. 双重探查
   h(k,i)=(h1(k)+ih2(k))mod m

3 再哈希法

再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生"聚集"，但增加了计算时间。

例题

已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7计算散列地址，并散列存储在散列表A【0....6】中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（C）

A、1.5 B、1.7?? C、2.0? D、2.3

（1+3+1+1+2+4）/6=2