9.19.29.3

l} Page檢索的效率

l} Page基本概念（續

l} Page基本概念（續

l} Page平均檢索長度

l} Page nAS =ni=

PiC

l} Page假設線性表為（a,b,c）檢索a、0.4×1+0.1×2+0.5×3=

l} Page

l} Page9.1.19.1.29.1.3

l} Page

l} Page//代碼9-1順序檢索的結構類型定temte<classType>classItem{Item(Typevalue):key(value){}TypegetKey(){returnkey;}voidsetKey(Typek){key=k;}Type string vector<Item<Type>*>

l} Page te<classType>intTypek){int }

l} Page假設檢索每個關鍵碼是等概率的，Pin-Pi·(n-i)i=

1n-(n-i)ni=0 n+1=i=

i=

l} PageASL=p n+1+q (n+1)=p n+1+(1-p)(n+1)=(n+1)(1-p/2（n+1)/2<ASL<

l} Page

l} Page9.1.2可根據三種比較結果區分出三種情況（以遞增為例

l} Page//代碼9-3 te<classType>intBinSearch(vector<Item<Type>*>&dataList,intlength,Typek) intlow=1,high=length,mid;while(low<=high){high=mid-1; elseif(k>dataList[mid]->getKey())low } }

l} Page檢索關鍵碼18。low=1;high=9;第K=18一次：mid=5;array[5]=35>18high=4;第二次：mid=2array[2]=17<18low=3;(high=4)第三次：mid=3array[3]=18=18mid=3；return8

l} Page n

n或log n

l} PagejjASL

1 i=

2i-1=n+1lo (n+1)-

?log2(n+1)-

(n>

l} Page

l} Page“按塊有序

l} Page

l} Page

l} Page

l} Page先在索引表中確定待查元素所在ASL(n)=ASLb+

l} Page索引表是按塊內最大關鍵碼有的，且長度也不大，可以二分檢各子表內各個記錄不是按記錄關鍵

l} PageASL

=b+2

ASL

=s+2ASL=b+1+s+1=b+s+ =n+s=ASL

n時，ASLn+1≈l} Page

l} PageASL=ASLb+?log2(b+1)-1+?log2(1+n/s)+

l} Page

l} Page9.2檢索是

l} Page

l} Page

l} PageS={and,begin,do,end,for,go,if,repeat,then,until,while}char在字母表{a,b,c,...,z}中的序號，即：H(key)=key[0]–

l} Page

l} Page例9.2：在集合S中增加4個關鍵碼，集合S1+{else,array,with,intcharkey[];inti;{i=while((i<8)&&(key[i]!=‘\0’))return((key[0]+key(i-1)–2*’a’)/2}

l} Page

l} Page散列表的空間大小為填入表中的結點數為

l} Page

l} PageAddress＝Hash(key)

l} Page

l} Page…

l} Page

l} Pageh(x)＝xmod

l} Page

l} Page那么，h(x)＝xmod2k僅僅是x(用二進制那么，h(x)＝xmod10k僅僅是x(用十進

l} Page

l} Pagekey乘上一個常數A(0<A<hash(key)=n*(A*key%1)“A*key1”A*keyA*key%1=A*key-A*key

l} Pagekey123456n且取A= 5-1)/2= = *123456%1)=10000* …%1)=10000* …=

l} Page若地址空間為p位，就取A*key%1=A*key-A*key值Knuth認為：A可以取任何值，與待排序的數據特征有關。一般情況下取黃金分割(5-2最理想

l} Page一組二進制關鍵碼：(，，，平方結果為：(，，，

l} Page

l} Pagerlkr

( αα

i

表示第i個符號在第k位上出n/rn個數中均勻出現的lkk位)

l} Page992148l1=991269l2=990527l3=991630l4=991805l5=991558l6=992047990001①②③④⑤3

l} Pagel1=（8-8/10）2×1+（0-8/10）2l2=（8-8/10）2×1+（0-8/10）2l3=（2-8/10）2×2+（4-8/10）2×1+（0-8/10）2l4=l5=l6=（2-8/10）2×2+（1-8/10）2×4+8/10）2×4

l} Page

l} Page

l} Page進制數(210485)13，再把它轉換為十進(210485)13=2×135+1×134+4×132+8×13+=

l} Page

l} Page—把各部分的最后一—各部分不折斷，沿

l} Page[例9.6如果一本書的編號為0-442-20586-586586422022 0+0[1]008 609

l} PageintELFhash(char*key){unsignedlongh=0;while(*key){h=(h<<4)+unsignedlongg=h&0xF if(g)h^=g>>24;h&=}returnh%}

l} Page

l} Page在實際應用中應根據關鍵碼的特點，選有人曾用“賭”的統計分析方法對它們進行了模擬分析，結論是平方取中法若關鍵碼不是整數而是字符串時，可以把每個字符串轉換成整數，再應用

l} Page開散列方法openhashing拉鏈法，separatechaining閉散列方法closedhashing開地址方法，openaddressing

l} Page例：{、 、、 h(Key)=Key%

l} Page

l} Page

l} Page時引起多次磁盤，從而增加了檢

l} Page基本思想

l} Page

l} Page

l} Page

l} Page

l} Page

l} Page

l} Page

l} Page

l} Page

l} Page

l} Page

l} Paged0，d1，d2，...di，...dm-

l} Page

l} Page

l} Page

l} Page p(K，i)=

l} Page列表長度M=15，用線性探查法解決構造n=11，M=h(key)=

l} Page26:h(26)=0，36:h(36)=41:h(41)=2，38:h(38)=44:h(44)= 可分別放在和

l} PageM=h(key)=

l} Page

l} Pageic)mod探查函數是p(K，i

l} Page

l} Paged2i-1=(d+i2)%d2i=(d–i2)%p(K，2i)=-

l} Page例：使用一個大小M13k1的探查序列是3、4、2、7、k2的探查序列是2、3、1、6、

l} Pagep(K，i)=perm[i-這里perm是一個長度為M1的數包含值從1到M1

l} Pagevoidpermute(int*array,intn){for(inti=1;i<=n;i++)}

l} Page例：考慮一個大小為M13的表，perm[02，perm[1]=3，perm[2]=7。k1的探查序列是4、6、7、11、k2的探查序列是2、4、5、9、

l} Page

l} Page

l} Page(d+h2(key))%M，(d+2h2(key))%M，(d+3h2(key))%M

l} Pagedi=(d+ih2(key))%p(K,i)=i*h2

l} Pageh2key)必須與M雙散列的優點:不易產生“

l} Page在1≤h2(K)≤M1范圍之間h2(K)=Kmod(M-2)+或者h2(K)=[K/M]mod(M-2)+p，(p是小于M的最大素數)h2(KKmodq1q是小于p的最大

l} Page數h，計算出散列地址h(K)直到某個地址空間未被占用（可以插入

l} Page//代碼9-6 <classKey,classElem,class dict<Key,Elem, lem&e){intintpos if pos=(home+p(getkey(e),i))%}HT[pos]=e; returntrue;}

l} Page

l} Pageh，計算出散列地址h

l} PageM=h(key)=

l} Page//檢索關鍵碼值為k的記錄。假定每個關鍵碼的探查序列中 <classKey,classElem,class boolhashdict<Key,Elem, hashSearch(constKey&K,Elem&e)const{inthome= int intposhome; if p::eq(KHT[pose=pos=(home+p(K,i))%}

l} Page

l} PageM=h(key)=

l} Page

l} Page

l} Page鍵碼k1和k2，h(k12，h(k26。的二次探查序列是、、、 的二次探查序列是、、 、、1、9、3、

l} Page被刪除標記值稱為(tombstone

l} Page

l} Page

l} Page te<classKey,classElem,class stKey&{inthome=h(K);inti=0;

intpos while if( temp=HT[pos];HT[pos]=TOMB;//設置returntemp; pos=(home+p(K,i))%}}

l} Page <classKey,classElem,class hdict<Key,Elem, m&e){inthome=h(getkey(e));home記錄基位置inti=0;intpos while if( p::eq(getkey(e),HT[pos]))returnfalse; pos=(home+p(getkey(e),i))%} returntrue;}

l} PageTOMB即“HT[pos]==TOMB”時就跳 入到第一個TOMB處（如果有的話），否

l} Page p, boolhashdict<Key,Elem, Elem&e){inthome=h(getkey(e)); inti=0,insce;boolintpos if( if( p::eq(TOMB,HT[pos])&& !tomb_pos){ pos=(home+p(getkey(e),i))%} returntrue;}

l} Page

l} Page

l} Pageα=N/M有關

l} Page

l} Page址被占用的可能性是用的可能性是NN1)M(M-