散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 x 到首字母 F(x) 的一个函数关系），在首字母为 W 的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则 F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
1. 基本概念
- 若关键字为 k，则其值存放在f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。
- 对不同的关键字 k 可能得到同一散列地址，即
$$
k1≠k2
$$
，而
$$
f(k1)=f(k2)
$$
，这种现象称为冲突（或碰撞，英语：Collision）。具有相同函数值的关键字对该散列函数来说称做 同义词。综上所述，根据散列函数 f(k) 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
- 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
2. 构造散列函数的方法
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。
- 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即
$$
hash(k)=k
$$
或
$$
hash(k)=a \cdot k+b
$$
, 其中 ab 为常数（这种散列函数叫做自身函数）
- 数字分析法：假设关键字是以 r 为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
- 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
- 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
- 除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即
$$
hash(k)=k\,{\bmod {\,}}p
$$
$$
p\leq m
$$
不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对 p 的选择很重要，一般取素数或 m，若 p 选择不好，容易产生冲突。
3. 处理冲突
为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理，而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：
开放寻址法 (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），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。
转载请注明出处