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