【笔记】
开放寻址法：所有元素都存放在散列表里。当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现该元素不在表中。
删除操作：在槽中置一个特定的值DELETED。因此在必须删除关键字的应用中，往往采用链接法解决碰撞。
计算开放寻址法中的探查序列：
线性探查：h(k,i) = (h'(k)+i) mod m, i = 0,1,...,m-1
二次探查：h(k,i) = (h'(k)+c1*i+c2*i^2) mod m
双重散列：h(k,i) = (h1(k)+i*h2(k)) mod m
双重散列是用于开放寻址法最好的方法之一，因为它所产生的排列具有随机选择的排列的许多特性。
【练习】
11.4-1 考虑将关键字10、22、31、4、15、28、17、88、59用开放寻址法插入到一个长度为m=11的散列表中，辅助散列函数为h(k)=k mod m。说明用线性探查、二次探查(c1=1,c2=3)以及双重散列h2(k)=1+(k mod (m-1))将这些关键字插入散列表的结果。
22 88 0 0 4 15 28 17 59 31 10
22 0 88 17 4 0 28 59 15 31 10
22 0 59 17 4 15 28 88 0 31 10
11.4-2 请写出HASH-DELETE的伪代码；修改HASH-INSERT，使之能处理特殊值DELETED。
bool hashDelete(int k) {
int i=0;
do{
int j=h(k,i);
if (T[j]==0) {
return false;
}
else if (T[j]==k) {
T[j]=DELETED;
return true;
}
else i++;
}while (i<m);
return false;
}int hashInsert(int k) {
int i=0;
do{
int j=h(k,i);
if (a[j]==0||a[j]==DELETED) {
a[j]=k;
return j;
}
else i++;
}while (i<m);
return -1;
}*11.4-3 数论相关，见31章。
11.4-4 考虑一个采用了一致散列的开放寻址散列表。给出当装载因子为3/4和7/8时，在一次不成功查找中期望探查数的上界，以及一次成功查找中期望探查数的上界。
*11.4-5