哈希函數(shù)構(gòu)造方法研究(doc畢業(yè)設(shè)計論文)-在線瀏覽
2025-08-05 20:54本頁面
【正文】 據(jù)哈希表的大小，選取其中各種符號分布均勻的若干位作為哈希地址。計算出rk值越小，i=1表明在該位（第k位）各種符號分布越不均勻。也可以把第①②和第⑤位想加，舍去進位，變成一位數(shù)，再與第③④位合起來哈希地址等。如果換一個關(guān)鍵字集合，選擇哪幾位重新決定。這種方法適用于關(guān)鍵字位數(shù)較多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻的情況。例4，當哈希表長為1000時，關(guān)鍵字key=110108331119891，允許的地址空間為三位十進制數(shù)，則這兩種疊加情況如圖（2）： 移位疊加 邊界疊加 8 9 1 8 9 1 1 1 9 9 1 1 3 3 1 3 3 1 1 0 8 8 0 1 + 1 1 0 + 1 1 0 (1) 5 5 9 (3)0 4 4 圖（2）由折疊法求哈希地址 用移位疊加得到的哈希地址是559，而用邊界疊加所得到的哈希地址是44。轉(zhuǎn)化的辦法可以用ASCⅡ字符或字符的次序值。這個方法是先取關(guān)鍵字的平方，然后根據(jù)可使用空間的大小，選取平方數(shù)是中間幾位為哈希地址。例5，若設(shè)哈希表長為1000則可取關(guān)鍵字平方值的中間三位，如圖（3）所示：關(guān)鍵字關(guān)鍵字的平方哈希函數(shù)值1234152275622721434592449924413217073424734321410329796297圖（3）平方取中哈希函數(shù)示例 [4] ↑有人曾用“輪盤賭”的統(tǒng)計分析方法對它們進行了模擬分析，結(jié)論是平方取中法最接近“隨機化”。假設(shè)可利用地址空間大小為103，平方后取平方數(shù)的中間三位作為相當記錄的存儲地址。 //去掉低11位 Key=11。 } 減去法是數(shù)據(jù)的鍵值減去一個特定的數(shù)值以求得數(shù)據(jù)存儲的位置。編號1001員工的數(shù)據(jù)在數(shù)據(jù)中的第一筆。從而獲得有關(guān)員工的所有信息，因為編號1000以前并沒有數(shù)據(jù)，所有員工編號都從1001開始編號。一般取大于原來基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個基數(shù)應該是互素的。[5] ↑取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址，即設(shè)定哈希函數(shù)為 Hash(key)=key mod p (p≤m)，其中，除數(shù)p稱作模。對于除留余數(shù)法求哈希地址，關(guān)鍵在于模p的選擇。理論研究表明，除留余數(shù)法的模p取不大于表長且最接近表長m素數(shù)時效果最好，～（n為存在的數(shù)據(jù)元素個數(shù)）。 又例圖(5)：表長m81632641282565121000模p7133161127251503997由于除留余數(shù)法的地址計算方法簡單，而且在許多情況下效果較好。編號5428員工的數(shù)據(jù)（編號5428除以236取余數(shù)得0）放數(shù)據(jù)中的第一筆，編號3512員工數(shù)據(jù)（編號3512除以236取余數(shù)得8）放數(shù)據(jù)中的第九筆…依次類推。隨機乘數(shù)法使用一個隨機實數(shù)f,0≤f1,乘積f*k的分數(shù)部分在0～1之間，用這個分數(shù)部分的值與n（哈希表的長度）相乘，乘積的整數(shù)部分就是對應的哈希值，顯然這個哈希值落在0～n1之間。通常若地址空間為p位就是選n=，他認為f取任何值都可以，但某些值效果更好。[8] ↑9．字符串數(shù)值哈希法在很都情況下關(guān)鍵字是字符串，因此這樣對字符串設(shè)計Hash函數(shù)是一個需要討論的問題。 while (i 10 amp。 X[i]) Sum +=X[i++]。 //N是記錄的條數(shù) }這種函數(shù)把字符串的前10個字符的ASCⅡ值之和對N取摸作為Hash地址，只要N較小，Hash地址將較均勻分布[0，N]區(qū)間內(nèi)，因此這個函數(shù)還是可用的。whie (*key){ h=(h4)+ *key。g=h amp。if (g) h^=g24。 =～g。} 這個函數(shù)稱為ELFHash(Exextable and Linking Format ,ELF,可執(zhí)行鏈接格式)函數(shù)。[7] ↑ 旋轉(zhuǎn)法是將數(shù)據(jù)的鍵值中進行旋轉(zhuǎn)。 例11，某學校同一個系的新生（小于100人）的學號前5位數(shù)是相同的，只有最后2位數(shù)不同，我們將最后一位數(shù)，旋轉(zhuǎn)放置到第一位，其余的往右移。[9] ↑偽隨機數(shù)法是將利用數(shù)據(jù)的鍵值經(jīng)過隨機數(shù)法的運算后的結(jié)果作為數(shù)據(jù)存儲的位置。[10] ↑ 小 結(jié)有許多種不同的哈希函數(shù)設(shè)計方法，這里主要討論幾種常用的不同類型關(guān)鍵字的希函數(shù)設(shè)計方法：直接定址法、數(shù)字分析法、折疊法、平方取中法、減去法、基數(shù)轉(zhuǎn)換法、除留余數(shù)法、隨機乘數(shù)法、字符串數(shù)值哈希法、偽隨機數(shù)法、旋轉(zhuǎn)法。如：當鍵字是字符串時可以用字符串數(shù)值哈希法構(gòu)造哈希函數(shù)；當關(guān)鍵字是整數(shù)類型時就可以用除留余數(shù)法、直接定址法和數(shù)字分析法等設(shè)計哈希函數(shù)；而關(guān)鍵字是小數(shù)類型常用偽隨機數(shù)法來構(gòu)造哈希函數(shù)等。 北京：清華大學出版社，2002[7]（C與
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1