概念
散列表的实现常常叫做散列（hashing）。散列是一种用于以常数平均时间执行插入、删除和查找的技术。
散列函数：每个关键字被映射到从0到TableSize-1这个范围中的某个数，并且被放到适合的单元中。这个映射就叫做散列函数（hash function）。
冲突：当两个关键字散列到同一值的时候，称为冲突。
散列函数
好的办法通常是保证表的大小是素数。
如果当一个元素被插入时另一个元素已经存在（散列值相同），那么就产生一个冲突，这个冲突需要消除。解决这种冲突的方法有几种，最简单的两种：分离链接法和开放定址法。
分离链表法
将散列到同一个值的所有元素保留到一个表中。
开放定址法
在开放定址散列算法系统中，如果有冲突发生，那么就要尝试选择另外的单元，直到找出空的单元为止。更一般地，单元h0(X),h1(X),h2(X),等等，相继被试选，其中hi(X) = (Hash(X) + F(i)) mod TableSize,且F(0) = 0。
函数F是冲突解决方法。
因为所有的数据都要置入表内，所以开放定址散列法所需要的表要比分离链接散列用表大。一般来说，对开放定址散列算法来说，装填因子应该低于λ = 0.5
- 线性探测法
在线性探测法中，函数F是i的线性函数，典型情形是F(i) = i。
只要表足够大，总能够找到一个自由单元，但是如此花费的时间是相当多的。更糟的是，即使表相对较空，这样占据的单元也会形成一些区块，其结果称为一次聚集，于是，散列到区块中的任何关键字都需要多次试选单元才能够解决冲突，然后该关键字才能被添加到相应的区块中。 - 平方探测法
平方探测法师消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次函数的探测方法。流行的选择是F(i) = i2。
虽然平方探测排除了一次聚集，但是散列到同一位置上的那些元素将探测相同的备选单元。这叫做二次聚集。 - 双散列
对于双散列，一种流行的选择是F(i)=i·hash2(x).
再散列
如果散列表的元素填得太满，那么操作的运行时间开始消耗过长，且Insert操作可能失败。一种解决方式是建立另外一种大约两倍大的表（而且使用一个相关的新散列函数。扫描整个原始散列表，计算每个（未删除）元素的新散列值并将其插入到新表中。整个操作就叫做再散列。虽然这是一种非常昂贵的操作；其运行时间为O(N)，因为有N个元素要再散列而表的大小约为2N。
再散列可以用平方探测以多种方式实现。
- 一种是只要表满到一半就再散列
- 另一种极端的方法是只有当插入失败时才再散列
- 第三种方法即途中策略：当表到达某一个装填因子时进行再散列。由于随着装填因子的增加表的性能的确有下降，因此，以好的截止手段实现的第三种策略，可能是最好的策略。
