散列函数：一个把查找表中的关键字映射称对应的地址的函数，记为Hash(key)=Addr(这里的地址也可以看作数组下标，索引或内存地址等)
散列函数把两个或两个以上的不同关键字映射到同一地址，称为“冲突”。（key1!=key2,但是f(key1)=f(key2)）
散列表：根据设定的散列函数和所选中的处理冲突的方法，将一组关键字映像到一个有限的、地址连续的地址集（区间）上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“散列表”
构造散列函数的方法
对数字的关键字有一下方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法
若关键字是非数字的，则需先对其进行数字化处理
1.直接定址法(仅适用于地址集合的大小==关键字集合的大小)
H(key)=a*key+b
2.数字分析法(仅适合已知关键字的集合)
假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,...,us)，分析关键字集合中的全体，并从中提取分布均匀的若干位（或他们的组合）组成地址
3.平方取中法（适用于关键字的每一位取值都不够均匀的情况）
以关键字的平防止的中间几位作为存储地址。求“关键字的平方值”的目的是为了扩大差别，同时平方值的中间各位又能受到整个关键字中各位的影响
4.折叠法（适用于关键字的数字位比较多的情况）
将关键字分割成若干部分，然后取他们的叠加和为散列地址（又分移位叠加和间界叠加）
5.除留余数法
H(key)=key%p
其中，p是不大于m但最接近或等于m的质数
为什么要对p进行限制？因为若是没有这个限制，冲突会比较多
处理冲突的实际含义就是为产生冲突的地址寻找下一个散列地址
1.开放定址法
H0=H(key)
Hi=(H(key)+di) MOD m
具体细分有4种方法
1.线性探测再散列
Di=c*i（i为查找的次数，c=1）
2.平方探测再散列
Di=12，-12，22，-22，...
3.随机探测再散列
Di是一组伪随机数列
4.双散列
Di=i*H2(key)
聚集现象：当我们使用处理冲突的方法后，占用了另一个本应存放在那里的元素的地址，就会产生聚集现象
2.链地址法
在所有本应存放数据的地方改换成指针，指向一个链表，链表中存放各同义词
散列表的查找
对于给定值K，计算散列地址i=H(K)
若r[i]==NULL,则查找不成功
若r[i].key=K,则查找成功
否则“求下一地址Hi”
直至r[hi]==NULL(查找不成功)
或r[Hi].key=K(查找成功)为止
决定散列表查找的ASL的因素
1.选用的散列函数（一般情况下，我们任务选用的散列函数是均匀的，所有在讨论ASL时，可以不考虑这个因素）
2.选用的处理冲突的方法
3.散列表饱和的程度：装填因子值的大小（n-记录数，m-表的长度）
