構造哈希表最常用的方法

1. 哈稀函數怎麼建立，

你的問題太不具體,其實建哈希函數不難,要看你用什麼方法,可以參考一下數據結構相關的書,一般上面都會有介紹的.
哈希函數是一個映象，即：將關鍵字的集合映射到某個地址集合上，它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可。哈希表中元素是由哈希函數確定的。
以下是構造哈希函數的5種方法：
1 直接定值法：可以取用關鍵字本身或它的線性函數作為它的哈希地址。
即 H（K）= K 或者 H（K）= aK+b；
2 除留余數法：選取一個不大於哈希表長的正整數P，用P除關鍵字K，所得的余數作為哈希地址。
即 H（K）= K mod P
3 數字分析法：設關鍵字有d位數，選取其中若干位的值構成哈希地址的方法！
4 平方取中法：先計算出K的平方，取K平方的中間幾位作為哈希地址！
5 折疊移位法：將太長的關鍵字盡可能的等長為若干段，然後將幾段的值相加，並將最高位的進位捨去，所得的結果為哈希地址。
我舉個簡單的例子,有一關鍵序列21,35,68,2,54, 用除留余數法構造哈希函數h(k)=k mod p(令p=5)則
k=21,h(k)=21 mod 5=1
k=35,h(k)=0,
k=68,h(k)=3,
k=1,h(k)=2,
k=54,h(k)=4
h(k)就是相應元素的哈希地址,理解了嗎？
因為這個例子比較簡單,沒有產生沖突,若產生沖突,還得用處理沖突的方法,在這里就不多講了！

2. 哈希表的常用方法

散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。
實際工作中需視不同的情況採用不同的哈希函數，通常考慮的因素有：
· 計算哈希函數所需時間
· 關鍵字的長度
· 哈希表的大小
· 關鍵字的分布情況
· 記錄的查找頻率
1. 直接定址法：取關鍵字或關鍵字的某個線性函數值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數（這種散列函數叫做自身函數）。若其中H(key）中已經有值了，就往下一個找，直到H(key）中沒有值了，就放進去。
2. 數字分析法：分析一組數據，比如一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體相同，這樣的話，出現沖突的幾率就會很大，但是我們發現年月日的後幾位表示月份和具體日期的數字差別很大，如果用後面的數字來構成散列地址，則沖突的幾率會明顯降低。因此數字分析法就是找出數字的規律，盡可能利用這些數據來構造沖突幾率較低的散列地址。
3. 平方取中法：當無法確定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然後按需要取平方值的中間幾位作為哈希地址。這是因為：平方後中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的概率產生不同的哈希地址。
例：我們把英文字母在字母表中的位置序號作為該英文字母的內部編碼。例如K的內部編碼為11，E的內部編碼為05，Y的內部編碼為25，A的內部編碼為01, B的內部編碼為02。由此組成關鍵字「KEYA」的內部代碼為11052501，同理我們可以得到關鍵字「KYAB」、「AKEY」、「BKEY」的內部編碼。之後對關鍵字進行平方運算後，取出第7到第9位作為該關鍵字哈希地址，如下圖所示 關鍵字 內部編碼 內部編碼的平方值 H(k)關鍵字的哈希地址 KEYA 11050201 122157778355001 778 KYAB 11250102 126564795010404 795 AKEY 01110525 001233265775625 265 BKEY 02110525 004454315775625 315
4. 折疊法：將關鍵字分割成位數相同的幾部分，最後一部分位數可以不同，然後取這幾部分的疊加和（去除進位）作為散列地址。數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割後的每一部分的最低位對齊，然後相加；間界疊加是從一端向另一端沿分割界來回折疊，然後對齊相加。
5. 隨機數法：選擇一隨機函數，取關鍵字的隨機值作為散列地址，通常用於關鍵字長度不同的場合。
6. 除留余數法：取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞。

3. 數據結構哈希演算法

1，直接定址法：
函數公式：f(key)=a*key+b (a,b為常數)
這種方法的優點是：簡單，均勻，不會產生沖突。但是需要事先知道關鍵字的分布情況，適合查找表較小並且連續的情況。
2，數字分析法：
比如我們的11位手機號碼「136XXXX7887」，其中前三位是接入號，一般對應不同運營公司的子品牌，如130是聯通如意通，136是移動神州行，153是電信等。中間四們是HLR識別號，表示用戶歸屬地。最後四們才是真正的用戶號。
若我們現在要存儲某家公司員工登記表，如果用手機號碼作為關鍵字，那麼極有可能前7位都是相同的，所以我們選擇後面的四們作為哈希地址就是不錯的選擇。
3，平方取中法：
故名思義，比如關鍵字是1234，那麼它的平方就是1522756，再抽取中間的3位就是227作為哈希地址。
4，折疊法：
折疊法是將關鍵字從左到右分割成位數相等的幾個部分(最後一部分位數不夠可以短些)，然後將這幾部分疊加求和，並按哈希表表長，取後幾位作為哈希地址。
比如我們的關鍵字是9876543210，哈希表表長三位，我們將它分為四組，987|654|321|0 ，然後將它們疊加求和987+654+321+0=1962，再求後3位即得到哈希地址為962，哈哈，是不是很有意思。
5，除留余數法：
函數公式：f(key)=key mod p (p<=m)m為哈希表表長。
這種方法是最常用的哈希函數構造方法。
6，隨機數法：
函數公式：f(key)= random(key)。
這里random是隨機函數，當關鍵字的長度不等是，採用這種方法比較合適。
兩種哈希函數沖突解決方法：
我們設計得最好的哈希函數也不可能完全避免沖突，當我們在使用哈希函數後發現兩個關鍵字key1!=key2，但是卻有f(key1)=f(key2)，即發生沖突。