散列表的实现常常叫做数列（hashing）。散列是一种以常数平均时间执行插入、删除和查栈的技术。但是，哪些需要元素间任何排序信息的操作将不会得到有效的支持。因此，诸如 FindMin、 FinMax 以及线性时间将排过序的整个表进行打印的操作都是散列所不支持的。
理想的散列表数据结构只不过是一个含有关键字的具有固定大小的数组。典型情况下，一个关键字就是一个带有相关值的字符串。我们把表的大小记作 TableSize，并将其理解为散列数据结构的一部分而不仅仅是浮动于全局的某个变量。通常的习惯是让表从 0 到 TableSize-1 变化。
将每个关键字映射到从 0 到 TableSize-1 这个范围中的某个数，并且放到适当的单元中。这个映射就叫做散列函数（hash function），理想情况下它应该运算简单并且应该保证任何两个不同的关键字映射到不同的单元。不过，这是不可能的，因为单元的数目是有限的，而关键字实际上是无穷无尽的。因此，我们寻找一个散列函数，该函数要在单元之间均匀地分配关键字。
这就是散列的基本想法。剩下的问题则是要选择一个函数，决定当两个关键字散列到同一个值的时候哦（称为冲突（collision））应该做什么以及如何确定散列表的大小。
网友评论