记录的存储位置 = f(关键字)
散列技术是在存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)
对应关系函数f称为散列函数(哈希函数)
采用三列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表(哈希表)

查找步骤

当存储记录时，通过散列函数计算出记录的散列地址
当查找记录时，通过散列函数计算记录的散列地址，并按此散列地址访问该记录
各记录之间没有任何关系
散列表适合1对1查找，不适合查找范围，也不适合关键字对应多个结果的查找
散列函数通过不同的关键字，计算出了相同地址，称之为冲突

构建散列函数

散列函数原则=计算简单+分布均匀(散列地址)
直接定址法
取关键字的某个线性函数值为散列地址：f(key)=a*key+b
适合查找表小，key比较连续的情况，不常用
数字分析法
适合处理关键字位数比较大的情况
抽取关键字的某几位作为散列地址
平方取中法
平方取中法是将关键字平方之后取中间若干位数字作为散列地址
适合不知道关键字的分布，关键字位数不是很大的情况
折叠法
将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址
除留余数法
f(key) = key mod p(p <= m)
m为表长
这个方法不仅可以对关键字直接取模，也可以通过折叠、平方取中后再取模
p的取值是关键，最好接近m的最小质数
随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址
f(key) = random(key)
random为随机函数，适合关键字长度不等的情况
选取方法时要考虑的因素：
计算散列地址所需时间
关键字长度
散列表大小
关键字分布情况
记录查找频率

处理散列冲突的方法

开放定址法
一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
1.线性探测法
fi(key) = (f(key)+di) mod m
其中di = 1,2,…,m-1
意思是，散列函数计算的地址已经被其他记录占据，就将散列函数计算的地址每次次加1到m-1的一个数,
再mod表长，将每次计算的结果当做新地址去探测有没有记录，如果没有就将该地址做为记录的地址
2.二次探测法
修改一次探测法di的取值
另di = 1^2,-1^2,2^2,-2^2,q^2,-q^2,其中q<=m/2
3.随机探测法
对di采用随机函数计算得到
再散列函数法
fi(key) = RHi(key)(i=1,2,3,…k)
就是用第一个散列函数计算的地址发生冲突就换第二个散列函数，如果第二个也发生冲突，则换第三个，以此类推
链地址法
地址处不存放单一记录，而是存放记录的链表，记录1指向记录2，计算得到地址相同，就继续指下去
公共溢出区法
不发生冲突的关键字放在基本表，将发生冲突的记录依次存放在溢出表，
查找时基本表找不到时就去查溢出表，溢出表找不到再宣告失败