《淺談hash》ppt課件-全文預(yù)覽
【正文】 ： A: (1,75,324,43,1353,90,46). 上述兩種方法分別造成了時間和空間上的大量浪費(fèi)，尤其是數(shù)據(jù)范圍較廣時，可以對第二種方法進(jìn)行優(yōu)化 設(shè)計一個函數(shù) h(key):=key mod 13 然后把 key儲存在 a[h(key)]中， 這樣的話定義一個 0..12的數(shù)組就夠了 A:(18,75,60,43,54,90,46,5,15,33) h[i]:=i mod 13 0 1 2 3 4 5 6 7 8 9 10 11 12 54 43 18 46 60 75 90 18 mod 13=5 75 mod 13=10 60 mod 13=8 43 mod 13=4 54 mod 13=2 90 mod 13=12 46 mod 13=7 5 mod 13=5 15 mod 13=2 31 mod 13=5 。 if A[posi]=x then member:=true else member:=false。 //error 即為發(fā)生了錯誤，當(dāng)然這是可以避免的 end。 插入元素 procedure insert(x:longint)。 i:=0。 end。 begin for i:=0 to p1 do A[i]:=empty。 初始化比較容易，例如 const empty=maxlongint。一般取大于原來基數(shù)的數(shù)作轉(zhuǎn)換的基數(shù)，并且兩個基數(shù)要是互質(zhì)的。折疊法是將關(guān)鍵碼從某些地方斷開，分關(guān)鍵碼為幾個部分，其中 有一部分的長度等于地址碼的長度，然后將其余部分加到它的上面，如果最高位有進(jìn)位，則把進(jìn) 位丟掉。 平方取中法 將關(guān)鍵碼的值平方，然后取中間的幾位作為散列地址。 本方法適用于所有關(guān)鍵字已知，并對關(guān)鍵字中每一位的取值分布情況作出了分析。也就是說余數(shù)的分布變得 不均勻了。 其中， [b div a]的取值范圍是不會超過 [0， b]的正整數(shù)。 除余法 選擇一個適當(dāng)?shù)恼麛?shù) m，用 m 去除關(guān)鍵碼，取其余數(shù)作為地址，即： h(Key)= Key mod m， 這個方法應(yīng)用的最多，其關(guān)鍵是
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1