保研复习数据结构记（7）--散列查找（哈希表）

除留余数法： H(key)=key%p。散列表长度为m，取一个不大于m但最接近或等于m的质数p，保证关键字均匀分布
散列函数要根据实际的关键字分布来考虑，不要教条化。
直接定址法：H(key)=a*key+b，其中a和b是常数。这种方法计算最简单，且不会产生冲突，他适合关键字分布基本连续的情况。但若关键字分布不连续，空位较多，会造成存储空间浪费
数字分析法：选取数码分布均匀的若干位作为散列地址。比如手机号码：156****0876，可以选取后四位作为散列地址，散列地址为0000-9999
平方取中法：取关键字平方值的中间几位作为散列地址，保证散列地址与任何一个地址位都相关。

什么是开放定址法？是指可存放新表项的空闲地址既向它的同义词表开放，又向它的非同义词表开放。其数学递推公式为：Hi=(H(key)+di)%m，m为散列表表长，di为增量序列
开放定址法有哪几种？线性探测法；平方探测法；伪随机序列法；
什么是线性探测法？di=0,1,2...m-1，即发生冲突时，以当前位置为起始每次往后探测相邻的下一个单元是否为空，线性探测得的地址长于哈希映射的地址。
开放定址法删除节点不能简单删除结点，那怎么办？删除结点不能简单的将被删除结点空间置为空，否则将认为它是终止节点，截断对后面结点的查找
线性探测法的查找效率？ 线性探测法很容易造成同义词和非同义词的聚集，堆积现象，严重影响查找效率
什么是平方探测法？发生冲突的元素以 $di=0^{2}+1^{2}-1^{2}+2^{2}-2^{2},...,k^{2},-k^{2}$
当使用平方探测法的时候，散列表长度m必须可以表示成4j+3的素数，才能探测到所有位置。
什么是伪随机序列法？di=某个伪随机序列