在数组中根据数组的下标查找一个元素只需要O(1)的时间，散列表是类似于数组的动态集合的数据结构，可以根据元素的关键字在一个表中快速地操作元素。

当散列表的关键字比较小，可以取自 {0, 1, ..., m-1} 一个有限的小范围内时，可以使用一个大小为 m 的数组 T 表示这个动态集合，这个数组称为直接寻址表，动态集合中的元素位于 T[key]中。

当这个动态集合变得很大，使用数组保存这些数据将变得不可能。我们可以使用一个比较小的数组 T —— 散列表，使用一个散列函数将关键字 k 转换为数组 T 的一个位置——槽，即将关键字映射到槽中，散列函数缩小了数组下标的范围，即减小了数组的大小，同时对这个大的动态集合的操作也会象普通数组一个变得快捷方便。

由于将一个数量比数组 T 大得多的动态集合来说，要将全部元素保存到数组中，散列函数计算出的下标值一定会有重复的值，即多个关键字可能会映射到同一个槽中，这种情形称为冲突（collision）。解决冲突的方法有多种，一种称为链接法，另一种称为开放寻址法。

链接法中，把散列到同一槽中的所有元素都放在一个链表中，每个槽中有一个指针，指向存储所有散列到这个单元的链表的表头，如果不存在这样的元素，则相应槽的指针为 null。要查找一个元素，根据元素的关键字 k，使用散列函数 h(k) 计算出槽的位置，然后遍历这个槽指向的链表。向散列表中插入元素和删除元素的操作也很简单，首先计算出散列位置，剩下的就是对链表进行操作。

对于一个能存放 n 个元素、具有 m 个槽位的散列表 T，一个链表的平均元素数为 n/m，这个值也叫做 T 的装载因子α。最坏情况下，所有 n 个元素都放散列到同一槽中，那么查找时间就是 O(n)，即长度为 n 的链表的查找时间，所以链接法的平均性能依赖于散列函数。我们可以假定 n 个元素散列到 m 个槽位上是平均的，即每个槽位上大约有 n/m 个元素，称这个假设为简单均匀散列。简单均匀散列的查找平均时间为 O(1+α)。

散列表