-散列表的基本内容
-散列函数的构造方法
散列表的基本概念
散列函数
一个把查找表中关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。（这里的地址可以是数组下标，索引，或内存地址等）
散列函数可能会把两个或者两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的办法。
散列表
散列表是根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
散列函数的构造方法
在构造散列函数时，必须注意以下几点：
1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
2）散列函数计算出来的地址应该能等概率，均匀地分布在整个地址空间，从而减少冲突的发生。
3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。
常用的散列函数
1.直接定址法
直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a*key+b。在这个函数式中，a和b是常数。这种方法计算最简单，并且不会产生冲突。它适合关键字的分布基本连续的情况，如果关键字分布不连续，空位较多，将造成存储空间的浪费。
2.除留余数法
这是一种最简单，最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用下列公式把关键字转换成散列地址。散列函数为H(key)=key%p。
除留余数法的关键在于选好p，使得每一个关键字在通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减小冲突的可能性。
3.数字分析法
设关键字是r进制数(如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有几种数码经常出现，则应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合。如果更换了关键字，就需要重新构造新的散列函数。
4.平方取中法
顾名思义，取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，使得散列地址分布比较均匀。适合于关键字的每一位取值都不够均匀或均小于散列地址所需的位数的情况。
5.折叠法
将关键字分割位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址。
在不同的情况下，不同的散列函数会发挥出不同的性能，因此不能笼统地说哪种散列函数最好。实际选择中，采用何种散列函数的方法取决于关键字集合的情况，但目标是为了使散列产生冲突的可能性尽量地降低。
