查找 - 散列技術 - 散列函數的構造方法

　　散列函數的構造方法

　　散列函數的選擇有兩條標准簡單和均勻

　　簡單指散列函數的計算簡單快速;

　　均勻指對於關鍵字集合中的任一關鍵字散列函數能以等概率將其映射到表空間的任何一個位置上也就是說散列函數能將子

　　集K隨機均勻地分布在表的地址集{…m}上以使沖突最小化

　　常用散列函數

　　為簡單起見假定關鍵字是定義在自然數集合上

　　()平方取中法

　　具體方法先通過求關鍵字的平方值擴大相近數的差別然後根據表長度取中間的幾位數作為散列函數值又因為一個乘積的中

　　間幾位數和乘數的每一位都相關所以由此產生的散列地址較為均勻

　　【例】將一組關鍵字()平方後得

　　()

　　若取表長為則可取中間的三位數作為散列地址集

　　()

　　相應的散列函數用C實現很簡單

　　int Hash(int key){ //假設key是位整數

　　key*=key; key/=; //先求平方值後去掉末尾的兩位數

　　return key%; //取中間三位數作為散列地址返回

　　}

　　()除余法

　　該方法是最為簡單常用的一種方法它是以表長m來除關鍵字取其余數作為散列地址即 h(key)=key%m

　　該方法的關鍵是選取m選取的m應使得散列函數值盡可能與關鍵字的各位相關m最好為素數

　　【例】若選m是關鍵字的基數的冪次則就等於是選擇關鍵字的最後若干位數字作為地址而與高位無關於是高位不同而低位相

　　同的關鍵字均互為同義詞

　　【例】若關鍵字是十進制整數其基為則當m=時…等均互為同義詞

　　()相乘取整法

　　該方法包括兩個步驟首先用關鍵字key乘上某個常數A(

　　

　　該函數的C代碼為：

　　int Hash(int key){

　　double d=key *A; //不妨設A和m已有定義

　　return (int)(m*(d-(int)d));//(int)表示強制轉換後面的表達式為整數

　　}

　　(4)隨機數法

　　選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址，即

　　h(key)=random(key)

　　其中random為偽隨機函數，但要保證函數值是在0到m-1之間。TW.wInGWiT.cOM

From:http://tw.wingwit.com/Article/program/sjjg/201311/23686.html