淺談hashppt課件-免費閱讀
【正文】 begin posi:=locate(x)。 end。 begin h:= x mod p。 設(shè)插入的元素的關(guān)鍵字為 x ， A 為存儲的數(shù)組。 折疊法 如果關(guān)鍵碼的位數(shù)比地址碼的位數(shù)多，而且各位分布較均勻，不適于用數(shù)字分析法丟掉某些 數(shù)位，那么可以考慮用折疊法。記住 “ 素數(shù)是我們的得力助手 ” 數(shù)字分析法 常有這樣的情況：關(guān)鍵碼的位數(shù)比存儲區(qū)域的地址的位數(shù)多，在這種情況下可以對關(guān)鍵碼的 各位進行分析，丟掉分布不均勻的位留下分布均勻的位作為地址。 簡單的證明：假設(shè) m 是一個有較多約數(shù)的數(shù)，同時在數(shù)據(jù)中存在 q 滿足 gcd(m,q)=d 1 ，即 有 m=a*d,q=b*d,則有以下等式： q mod m= q – m* [q div m] =q – m*[b div a] 。現(xiàn)在要儲存和使用下面的線性表： A: (1,75,324,43,1353,90,46). 我們可以定義一維數(shù)組 a:array[1..n] of longint。 其中， [b div a]的取值范圍是不會超過 [0， b]的正整數(shù)。 本方法適用于所有關(guān)鍵字已知，并對關(guān)鍵字中每一位的取值分布情況作出了分析。折疊法是將關(guān)鍵碼從某些地方斷開，分關(guān)鍵碼為幾個部分，其中 有一部分的長度等于地址碼的長度，然后將其余部分加到它的上面，如果最高位有進位，則把進 位丟掉。 初始化比較容易，例如 const empty=maxlongint。 end。 插入元素 procedure insert(x:longint)。 if A[posi]=x then member:=true else member:=false。 var posi:integer。 locate:=(orig+i) mod S。 哈希函數(shù)值的運算根據(jù)函數(shù)的不同而變化，例如除余法的一個例子： function h(x:longint):Integer。 （ 236075） 13=2*135+3*134+6*133+7*13+5 =(841547)10 再進行數(shù)字分析，比如選擇第 2,3,4,5 位，于是h(236075)=4154 A:(18,75,60,43,54,90,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1