§ 9.3.2 B-树 1.概念 B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于外部查找。 基本想法是增大结点来降低树高，减少访问外存的次数 一棵m阶B-树，每个结点最多有m个孩子，m一般为50－2000 例如，1棵1001阶B-树，3层即可包含10亿以上的Keys，当根结点置于内存时，查找任一Key至多只要访问2次外存。 1000 … 1001 1个结点 1000个关键字 1001个结点 1,001,000个关键字 1,002,001个结点 1,002,001,000个关键字

§ 9.3.2 B-树 定义：一棵m(m≥3)阶的B-树是满足下述性质的m叉树： 性质1：每个结点至少包含下列数据域：(j, P0, K1, P1, K2, … , Kj , Pj ) j：keys总数， Ki：关键字， Pi：指针 keys(P0) < K1 <keys(P1) < K2 < … < Kj < keys(Pj) 性质2：所有叶子在同一层上，叶子层数为树高h，叶子中的指针为空。 性质3：每个非根结点中的关键字数目j满足： 即：每个非根的内部结点的子树数在m和 之间 性质4：非空的B－树中，根至少有1个关键字。 即：根不是叶子时，子树数为：2～m之间

a 1 24 c b 1 15 3 33 48 53 d e 2 ∧ 10 ∧ 20 ∧ 1 ∧ 20 ∧ g h f 2 ∧ 28 ∧ 31 ∧ 1 ∧ 37 ∧ 1 ∧ 50 ∧ i 1 ∧ 56 ∧ 一棵包含13个关键字的4阶B_树

§ 9.3.2 B-树 运算 查找 多路查找：先在结点内查找（折半或顺序），后在子结点中查找（读盘） 插入和生成 平衡机制：满时插入分裂结点，从叶子 根，树高可能长 一层 删除 平衡机制：半满时删除，可能要合并结点，从叶子 根， 树高可能减一层

#define M 5 /* 根据实际需要定义B_树的阶数 */ typedef struct BTNode { int keynum ; /* 结点中关键字的个数 */ struct BTNode *parent ; /* 指向父结点的指针 */ KeyType key[M+1] ; /* 关键字向量,key[0]未用 */ struct BTNode *ptr[M+1] ; /* 子树指针向量 */ RecType *recptr[M+1] ; /* 记录指针向量,recptr[0]未用 */ }BTNode ;

2 B_树的查找 ⑴ 算法思想 由B_树的定义可知，在其上的查找过程和二叉排序树的查找相似。 ① 从树的根结点T开始，在T所指向的结点的关键字向量key[1…keynum]中查找给定值K(用折半查找) ： 若key[i]=K(1≤i≤keynum)，则查找成功，返回结点及关键字位置；否则，转⑵； ② 将K与向量key[1…keynum]中的各个分量的值进行比较，以选定查找的子树： ◆ 若K<key[1]：T=T->ptr[0]；

⑵ 算法实现 ◆ 若key[i]<K<key[i+1](i=1, 2, …keynum-1)： T=T->ptr[i]； ◆ 若K>key[keynum]：T=T->ptr[keynum]； 转①，直到T是叶子结点且未找到相等的关键字，则查找失败。 ⑵ 算法实现 int BT_search(BTNode *T, KeyType K, BTNode *p) /* 在B_树中查找关键字K, 查找成功返回在结点中的位置 */ /* 及结点指针p; 否则返回0及最后一个结点指针 */ { BTNode *q ; int n ; p=q=T ;

⑶ 算法分析 在B_树上的查找有两中基本操作： while (q!=NULL) { p=q ; q->key[0]=K ; /* 设置查找哨兵 */ for (n=q->keynum ; K<q->key[n] ; n--) if (n>0&&EQ(q->key[n], K) ) return n ; q=q->ptr[n] ; } return 0 ; ⑶ 算法分析 在B_树上的查找有两中基本操作： ◆ 在B_树上查找结点(查找算法中没有体现)；

◆ 在结点中查找关键字：在磁盘上找到指针ptr所指向的结点后，将结点信息读入内存后再查找。因此，磁盘上的查找次数(待查找的记录关键字在B_树上的层次数)是决定B_树查找效率的首要因素。 根据m阶B_树的定义，第一层上至少有1个结点，第二层上至少有2个结点；除根结点外，所有非终端结点至少有m/2棵子树，…，第h层上至少有m/2h-2个结点。在这些结点中：根结点至少包含1个关键字，其它结点至少包含m/2-1个关键字，设s=m/2，则总的关键字数目n满足： n≧1+(s-1)∑ 2si-2=1+ i=2 h =2sh-1-1 s-1 sh-1-1 2(s-1)

因此有： h≦1+ ㏒s((n+1)/2)=1+㏒m/2((n+1)/2) 即在含有n个关键字的B_树上进行查找时，从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+ ㏒m/2((n+1)/2) 。

3 B_树的插入 B_树的生成也是从空树起，逐个插入关键字。插入时不是每插入一个关键字就添加一个叶子结点，而是首先在最低层的某个叶子结点中添加一个关键字，然后有可能“分裂”。 ⑴ 插入思想 ① 在B_树的中查找关键字K，若找到，表明关键字已存在，返回；否则，K的查找操作失败于某个叶子结点，转 ②； ② 将K插入到该叶子结点中，插入时，若： ◆ 叶子结点的关键字数<m-1：直接插入； ◆ 叶子结点的关键字数=m-1：将结点“分裂” 。

⑵ 结点“分裂”方法 设待“分裂”结点包含信息为： (m，A0，K1，A1，K2，A2，… ，Km，Am)，从其中间位置分为两个结点： (m/2-1，A0，K1，A1，… ，Km/2-1 ，Am/2-1 ) (m-m/2，Am/2，Km/2+1，Am/2+1 ，… ，Km，Am ) 并将中间关键字Km/2插入到p的父结点中，以分裂后的两个结点作为中间关键字Km/2的两个子结点。 当将中间关键字Km/2插入到p的父结点后，父结点也可能不满足m阶B_树的要求(分枝数大于m)，则必须对父结点进行“分裂”，一直进行下去，直到没有父结点或分裂后的父结点满足m阶B_树的要求。

当根结点分裂时，因没有父结点，则建立一个新的根，B_树增高一层。 ⑶ 算法实现 要实现插入，首先必须考虑结点的分裂。设待分裂的结点是p，分裂时先开辟一个新结点，依此将结点p中后半部分的关键字和指针移到新开辟的结点中。分裂之后，而需要插入到父结点中的关键字在p的关键字向量的p->keynum+1位置上。

f h m b f h m b d f h m p b d h f m p h l f m b d p g h l l f h m g l (a) 一棵2-3树 f h m b d (b) 插入d后 f h m p b d 分裂 (c) 插入p后并进行分裂 h f m p h l f m b d p (d) 插入l后 分裂 g h l (e) 插入g后并进行分裂 l f h m g 分裂 在B_树中进行插入的过程 l f h m b d p g h f m (f) 继续进行分裂

BTNode *split(BTNode *p) /* 结点p中包含m个关键字，从中分裂出一个新的结点 */ { BTNode *q ; int k, mid, j ; q=(BTNode *)malloc(sizeof( BTNode)) ; mid=(m+1)/2 ; q->ptr[0]=p->ptr[mid] ; for (j=1,k=mid+1; k<=m; k++) { q->key[j]=p->key[k] ; q->ptr[j++]=p->ptr[k] ; } /* 将p的后半部分移到新结点q中 */ q->keynum=m-mid ; p->keynum=mid-1 ; return(q) ; }

/* 在B_树T中插入关键字K，*/ void insert_BTree(BTNode *T, KeyType K) { BTNode *q, *s1=NULL, *s2=NULL ; int n ; if (!BT_search(T, K, p)) /* 树中不存在关键字K */ { while (p!=NULL) { p->key[0]=K ; /* 设置哨兵 */ for (n=p->keynum ; K<p->key[n] ; n--) { p->key[n+1]=p->key[n] ; p->ptr[n+1]=p->ptr[n] ; } /* 后移关键字和指针 */ p->key[n]=K ; p->ptr[n-1]=s1 ;

p->ptr[n+1]=s2 ; /* 置关键字K的左右指针 */ if (++(p->keynum )<m) break ; else { s2=split(p) ; s1=p ; /* 分裂结点p */ K=p->key[p->keynum+1] ; p=p->parent ; /* 取出父结点*/ } if (p==NULL) /* 需要产生新的根结点 */ { p=(BTNode*)malloc(sizeof( BTNode)) ; p->keynum=1 ; p->key[1]=K ; p->ptr[0]=s1 ; p->ptr[1] =s2 ; } }

4 B_树的删除 利用m阶B_树的插入操作，可从空树起，将一组关键字依次插入到m阶B_树中，从而生成一个m阶B_树。 在B_树上删除一个关键字K ，首先找到关键字所在的结点N，然后在N中进行关键字K的删除操作。 若N不是叶子结点，设K是N中的第i个关键字，则将指针Ai-1所指子树中的最大关键字(或最小关键字)K’放在(K)的位置，然后删除K’，而K’一定在叶子结点上。如图，删除关键字h，用关键字g代替h的位置，然后再从叶子结点中删除关键字g。

l m b d q e g h f p l m e g b g m b f 删除q 删除h (a) 删除e 删除d (d) (c) (b)

⑴ 若结点N中的关键字个数>m/2-1：在结点中直接删除关键字K，如图 (b)∽©所示。 从叶子结点中删除一个关键字的情况是： ⑴ 若结点N中的关键字个数>m/2-1：在结点中直接删除关键字K，如图 (b)∽©所示。 ⑵ 若结点N中的关键字个数=m/2-1：若结点N的左(右)兄弟结点中的关键字个数>m/2-1，则将结点N的左(或右)兄弟结点中的最大(或最小)关键字上移到其父结点中，而父结点中大于(或小于)且紧靠上移关键字的关键字下移到结点N，如图 (a)。 ⑶ 若结点N和其兄弟结点中的关键字数=m/2-1：删除结点N中的关键字，再将结点N中的关键字、指针与其兄弟结点以及分割二者的父结点中的某个关键字Ki，合并为一个结点，若因此使父结点中的关键字个数<m/2-1 ，则依此类推，如图 (d)。

算法实现 在B_树上删除一个关键字的操作，针对上述的⑵和⑶的情况，相应的算法如下： int BTNode MoveKey(BTNode *p) /* 将p的左(或右)兄弟结点中的最大(或最小)关键字上移 */ /* 到其父结点中,父结点中的关键字下移到p中 */ { BTNode *b , *f=p->parent ; /* f指向p的父结点 */ int k, j ; for (j=0; f->ptr[j]!=p; j++) /* 在f中找p的位置 */ if (j>0) 　　/* 若p有左邻兄弟结点 */ { b=f->ptr[j-1] ; /* b指向p的左邻兄弟 */

{ for (k=p->keynum; k>=0; k--) { p->key[k+1]=p->key[k]; if (b->keynum>(m-1)/2) /* 左邻兄弟有多余关键字 */ { for (k=p->keynum; k>=0; k--) { p->key[k+1]=p->key[k]; p->ptr[k+1]=p->ptr[k]; } /* 将p中关键字和指针后移 */ p->key[1]=f->key[j]; f->key[j]=b->key[keynum] ; /* f中关键字下移到p, b中最大关键字上移到f */ p->ptr[0]= b->ptr[keynum] ; p->keynum++ ; b->keynum-- ;

if (j<f->keynum) /* 若p有右邻兄弟结点 */ return(1) ; } if (j<f->keynum) 　/* 若p有右邻兄弟结点 */ { b=f->ptr[j+1] ; /* b指向p的右邻兄弟 */ if (b->keynum>(m-1)/2) /* 右邻兄弟有多余关键字 */ { p->key[p->keynum]=f->key[j+1] ; f->key[j+1]=b->key[1]; p->ptr[p->keynum]=b->ptr[0]; /* f中关键字下移到p, b中最小关键字上移到f */ for (k=0; k<b->keynum; k++)

{ b->key[k]=b->key[k+1]; b->ptr[k]=b->ptr[k+1]; } /* 将b中关键字和指针前移 */ p->keynum++ ; b->keynum-- ; return(1) ; } return(0); } /* 左右兄弟中无多余关键字,移动失败 */

BTNode *MergeNode(BTNode *p) { BTNode *b, f=p->parent ; int j, k ; for (j=0; f->ptr[j]!=p; j++) /* 在f中找出p的位置 */ if (j>0) b=f->ptr[j-1]; /* b指向p的左邻兄弟 */ else { b=p; p=p->ptr[j+1]; } /* p指向p的右邻 */ b->key[++b->keynum]=f->key[j] ; b->ptr[p->keynum]=p->ptr[0] ; for (k=1; k<=p->keynum ; k++) { b->key[++b->keynum]=p->key[k] ; b->ptr[b->keynum]=p->ptr[k] ; } /* 将p中关键字和指针移到b中 */

free(p); for (k=j+1; k<=f->keynum ; k++) { f->key[k-1]=f->key[k] ; f->ptr[k-1]=f->ptr[k] ; } /* 将f中第j个关键字和指针前移 */ f->keynum-- ; return(b) ; }

void DeleteBTNode(BTNode *T, KeyType K) { BTNode *p, *S ; int j,n ; j=BT_search(T, K, p) ; /* 在T中查找K的结点 */ if (j==0) return(T) ; if (p->ptr[j-1]) { S=p->ptr[j-1] ; while (S->ptr[S->keynum]) S=S->ptr[S->keynum] ; /* 在子树中找包含最大关键字的结点 */ p->key[j]=S->key[S ->keynum] ; p=S ; j=S->keynum ; }

for (n=j+1; n<p->keynum; n++) p->key[n-1]=p->key[n] ; /* 从p中删除第m个关键字 */ p->keynum-- ; while (p->keynum<(m-1)/2&&p->parent) { if (!MoveKey(p) ) p=MergeNode(p); p=p->parent ; } /* 若p中关键字树目不够,按⑵处理 */ if (p==T&&T->keynum==0) { T=T->ptr[0] ; free(p) ; } }

5 B+树 在实际的文件系统中，基本上不使用B_树，而是使用B_树的一种变体，称为m阶B+树。 它与B_树的主要不同是叶子结点中存储记录。在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B_树的主要差异是： ⑴ 若一个结点有n棵子树，则必含有n个关键字； ⑵ 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接；

⑶ 所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。 如图所示是一棵3阶B+树。 ⑶ 所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。 如图所示是一棵3阶B+树。 由于B+树的叶子结点和非叶子结点结构上的显著区别，因此需要一个标志域加以区分，结点结构定义如下： 一棵3阶B+树 35 96 17 35 58 76 96 5 12 17 63 76 79 84 96 19 23 35 41 49 58

typedef enum{branch, left} NodeType ; typedef struct BPNode { NodeTag tag ; /* 结点标志 */ int keynum ; /* 结点中关键字的个数 */ struct BTNode *parent ; /* 指向父结点的指针 */ KeyType key[M+1] ; /* 组关键字向量,key[0]未用 */ union pointer { struct BTNode *ptr[M+1] ; /* 子树指针向量 */ RecType *recptr[M+1] ; /* recptr[0]未用 */ }ptrType ; /* 用联合体定义子树指针和记录指针 */ }BPNode ;

与B_树相比，对B+树不仅可以从根结点开始按关键字随机查找，而且可以从最小关键字起，按叶子结点的链接顺序进行顺序查找。在B+树上进行随机查找、插入、删除的过程基本上和B_树类似。 在B+树上进行随机查找时，若非叶子结点的关键字等于给定的K值，并不终止，而是继续向下直到叶子结点(只有叶子结点才存储记录) ， 即无论查找成功与否，都走了一条从根结点到叶子结点的路径。 B+树的插入仅仅在叶子结点上进行。当叶子结点中的关键字个数大于m时，“分裂”为两个结点，两个结点中所含有的关键字个数分别是(m+1)/2和 (m+1)/2 ，且将这两个结点中的最大关键字提升到父结点中，用来替代原结点在父结点中所对应的关键字。提升后父结点又可能会分裂，依次类推。

§ 9.4 散列技术 lgn＋O(1) 要突破此界，就不能只依赖于比较来进行。 § 9.4.1 散列表的概念 上述查找均是基于key的比较，由判定树可证明，在平均和最坏情况下所需的比较次数的下界是： lgn＋O(1) 要突破此界，就不能只依赖于比较来进行。 § 9.4.1 散列表的概念 直接寻址：当结点的key和存储位置间建立某种关系时，无须比较即可找到结点的存储位置。 例如，若500个结点的keys取值为1～500间互不相同的整数，则keys可作为下标，将其存储到T[1..500]之中，寻址时间为O (1)。

§ 9.4.1 散列表的概念 压缩映象： 例子：设影像出租店 总片数：10,000张 借还：500人次/每天 记录：（电话号码，姓名，住址，…）, Key为7位电话号码 直接寻址：须保留1000万个记录 但实际只要大于500即可，最多1万个记录 一般情况 全集U：可能发生的关键字集合，即关键字的取值集合 实际发生集K：实际需要存储的关键字集合 ∵ |K| << |U|，当表T的规模取|U|浪费空间，有时甚至无法实现 ∴ T的规模一般取O(K), 但压缩存储后失去了直接寻址的功能

§ 9.4.1 散列表的概念 散列（hash）函数h 在keys和表地址之间建立一个对应关系h，将全集U映射到T[0..m-1]的下标集上： h：U→{ 0, 1, … , m-1 } ∀ki∈U，h(ki) ∈ { 0,1,…,m-1 } 散列表: T 散列地址（散列值）：散列函数值h(ki) 散列（hashing）： 关键字 集合 存储地址 hash T[0..m-1] h(k2) U. . . K k1 . . . . k2 . . . k3. h(k1)=h(k3) m-1

§ 9.4.1 散列表的概念 冲突(碰撞): 若ki ≠kj，有h(ki) ＝ h(kj) 散列（hash）函数h 冲突(碰撞): 若ki ≠kj，有h(ki) ＝ h(kj) 同义词：发生冲突的两个关键字互为同义词(相对于h) 能完全避免冲突吗？ 须满足：① |U|≤m ② 选择合适的hash函数 否则只能设计好的h使冲突尽可能少 解决冲突： 须确定处理冲突的方法 装填因子：冲突的频繁程度除了与h的好坏相关，还与表的填满程度相关 α＝n/m， 0≤ α ≤ 1

§ 9.4.2 散列函数的构造方法 原则：简单、均匀 简单－－计算快速，均匀－－冲突最小化 假定：关键字定义在自然数集合上，否则将其转换到自然数集合上 1、平方取中法 先通过平方扩大相近数的差别，然后取中间的若干位作为散列地址。因为中间位和乘数的每一位相关，故产生的地址较为均匀。 int Hash( int k ) { k *=k; k /=100; //去掉末尾两位数 return k％1000；//取中间3位，T的地址为0~999 }

§ 9.4.2 散列函数的构造方法 2、除余法 3、随机数法 选取哈希函数，考虑的因素 用表长除以关键字，取其余数作为散列地址 h(k)＝ k%p； p≤m，有时取p＝m p最好取素数，或取不包含小于20的质因数的合数 优点：最简单，无需定义为函数，直接写到程序里使用 3、随机数法 h(k)＝random( k ); 伪随机函数须保证函数值在0～m－1之间 选取哈希函数，考虑的因素 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率

§ 9.4.3 处理冲突的方法 1、开放地址法（闭散列） 基本思想：当发生冲突时，使用某种探测技术在散列表中形成一个探测序列，沿此序列逐个单元查找，直到找到给定的key，或碰到1个开放地址（空单元）为止 插入时，探测到开地址可将新结点插入其中 查找时，探测到开地址表示查找失败 开地址表示：与应用相关，如key为串时，用空串表示开地址 一般形式 hi＝（h(k)＋di）％m 1 ≤i ≤ m－1 （9.1） 探测序列：h(k), h1, h2 , …, hm-1 开地址法要求：α<1， 实用中 0.5≤ α ≤ 0.9

§ 9.4.3 处理冲突的方法 （1）线性探测法 开放地址法分类：按照形成探测序列的方法不同，可将其分为3类：线性探测、二次探测、双重散列法 基本思想：将T[0..m-1]看作一循环向量，令di＝i，即 hi＝（h(k)＋i）％m 0 ≤i ≤ m－1 若令d＝h(k)，则最长的探测序列为： d,d+1,…,m-1,0,1,…,d-1 探测过程终止于 探测到空单元：查找时失败，插入时写入 探测到含有k的单元：查找时成功，插入时失败 探测到T[d-1] 但未出现上述2种情况：查找、插入均失败

§ 9.4.3 处理冲突的方法 例1：已知一组keys为（26,36,41,38,44,15,68,12,06,51）, 用除余法和线性探测法构造散列表 解：∵ α<1，n＝10，不妨取m＝13，此时α≈0.77 h( k )= k%13 keys：(26,36,41,38,44,15,68,12,06,51) 对应的散列地址：( 0,10, 2, 12, 5, 2, 3, 12, 6, 12) 12 11 10 9 8 7 6 5 4 3 2 1 38 36 44 41 26 51 06 68 15 T[0..12] 探测次数

§ 9.4.3 处理冲突的方法 非同义词冲突：上例中，h(15)=2，h(68)=3，15和68不是同义词，但是15和41这两个同义词处理过程中，15先占用了T[3]，导致插入68时发生了非同义词的冲突。 聚集（堆积）：一般地，用线性探测法解决冲突时，当表中i,i+1,…,i+k的位置上已有结点时，一个散列地址为i,i+1,…,i+k,i+k+1的结点都将争夺同一地址：i＋k＋1。这种不同地址的结点争夺同一后继地址的现象称为聚集。 聚集增加了探测序列的长度，使查找时间增加。应跳跃式地散列。 12 11 10 9 8 7 6 5 4 3 2 1 38 36 44 41 26 51 06 68 15 T[0..12] 探测次数

§ 9.4.3 处理冲突的方法 （2）二次探测法： 探测序列为( 增量序列为di =i2 )： hi＝（h(k)＋i*i）％m 0 ≤i ≤ m－1 缺点：不易探测到整个空间 （3）双重散列法： 是开地址法中最好的方法之一，探测序列为 hi＝（h(k)＋i* h1(k) ）％m 0 ≤i ≤ m－1 即： di =i* h1(k) 特点：使用了两个散列函数，一般须使h1(k)的值与m互素

§ 9.4.3 处理冲突的方法 2、拉链法（开散列） 基本思想：将所有keys为同义词的结点连接在同一个单链表中，若散列地址空间为0～m-1，则将表定义为m个头指针组成的指针数组T[0..m-1]，其初值为空。 例2：keys和hash函数同前例 0 1 2 3 4 5 6 7 8 9 10 11 12 44 ^ 41 15 26 68 06 36 12 38 51 比较次数： 1 2 3

§ 9.4.3 处理冲突的方法 特点 无堆积现象、非同义词不会冲突、ASL较短 无法预先确定表长度时，可选此方法 删除操作易于实现，开地址方法只能做删除标记 允许α>1，当n较大时，节省空间

§ 9.4.4 散列表上的运算 仅给出开放定址法处理冲突时的相关运算 存储结构 1、查找运算 #define NIL -1 //空结点标记 #define m 997 //表长，依赖应用和α typedef struct { KeyType key; //…. }NodeType, HashTable[m]; 1、查找运算 和建表类似，使用的函数和处理冲突的方法应与建表一致 开地址可统一处理

§ 9.4.4 散列表上的运算 int Hash( KeyType K, int i){ return ( h(K)+ Increment( i ) )%m; //Increment相当于di } Int HashSearch( HashTable T, KeyType K, int *pos){ int i=0; //探测次数计数器 do { *pos=Hash( K,i ); //求探测地址hi if ( T[*pos].key==K ) return 1; //成功 if ( T[*pos].key==NIL ) return 0; //失败 } while (++i<m); //最多探测m次 return -1; //可能是表满，失败

§ 9.4.4 散列表上的运算 2、插入和建表 插入：先查找，找到开地址成功，否则(表满、K存在)失败 void HashInsert( HashTable T, NodeType new ){ int pos, sign; sign=HashSearch( T, new.key, &pos ) ; if ( !sign ) //标记为0，是开地址 T[pos]=new; //插入成功 else if ( sign>0 ) printf(“duplicate key”) ; //重复，插入失败 else Error(“overflow”); //表满，插入失败 } 建表：将表中keys清空，然后依次调用插入算法插入结点

§ 9.4.4 散列表上的运算 3、删除 开地址法不能真正删除（置空），而应该置特定标记Deleted 当有删除操作时，一般不用开地址法，而用拉链法 4、性能分析 只分析查找时间，插删取决于查找，因为冲突，仍需比较。 例子（见例1和例2图） 成功 线性探测：ASL＝(1*6+2*2+3*1+9*1)/10=2.2 //n=10 拉链法： ASL＝(1*7+2*2+3*1)/10=1.4 //n=10

§ 9.4.4 散列表上的运算 不成功: 查找不成功时对关键字需要执行的平均比较次数 线性探测：直到探测到开地址为止 若h(K)=0，则必须依次将T[0..8]中的关键字和K比较 ASL＝(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54 //m=13 注意：当m>p（p＝|散列地址集|）时，分母应该为p T[0..12] 12 11 10 9 8 7 6 5 4 3 2 1 38 36 51 06 44 68 15 41 26 探测次数

§ 9.4.4 散列表上的运算 不成功 拉链法：不包括空指针判定 ASL＝(1+0+2+1+0+1+1+0+0+0+1+0+3)/13=0.77 //m=13 0 1 2 3 4 5 6 7 8 9 10 11 12 44 ^ 41 15 26 68 06 36 12 38 51 比较次数： 1 2 3

§ 9.4.4 散列表上的运算 一般情况 5、用途 加速查找 加密等信息安全领域 线性探测 成功：ASL＝（1＋1/(1－α)）/2 显然，只与α相关，只要α合适，ASL＝O(1)。 其他方法优于线性探测：略 5、用途 加速查找 加密等信息安全领域