散列
散列表的实现常常叫作散列。散列是一种用于以常数平均时间执行插入、删除和查找的技术。但是，那些需要元素间任何排序信息的树操作将不会得到有效的支持。因此诸如 findMin、findMax 以及以线性时间将排过序的整个表进行打印的操作都是散列所不支持的。
理想的散列表数据结构只不过是一个包含一些项(item)的具有固定大小的数组。通常查找是对项的某个部分(即数据域)进行的。这部分就叫作关键字(key)。
每个关键字被映射到从 0 到 TableSize - 1 这个范围中的某个数，并且被放到适当的单元中。这个映射就叫作散列函数，理想情况下它应该计算起来简单，并且应该保证任何两个不同的关键字映射到不同的单元。不过这是不可能的，因为单元的数目是有限的，而关键字实际上是用不完的。因此，如下图完美情况的一个典型。这个列子中，john 散列到 3，phil 散列到 4，dave 散列到 6，mary 散列到 7。
这就是散列的基本想法。剩下的问题就是要选择一个函数，决定当两个关键字散列到同一个值的时候(这叫作冲突)应该做什么以及如何确定散列表的大小。
散列函数
如果输入的关键字是整数，则一般合理的方法就是直接返回 Key mod Tablesize，除非 Key 碰巧具有某些不合乎需要的性质。在这种情况下，散列函数的选择需要仔细地考虑。
例如，若表的大小是 10 而关键字都是以 0 为个位，则此时上述标准的散列函数就是一个不好的选择。其原因在后面写到，而为了避免上面那样的情况，好的办法通常是保证表的大小是素数。当输入的关键字是随机整数时，散列函数不仅计算起来简单而且关键字的分配也很均匀。
如果当一个元素被插入时与一个已经插入的元素散列到相同的值，那么就产生一个冲突，这个冲突需要消除。解决这种冲突的方法有几种，最简单的两种：分离链接法和开放定址法。
分离链接法
解决冲突的第一种方法通常叫作分离链接法，其做法是将散列到同一个值的所有元素保留到一个表中。我们可以使用标准表的实现方法。如果空间很紧，则可取的方法是避免使用它们(因为这些表是双向链接的并且浪费空间)。
为执行一次查找，我们使用散列函数来确定究竟遍历哪个链表。然后再被确定的链表中执行一次查找。为执行 insert，检查相应的链表看看该元素是否已经处在适当的位置(如果允许插入重复元素，那么通常要留出一个额外的域，这个域当出现匹配事件时增 1)。如果这个元素是一个新元素，那么它将被插入到链表的前端，这不仅因为方便，还因为常常发生这样的事实：新近插入的元素最有可能不久又被访问。
不用链表的散列表
分离链接散列算法的缺点是使用一些链表。一般来说，对于不使用分离链接的散列表来说，其装填因子应该低于λ=0.5。我们把这样的表叫作探测散列表。有三种通常的冲突解决方案。
线性探测法
在线性探测法中，函数f 是 i 的线性函数，典型情形是f(i)=i。这相当于相继探测逐个单元(必要时可以回绕)以查找出一个空单元。如下图 显示使用与前面相同的散列函数将各个关键字|89，18，49，58，69|插入到一个散列表中的情况，而此时的冲突解决方法就是 f(i)=i。
第一个冲突的插入关键字 49 时产生；它被放入下一个空闲地址，即地址 0，该地址是开放的。关键字 58 先与 18 冲突，再与 89 冲突，然后又和 49 冲突，试选三次之后才找到一个空单元。对 69 的冲突用类似的方法处理。只要表足够大，总能够找到一个自由单元，但是如此花费的时间是相当多的。更糟的是，即使表相对较空，这样占据的单元也会开始形成一些区块，其结构称为一次聚集，就是说，散列到区块中的任何关键字都需要多次试选单元才能够解决冲突，然后该关键字被添加到相应的区块中。
平方探测法
平方探测是消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次的探测方法。
对于线性探测，让散列表几乎填满元素并不是一个办法，因为此时表的性能会降低。对于平方探测情况甚至更糟：一旦表被填充超过一半，当表的大小不是素数时甚至在表被填充一半之前，就不能保证一次找到空的单元了。这是因为最多有表的一般可以用作解决冲突的备选位置。
定理，如果使用平方探测，且表的大小是素数，那么当表至少有一般是空的时候，总能够插入一个新的元素。
再散列
对于使用平方探测的开放定址散列法，如果散列表填得太满，那么操作的运行时间将开始消耗过长，且插入操作可能失败。这可能发生在有太多的移动和插入混合的场合。此时，一种解决方法是建立另外一个大约两倍大的表(而且使用一个相关的新散列函数)，扫描整个原始散列表，计算每个(未删除的)元素的新散列值并将其插入到新表中。
再散列可以用平方探测以多种方法实现。一种做法是只要表满到一半就再散列。另一种极端的方法是只有当插入失败时才再散列。第三种方法即途中策略：当散列表达到某一个装填因子时进行再散列。由于随着装填因子的增长散列表的性能确实下降，因此，以好的截止手段实现的第三种策略，可能是最好的策略。
小结
散列表可以用来以常数平均时间实现 insert 和查找操作。当使用散列表时注意诸如装填因子这样的细节是特别重要的，否则时间界将不再有效。当关键字不是短的串或整数时，仔细选择散列函数也是很重要的。
对于分离链接散列法，虽然填装因子不很大时性能并不明显降低，但装填因子还是应该接近于 1。对于探测散列算法，除非完全不可避免，否则装填因子不应该超过 0.5。如果使用线性探测，那么性能随着装填因子接近于 1 将急速下降。再散列运算可以通过使散列表增长(和收缩)来实现，这样将会保持合理的装填因子。对于空间紧缺并且不可能声明巨大散列表的情况，这是很重要的。
二叉查找树也可以用来实现 insert 和 contains 运算。虽然平均时间界为 O(logN)，但是二叉查找树也支持那些需要序从而功能更强大的例程。使用散列表不可能找出最小元素。除非准确知道一个字符串，否则散列表也不可能有效地查找它。二叉查找树可以迅速找到在一定范围内的所有项；散列表是做不到的。此外，O(logN)这个时间界也不一定比 O(1)大很多，这特别是因为使用查找树不需要乘法和除法。
另一方面，散列的最坏情况一般来自于实现的错误，而有序的输入却可能使二叉树运行得很差。平衡二叉树实现的代价相当高，因此，如果不需要有序的信息以及对出入是否被排序存有怀疑，那么就应该选择散列这种数据结构。
散列表用途：编译器使用散列表跟踪源代码中声明的变量、对任何带有实际名字而非数字的节点的图论问题、在线拼写检验程序、现实缓存(互联网浏览器的缓存、硬件中、计算机内存、路由器的硬件实现)。
