散列函數的構造方法

一個“好”的散列函數一般應考慮下列兩個因素：

1. 計算簡單，以便提高轉換速度；
2. 關鍵詞對應的位址空間分布均勻，以盡量減少沖突。

1 數字關鍵詞的散列函數構造

1.1 直接定址法

取關鍵詞的某個線性函數值為散列位址，即

h(key) = a × key + b (a、b為常數)

位址 h(key)	出生年月（ key ）	人數（attribute）
1900	1285萬
1	1901	1281萬
2	1902	1280萬
……
10	2000	1250萬
	2011	1180萬

根據上表，得出散列函數的構造函數為：h(key)=key-1990

1.2 除留餘數法

散列函數為：h(key) = key mod p

例: h(key) = key % 17

			3	4	5	6	7	8	9		11	12	13	14	15	16
關鍵詞	34	18		20	23		42	27		30

一般，p 取

素數

，這裡：p = Tablesize = 17

1.3 數字分析法

分析數字關鍵字在各位上的變化情況，取比較随機的位作為散列位址

比如：取11位手機号碼

key

的後4位作為位址：

散列函數為：h(key) = atoi(key+7) (char *key)

如果關鍵詞

key

是18位的身份證号碼：

用紅線标出來的是變化比較大的的6位數字，這裡就取這6位數字來組建散列函數

h1(key) = (key[6]-‘0’)×104 + (key[10]-‘0’)×103 +(key[14]-‘0’)×102 + (key[16]-‘0’)×10 + (key[17]-‘0’)

當 key[18] = ‘x’時，身份證最後一位為X

h(key) = h1(key)×10 + 10

當 key[18] 為’0’~’9’時，身份證最後一位為數字

h(key) = h1(key)×10 + key[18]-‘0’

1.4 折疊法

把關鍵詞分割成位數相同的幾個部分，然後疊加

1.5 平方取中法

2 字元關鍵詞的散列函數構造

2.1 一個簡單的散列函數——ASCII碼加和法

對字元型關鍵詞key定義散列函數如下：

h(key) = ( Σkey[i] ) mod TableSize

問題：對于ASCII之和相同的字元串就會沖突，比如a3、 b2、c1；eat、 tea；

2.2 簡單的改進——前3個字元移位法

把字元串的前三個字元取出來，看成27進制種的個位數，十位數，百位數，為什麼使用27，因為有26個字元，考錄空格，就是27。

h(key)=(key[0]×272 + key[1]×27 + key[2]) mod TableSize

問題：

1、仍然沖突：string、 street、strong、structure等等，前三個字元相同；

2、空間浪費：3000/263 ≈ 30%

前三個字元的不同組合在實際使用中大概有3000種可能，我們假設所有的字母（26個英文字母）排列組合有263種情況，散清單隻用到30%。

2.3 好的散列函數——移位法

Index Hash(const char *Key, int TableSize)
{
	unsigned int h = 0;		//散列函數值，初始化為0
	while (*Key != '\0')		//位移映射
		h = (h << 5) + *Key++;
	return h % TableSize;
}
           

3 總結

• 數字關鍵詞的散列函數構造（1、直接定址法 2、除留餘數法 3、數字分析法 4、折疊法 5、平方取中法）
• 字元關鍵詞的散列函數構造（1、ASCII碼加和法 2、前3個字元移位法 3、移位法）