本博文源于浙江大学《数据结构》。散列（Hashing）是一种重要的查找方法。它的基本思想是：以数据对象的关键字key为自变量，通过一个确定的函数关系h，计算出对应的函数值h(key),把这个值解释为数据对象的存储地址，并按此存放，即“存储位置=h(key)”。

在查找数据对象时，由函数h对给定值key计算出地址，将key与该地址单元中数据对象关键字进行比较，确定查找是否成功。因此，散列法又称为“关键字-地址转换法”。散列方法中使用的计算函数称为散列函数（也称哈希函数），按这个思想构造的表称为散列表，所以它是一种存储方法。

一般情况下，设散列表空间大小为m，填入表中的元素个数是n,则称α=n/m为散列表的装填因子，例如大小为17，元素为11，装填因子为0.65.实用时，常见散列表大小设计使得α=0.5~0.8为宜。

映射到同一散列地址上的关键字称为同义词

一个“好”的散列函数一般应考虑下列两个因素：

这类函数计算简单，分布均匀，不会产生冲突，但要求地址集合与关键词集合大小相同，因此，对于较大的关键词集合不适用。所以在现实应用中并不常用

现实应用中比较常用的方法是除留取余法。假设散列表长为TableSize(TableSize的选取，通常由关键词集合的大小n和允许最大装填因子α决定，一般将TableSize取为n/α),选择一个正整数p