许多应用都需要一种动态集合结构，至少要支持INSERT、SEARCH和DELETE字典操作，散列表（hash table）是实现字典操作的一种有效数据结构。可以简单地理解散列表是存储键值对（key-value）的数据结构。
其C语言代码实现在代码链接，用到了uthash的库。
0 直接寻址表
散列表是普通数组概念的推广，由于普通数组可以直接寻址，使得能在O(1)时间内访问数组的任意位置。当表中的所有的键都是较小的整数时（或者集中在一个较小的范围内），我们可以直接使用数组来实现直接寻址表，记为T[0..m-1]。其中每个位置，或称为槽（slot），对应全域中的一个关键字。其基本的操作伪代码如下：
1 | DIRECT-ADDRESS-SEARCH(T, k) |
1 散列表
直接寻址的缺点是非常明显的：如果全域很大，则可能一台标准计算机的可用内存都不够用，还有实际存储的关键字集合相对全域可能很小，使得分配的空间绝大多数都被浪费掉。
当存储在字典中的关键字集合比所有可能的关键字全域要小许多时，散列表需要的存储空间比直接寻址表少很多。散列表中查找一个元素的优势依然得到保持，只需要O(1)时间。问题是这是针对平均情况时间的，而对直接寻址而言，它适用于最坏情况时间。
存在一个问题：两个关键字可能映射到一个槽中，我们称这种情况为冲突。一方面我们可以通过精心设计的散列函数来尽可能地减少冲突的次数；另一方面仍需要有解决可能出现冲突的方法。下面我们就着重介绍这两部分。
1.1 散列函数
好的散列函数应（近似地）满足简单均匀散列假设：每个关键字都被等可能地散列到槽位中的任何一个，并与其他关键字散列到哪个槽位无关。遗憾的是，一般无法检查这一条件是否成立。本节将介绍由《算法导论》书本介绍的三种散列方法，其中两种本质上属于启发式方法，而第三种方法（全域散列）则利用了随机技术来提供可证明的良好性能。
1.1.1 除法散列法
通过取关键字k处于槽数m的余数，将关键字映射到m个槽中的某一个，即散列函数为：
1 | h(k) = k mod m |
除法散列法最重要的就是m的选择，选择一个不太接近2的整数幂的素数，常常是m的一个较好的选择。
1.1.2 乘法散列法
构造散列函数的乘法散列法包含两个步骤：
- 用关键字k乘以常数A(0<A<1)，并提取A的小数部分kA；
- 用m乘以这个值，再向下取整。
散列函数为：
1 | h(k) = | m(kA mod 1) | |
乘法散列法对m的选择不是特别关键，但是A的选值会影响效率，某些文献认为黄金比例0.618是一个比较理想的值。
1.1.3 全域散列法
如果让一个恶意的对手来针对某个特定的散列函数选择要散列的关键字，那么他会将n个关键字全部散列到同一个槽里。为了避免这种情况，唯一有效的改进方法是随机地选择散列函数，使之独立与要存储的关键字。这种方法称为全域散列(universal hashing)。全域散列在执行开始时，就从一组精心设计的函数中，随机地选择一个作为散列函数。因为随机地选择散列函数，算法在每一次执行时都会有所不同，甚至相同的输入都会如此（不明白如果插入时和寻找时散列函数不同是怎么做到准确查找的，难道是还得记录已入表的k值对应的函数？）。这样就可以确保对于任何输入，算法都具有较好的平均情况性能。
1.1.4 完全散列
如果某种散列技术可以在查找时，最坏情况内存访问次数为O(1)的话，则称其为完全散列（perfect hashing）。当关键字集合是静态的时，这种最坏情况的性能是可以达到的。所谓静态就是指一旦各关键字存入表中后，关键字集合就不再变化了。
我们可以用一种两级的散列方案来实现完全散列，其中每级上采用的都是全域散列。如下图：
首先第一级使用全域散列把元素散列到各个槽中，这与其它的散列表没什么不一样。但在处理碰撞时，并不像链接法（碰撞处理方法）一样使用链表，而是对在同一个槽中的元素再进行一次散列操作。也就是说，每一个（有元素的）槽里都维护着一张散列表，该表的大小为槽中元素数的平方，例如，有3个元素在同一个槽的话，该槽的二级散列表大小为9。不仅如此，每个槽都使用不同的散列函数，在全域散列函数簇h(k) = ((a*k+b) mod p) mod m中选择不同的a值和b值，但所有槽共用一个p值如101。每个槽中的（二级）散列函数可以保证不发生碰撞情况。
可 以证明，当二级散列表的大小为槽内元素数的平方时，从全域散列函数簇中随机选择一个散列函数，会产生碰撞的概率小于1/2。所以每个槽随机选择散列函数后，如果产生了碰撞，可以再次尝试选择其它散列函数，但这种尝试的次数是非常少的。
虽然二级散列表的大小要求是槽内元素数的平方，看起来很大，但可以证明，当散列表的槽的数量和元素数量相同时(m=n)，所有的二级散列表的大小的总量的期望值会小于2*n，即Ө(n)。
1.2 解冲突
1.2.1 链接法
链接法就是把散列到同一槽中的所有元素都放到一个链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。如下：
1.2.2 开放寻址法
开放寻址法的思路是：在产生冲突的情况下，在hashtable中寻找其他空闲的槽位插入；当然，如何寻找其他空闲的槽位，我们有几种方法，包括：线性探查、二次探查、双重散列、随机散列。
从开放寻址法的散列表中删除操作元素比较困难。在必须删除关键字的应用中，更常见的做法是采用链接法来解决冲突。
1.2.2.1 线性探查
给定一个普通的散列函数h’:U–>{0,1,…,m-1}，称为辅助散列函数，线性探查方法采用的散列函数为：
1 | h(k,i) = (h'(k) + i) mod m, i = 0,1,2...m-1 |
给定一个关键字k，首先探查槽T[h’(k)],即由辅助三列函数所给出的槽位。再探测T[h’(k)+1]，依次类推，直到槽T[m-1]。然后，又绕到槽T[0],T[1],…,直到最后探测到槽T[h’(k)-1]。
线性探测方法比较容易实现，但它存在着一个问题，称为一次群集。随着连续被占用的槽不断增加，平均查找时间也随之不断增加。集群现象很容易出现，这是因为当一个空槽前有i个满的槽时，该空槽下一个将被占用的概率是(i+1)/m。连续被占用的槽就会变得越来越长，因而平均查询时间也会越来越大。采用例子进行说明线性探测过程，已知一组关键字为(26，36，41，38，44，15，68，12，6，51)，用除法散列构造散列函数，初始情况如下图所示：
1.2.2.2 二次探查
二次探查采用如下形式的散列函数
1 | h(k,i)=(h'(k)+c₁i+c₂i²) mod m , i = 0,1,...,m-1 |
其中h’是一个辅助散列函数，c₁和c₂为正的辅助常数，i=0,1,…m-1。初始的探查位置为T[h’(k)]，后续的探查位置要加上一个偏移量，该偏移量以二次的方式依赖于探查序号i。这种探查方法的效果要比线性探查好很多，但是，为了能够充分利用散列表，c₁，c₂和m的值要受到限制。此外，如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的。这一性质可导致一种轻度的群集，称为二次群集。
1.2.2.3 双重散列
双重散列(double hashing)是用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择队列的许多特性。双重散列采用如下形式的散列函数:
1 | h(k,i)=(h₁(k)+ih₂(k)) mod m, i = 0,1,...,m-1 |
其中h₁和h₂均为辅助散列函数。初始探查位置为T[h₁(k)]，后续的探查位置是前一个位置加上偏移量h₂(k)模m。因此，不像线性探查或二次探查，这里的探查序列以两种不同方式依赖于关键字k，因为初始探查位置、偏移量或者两则都可能发生变化。下图给出了一个使用双重散列法进行插入的例子。
上图说明：双重散列法的插入。此处，散列表的大小为13，h₁(k)=k mod13，h₂(k)＝1+(k mod 11)。以元素14为例：因为h₁(14)=(14 mod13)=1，槽1已被79占用，–》h₂(14)＝1+(14 mod 11)=4，则h(14,1)=h₁(14)+h₂(14)=1+4=5,槽5已被98占用，–》h(14,2)=h₁(14)+2h₂(14)=1+24=9，槽9空闲，则插入到槽9中；所以在探查了槽1和槽5，并发现它们被占用后，关键字14插入了槽9中。
