1、散列表的基本概念 散列函数：一个吧查找表中的关键字映射成该关键字对应的地址的函数，纪为Hash(key)=Addr。 哈希表可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。 散列表：根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址之间的直接映射关系。 理想状态下查找的时间复杂度为O(1),即与表中元素个数无关 2、散列函数的构造方法 （1）散列函数必须包含全部需要存储的关键字，而值域的范围依赖于散列表的大小或地址 （2）散列函数计算出来的地址应该能等概率、均匀分布在整个地址空间吧，从而减少冲突的发送 （3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。 2.1直接定址法 直接取关键字的某个线性函数值为散列地址，散列函数为： 
2.2除留余数法 
2.3数字分析法 
2.4平方取中法 
2.5、折叠法 
3、处理冲突的方法 任何设计出来的散列函数都把不可能绝对避免冲突，为此吗，必须考虑在发生冲突的时候应如何进行处理，即为产生冲突的关键字寻址下一个“空的”Hash地址。 3.1开放定址法 
3.2拉链法 对弈不同关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性表中，这个线性表由其散列地址唯一标识。 
4、散列查找及性能分析 散列表的查找过程与构造散列表的过程基本一致。对于给定的关键字key，根据散列函数可以计算出其散列地址，执行步骤如下：
