1 直接寻址表
直接寻址表是数组的扩展，应用范围是全域U不是很大。它和散列表的区别是不用处理冲突，因为不会出现冲突。

2 散列表
当全域U很大的时候，由于内存的限制，直接寻址表出现问题，因此可以用散列表解决。对于直接寻址表，具有关键字k的元素在槽k中，而该元素则在散列表的h(k)处，其中，h(k)是散列函数，这个函数将全域U映射到散列表T的[0...m-1]的槽位上。对于两个关键字映射到同一个槽位上的情况，我们称之为碰撞。
解决碰撞有：

• 链接法解决碰撞
• 开放寻址法

1.1 链接法
链接法解决碰撞的思想很简单，当有多个元素同时被映射到散列表T的同一个槽位的时候，就使用链表的方式链接到该槽位上。这样，在某些发生冲突的槽位后面形成一条长度随机不等的链表。
定义两个概念：

• 装载因子：给定一个能存放n个元素的、具有m个槽位的散列表T，装载因子定义为n/m。含义是一个链中平均存放的元素数。
• 简单一致散列：任何元素散列到m个槽中每一个的可能性是相同的，且与其他元素已被散列到什么位置独立无关。

定理：对一个用连接技术来解决碰撞的散列表，在简单一致散列的假设下，一次不成功查找的期望时间为θ(1+α)，这个时间包含计算h(k)的时间。
证明：由于简单一致散列，因此元素被映射到第i个槽的概率为1/m，假设槽i的链表有ni个元素，则期望时间为1+Σni/m = 1+(Σni)/m = 1 + α，证毕。
定理：在简单一致散列的假设下，对于用链接技术解决碰撞的散列表，平均情况下一次成功的查找需要θ(1+α)时间。
证明见书。

1.2 散列函数
好的散列函数应（近似的）满足简单一致散列的假设，但很难去检验，因为人们很少知道关键字所符合的概率分布。
1.2.1 将关键字解释为自然数
比如：一个字符串关键字可以被解释为按适当的基数记号表示的整数。如pt表示为(112 * 128) + 116 = 14452。这将字符串看成是以128为基数的整数。
1.2.2 除法散列法
h(k) = k mod m，通过取k除以m的余数来将关键字k映射到m个槽的某一个中去。
注意除数m的选择，m不应该是2的幂，因为如果m = 2^p，则h(k)就是k的p个最低位数字。并且，当k是一个按基数2^p解释的字符串时，选m = 2^p - 1可能是个比较糟糕的选择，因为将k的各字符进行排列并不会改变h(k)的值，这个证明比较简单，略。一般选取m为与2的幂不太接近的素数。
1.2.3 乘法散列法
h(k) = ⌊m(kA - ⌊kA⌋)⌋。其中A为(0, 1)之间的常数。m一般选为2的某个幂次。Knuth认为A ≅(√5 - 1)/2 = 0.6180339887…是一个比较理想的值。

1.3 开放寻址法
在开放寻址法中，所有的元素都存放在散列表中，和连接法处理冲突时采用连接形式不同，开放寻址法的散列表每个表项或包含动态集合的一个元素，或包含NIL。
在开放寻址法中，当要插入一个元素时，可以连续地探查散列表的各项，直到找到一个空槽来放置待插入的关键字为止。
1.3.1 线性探查
h(k, i) = (h'(k) + i) mod m, i = 0, 1, ... ,m - 1
在线性探查方法中，初始探查位置确定了整个序列，因此只有m种不同的探查序列。且它存在一次群集现象。
1.3.2 二次探查
h(k, i) = (h'(k) + c * i + d * i^2) mod m
其中c和d为辅助常数。初始探查位置为T[h'(k)]，后续的探查位置要在此基础上加上一个偏移量，该偏移量以二次的方式依赖于探查号i。它比线性探查好的多。但是如果两个关键字初始探查位置相同，那么他们的探查序列也是相同的。因此它存在程度较一次群集轻的二次群集现象。
1.3.3 双重散列
h(k, i) = (f(k) + i * g(k)) mod m
其中f(k)和g(k)为辅助散列函数。与线性探查和二次探查不同的是，这里的探查序列以两种方式依赖于关键字k。为能查找整个散列表，值g(k)要与m互素。可以取m为2的幂，并设计g(k)为总产生奇数。或者取m为素数，设计g(k)总产生比m小的正整数。比如：可以取m为素数，并取f(k) = k mod m, g(k) = 1 + (k mod n) 其中n略小于m（比如为m - 1）。双重散列法用了θ(m^2)种探查序列。