什么是散列表（Hash Table）

摘要：称这个对应关系为散列函数，按这个思想建立的表为散列表。具有相同函数值的关键字对该散列函数来说称做同义词。此时线性探测的方法是取并假定取关键字除以的余数为散列函数法则。

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

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 x 到首字母 F(x) 的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

若关键字为 k，则其值存放在f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。

对不同的关键字k可能得到同一散列地址，即

$$ k1≠k2 $$

，而

$$ f(k1)=f(k2) $$

，这种现象称为冲突（或碰撞，英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k) 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。

直接定址法：取关键字或关键字的某个线性函数值为散列地址。即

$$ hash(k)=k $$

或

$$ hash(k)=a cdot k+b $$

, 其中ab为常数（这种散列函数叫做自身函数）

数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即

$$ hash(k)=k,{mod {,}}p $$

$$ pleq m $$

不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理，而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：

开放寻址法(open addressing)。想象一下，有一趟对号入座的火车，假设它只有一节车厢，上来一位坐7号座位的旅客。过了一会儿，又上来一位旅客，他买到的是一张假票，也是7号座位，这时怎么办呢？列车长想了想，让拿假票的旅客去坐8号座位。过了一会儿，应该坐8号座位的旅客上来了，列车长对他说8号座位已经有人了，你去坐9号座位吧。哦？9号早就有人了？10号也有人了？那你去坐11号吧。可以想见，越到后来，当空座越来越少时，碰撞的几率就越大，寻找空座愈发地费劲。但是，如果是火车的上座率只有50%或者更少的情况呢？也许真正坐8号座位的乘客永远不会上车，那么让拿假票的乘客坐8号座位就是一个很好的策略了。所以，这是一个空间换时间的游戏。玩好这个游戏的关键是，让旅客分散地坐在车厢里。如何才能做到这一点呢？答案是，对于每位不同的旅客使用不同的探查序列。例如，对于旅客 A，探查座位 7，8，23，56……直到找到一个空位；对于旅客B，探查座位 25，66，77，1，3……直到找到一个空位。如果有 m 个座位，每位旅客可以使用 <0, 1, 2, ..., m-1> 的m! 个排列中的一个。

显而易见，最好减少两个旅客使用相同的探查序列的情况。也就是说，希望把每位旅客尽量分散地映射到 m! 种探查序列上。换句话说，理想状态下，如果能够让每个上车的旅客，使用 m! 个探查序列中的任意一个的可能性是相同的，我们就说实现了一致散列。（这里没有用“随机”这个词儿，因为实际是不可能随机取一个探查序列的，因为在查找这名旅客时还要使用相同的探查序列）。

线性探查：最简单的方法是，如果发现 values[8] 已经被占用了，就看看 values[9] 是否空着，如果 values[9] 也被占用了，就看看 values[0] 是不是还空着。完整的描述是，先使用 H() 函数获取 k 的第一个地址，如果这个地址已被占用，就探查下一个紧挨着的地址，如果还是不能用，就探查下一个紧挨着的地址，如果到达了数组的末尾，就卷绕到数组的开头，如果探查了 m 次还是没有找到空槽，就说明数组已经满了，这就是线性探查（linear probing）

真正的一致散列是难以实现的，实践中，常常采用它的一些近似方法。常用的产生探查序列的方法有：线性探查，平方探测，以及双重散列探查。这些方法都不能实现一致散列，因为它们能产生的不同探查序列数都不超过

$$ m^2 $$

个（一致散列要求有 m! 个探查序列）。在这三种方法中，双重散列能产生的探查序列数最多，因而能给出最好的结果。

显示线性探测填装一个散列表的过程：

关键字为{89,18,49,58,69}插入到一个散列表中的情况。此时线性探测的方法是取

$$ d_{i}=i $$

并假定取关键字除以10的余数为散列函数法则。

第一次冲突发生在填装49的时候。地址为9的单元已经填装了89这个关键字，所以取 $i=1$，往下查找一个单位，发现为空，所以将49填装在地址为0的空单元。

第二次冲突则发生在58上，取i=3，往下查找3个单位，将58填装在地址为1的空单元。69同理。
表的大小选取至关重要，此处选取10作为大小，发生冲突的几率就比选择质数11作为大小的可能性大。越是质数，mod取余就越可能均匀分布在表的各处。

聚集（Cluster，也翻译做“堆积”）的意思是，在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。

转载请注明出处