散列表（Hash）概述

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置（f(key)）。查找时，根据这个确定的对应关系找到给定值key的映射f(key)。这里的对应关系f称为散列函数。

散列技术既是一种存储方法，也是一种查找方法。

 

散列函数的构造方法

散了函数的构造原则：1.计算简单，2.散列地址分布均匀

构造方法：

1.直接定址法：需要预先知道关键字的分布情况，适合查找表较小且连续的情况。

f(key)=a*key+b        直接取关键字的么讴歌线性函数值为散列地址。

2.数字分析法：通常适合处理关键字位数比较大的情况，也要事先知道关键字的分布和关键字若干位分布较均匀。

抽取关键字的一部分来计算散列存储位置的方法。

3.平方取中法：适合不知道关键字的分布情况，而位数又不是很大的情况。

将关键字平方然后取其中的数位作为散列函数。

4.折叠法：适合不知道关键字的分布，且关键字位数较多的情况。

将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

5.除留余数法：

f(key)=key mod p (p<<m)

6.随机数法：关键字唱的不等时，采用这个方法交合适。

f(key)=random(key)

构造散列函数需要考虑的因素：

1.计算散列地址的时间

2.关键字的长度

3.散列表的大小

4.关键字的分布情况

5.记录查找的频率

 

散列函数冲突处理方法

1.开发定址法：一旦发生了冲突，就去寻找下一个空散列地址，只要列表足够大，空散列地址总能找到，并记录存入，这种方法也叫线性探测法。

f'(key)=(f(key)+d') mod m (d'=1,2,...,m-1)

2.再散列函数法

f'(key)=RH'(key)  RH'就是不同的散列函数

3.链接地址法

4.公共溢出区法：为所有冲突的关键字建立了一个公共的溢出区来存放。

更加详细的讲解一定要看http://www.partow.net/programming/hashfunctions/以及一个中文的翻译http://blog.csdn.net/wwwsq/article/details/1526595