散列表也叫哈希表，在前面的各种数据结构中(数组，链表，树等),记录在结构中的相对位置是随机的，和记录的关键字不存在确定的关系。在顺序结构中，顺序查找，比较的结果是'='或者'!=',在二分查找，二叉排序树比较的关系是'>','=‘，’<‘,查找的效率依赖于查找过程中比较的次数。 什么样的方法能使得理想情况下不需要进行任何比较，通过一次存储就能得到所查的记录。答案就是记录存储位置和关键字之间的对应关系。
我们记录了存储位置和关键字的对应关系h,因此在查找的过程中，只要根据对应关系h找到给定值k的像h(k),如果结构中存在关建字和k相等的记录，那么肯定是存储在h(k)的位置上，就像上图k1..k5的一样，我们称这个对应关系h为散列函数或者是哈希函数。
从上面的例子可以看出:
1.散列函数是一个映像，因此设定散列函数可以非常灵活。
2.从图中可以看出，k2 != k5 ,但是h(k2)===h(k5),这就是散列冲突。
我们看当前例子，关键字 John Smith !=Sandra Dee,但是通过散列函数之后h(John Smith)===h(Sandra Dee),他们的位置都在散列表01这个位置，但是这个位置只能存储一个记录，那多出来的记录存放在哪里?
正因为散列函数是一个映像，我们在构造散列函数的时候，只能去分析关键字的特性，选择一个恰当的散列函数来避免冲突的发生。一般情况下，冲突只能尽可能的减少，而不能完全避免。
先来看看什么是好的散列函数。如果对于关键字集合中任意一个，经过散列函数映射到地址集合中任何一个位置的概率都是相等的，就可以称为均匀散列函数。
1.直接定址法
取关键字或者关键字的某个线性函数值为哈希地址。
h(key)=key或者h(key)=a*key+b a,b为常量。比如说做一个地区年龄段的人数统计，我们就可以把年龄1-100作为关键字，现在你要查38岁的人口数时只需要h(38)=？？？。
2.数字分析法
要通过具体的数字分析，找出关键字集合的特点和关系，通过这组关系构造一个散列函数。
3.平方取中法
取关键字平方后的中间几位为哈希地址，因为一般情况下，选定哈希函数时并不一定知道关键字的全部情况，取哪几位也不一定合适，而一个平方后的中间几位数和数的每一位都有关，由此使随机分布的关键字得到的哈希地址也是随机的。
4.折叠法
将关键字分割成位数相同的几部分，然后取这几部分的叠加和，也就是舍去它的进位，作为他的哈希地址。
5.除留余数法 取关键字被某个不大于散列表表长m的数(暂且称之为p)除后所得余数为哈希地址。
h(key)=key MOD p, p<=m以上都偏于理论，具体的使用需要视情况而定，通常，考虑的因素有以下几点
1.计算散列函数所需的时间
2.关键字的长度
3.哈希表的大小
4.关键字的分布情况
5.记录查找的频率
之前说过，散列函数可以减少冲突,但是不能避免，这时候我们就需要处理冲突。
1.开放寻址法
简单的来说，下图中当前哈希表的长度是8，现在已填入关键字1，9，3，4，5的记录，假如当前我们需要再填入关键字10这条记录。通过散列函数得出h(3)===h(10),但是此时哈希地址2已被3占领。现在我们咋么处理？
线性探测再散列得到下一个地址3，发现3也被占领，再求下一个地址4，还被占领,直到5这个位置时，处理冲突过程结束，把当前h(10)记录在地址为5的位置即可。也可以使用二次探测再散列或者伪随机再散列都是属于开放寻址法。
2.再散列法
即在同义词产生地址冲突时计算另一个散列函数的地址，直到冲突不再发生，这种方法毋庸置疑，增加了计算的时间。
3.链地址法
将所有关键字为同义词的记录存储在同一个线性链表中。初始状态是一个空指针。凡是通过关键字计算出地址一样的记录都插入到当前位置的链表中，在链表中插入的位置可以是表头，表尾，或者表中，以保持同义词在同一个线性表中按关键字有序。
4.建立一个公共溢出区
假设散列函数的值域为[0,m-1],则设置向量HashTable[0,m-1]为基本表，每一个分量存储一个记录，另外设置向量OverTable[0,v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表中。
