散列表
理想的散列表数据结构只不过是一个包含有关键字的具有固定大小的数组。我们把表的大小记作Tablesize.（最好让表的大小是一个质数）每一个关键字被映射到从0到TableSize-1这个范围中的某个数，并且被放到适当的单元中。这个映射就叫做散列函数，理想情况下它应该运算简单并且应该保证任何两个不同的关键字映射到不同的单元。不过这是不可能的，因为单元的数目是有限的，而关键字实际上是用不完的。
这就是散列的基本想法。剩下的问题则是要选择一个函数，决定当关键字散列到同一个值的时候（称为冲突）应该做什么。
散列冲突
如果当一个元素被插入时另一个元素已经存在（散列值相同），那么就产生一个冲突，这个冲突需要消除。我讲介绍其中最简单的2种方法：分离链接法和开放地址法。
分离链接法
解决冲突的第一种方法通常叫做分离链接法，其做法是将散列到同一个值的所有元素保留到一个表中。为了方法起见，这些表都有表头。也就是数组里存了一个链表，为了以后删除元素方便，每个链表都有一个表头。如下图所示：
分离链接法的缺点是需要指针，由于给新单元分配地址需要时间，一次这就导致算法的速度多少有些慢，同时算法实际上还要求对另一种数据结构的实现。
开放定址法
开放定址散列法是另外一种不同链表解决冲突的方法。在这个方法中，如果有冲突发生，那么就要尝试选择另外的单元，直到找出空的单元为止。更一般的，单元$h_0(X),h_1(X),h_2(X)$等等，相继被试选，其中
$h_i(X)=(Hash(X)+F(i))$ mod TableSize 函数F是冲突解决方法。 一般来说，对开放定址散列算法来说，装填因子应该低于$\lambda$=0.5。接下来介绍3个通常解决冲突的方法。
线性探测法
在线性探测法中，函数F是i的线性函数，典型情形是F(i)=i。这相当于逐个探测每个单元（必要时可以绕回）以查找出一个空单元。 如果表可以有多于一半被填满的话，那么线性探测就不是一个好办法。
平方探测法
平方探测法是消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次函数的探测方法。流行的选择是$F(i)=i^2$
对于线性探测，让元素几乎填满散列表并不是一个好的主意，因此测试表的性能会降低。对于平方探测情况甚至更糟：一旦表被填满超过一半，当表的大小不是质数时甚至在表被填满一半之前，就不能保证一次找到一个空单元了。这是因为最多有表的一半可以用作解决冲突的备选位置。
对于这种情况，我们可以使用再散列,就是建立另外一个大约两倍大的表（并且使用一个相关的新散列函数），扫描这个那个原始散列表，计算每个（未删除的）元素的新散列值并将其插入到新表。
在散列可以用平方探测以多种方法实现。一种做法是只要表满到一半就再散列。另一种极端的方法是只有当插入失败时才再散列。第三种是当表到达某一个装填因子时进行再散列。由于随着装填因子的增加表的性能的确有下降，因此第三种可能是最好的策略。
双散列
对于双散列，一种流行的选择是$F(i)=i * hash(x)$.这个方法如果hash函数选择的不好将会是灾难性的。比如X=99，hash(x) = x mod 9.因此，函数一定不要算得0.
