數據結構-哈希函數

數據結構-哈希函數

哈希查找

之前的查找算法，時間復雜度為O(n)，或者O(㏒2n)，其效率取決於“比較”的次數。

   即使對於采取排序樹結構的查找表，由於每一次比較的結果，如果關鍵字與數據元素不相等，則有“大於”或者“小於”兩個結果，所以下一步會有兩種可能的方向，因此O(㏒2n)已經是最優了。

哈希表（Hash Table）采取另一種算法，其查找的時間復雜度最快可以達到O(1)，即只要給出關鍵字，立刻就可以查找到該元素。

實際應用中大量采取哈希表的方式，很多編程語言中內置了哈希查找的方式，如java中的HashTable，HashSet等。

基本思想
將記錄的存儲地址和它的關鍵字之間建立一個確定的對應關系；這樣，不經過比較，一次存取就能得到所查元素的查找方法。

  1. 哈希函數(Hash函數)
 f : 關鍵字 → 存儲位置。即，hash函數是指關鍵字與存儲位置（哈希地址）的對應關系，只要給出關鍵字，就可以通過這個函數得到存儲位置。

如：給定一個保存了10個元素的數組
[ 0 1 2 3 4 5 6 7 8 9 ]

如果給定Hash函數f(K)=K mod 10，就可以立刻得到該鍵值對應元素的數組下標

如果給定Hash函數f(K)=K mod 2，則雖然也縮小了查找范圍，但達不到上面函數的效果

哈希函數的沖突

如果不同的鍵值，被Hash函數映射到同樣的一個哈希地址，則稱為沖突（ki?kj，H(ki)=H(kj)）

同義詞：具有相同函數值的兩個不同的關鍵字，稱為該哈希函數的同義詞。

   Hash函數不可能完全避免沖突，只可能盡量減少沖突，或者說，好的Hash函數能將關鍵字映射後得到的哈希地址，盡量均勻地分布

設計Hash表的時候，除了采用好的Hash函數之外，如何有效地處理沖突，也是很重要的一方面

哈希表：

 根據設定的哈希函數H(key)和處理沖突的方法，將一組關鍵字映射到一個有限的連續的地址區間上，並以關鍵字的映像作為記錄在表中的存儲位置。

映射過程稱為哈希造表，或者散列（哈希表有時也叫散列表）
所得的存儲位置值稱為哈希地址或者散列地址

哈希函數的構造

   哈希函數是一種映象，其設定很靈活，只要使任何關鍵字的哈希函數值都落在表長允許的范圍之內即可。哈希函數“好壞”的主要評價因素有：

◆ 散列函數的構造簡單；
◆ 關鍵字經哈希函數映射後，得到的地址是等概率的，即“均勻”的，這樣的Hash函數稱為“均勻的哈希函數”

好的Hash函數，可以減少關鍵字的沖突。

直接定址法：取關鍵字或者關鍵字的某個線性函數作為Hash地址，即：
    H(key) = key
    H(key) = a×key + b，a、b為常數
特點：直接定址法所得地址集合與關鍵字集合大小相等，不會發生沖突，但實際中很少使用，因為需事先知道關鍵字的分布情況。
數字分析法：取關鍵字的若干位或組合作為哈希地址
平方取中法：將關鍵字平方後取中間幾位作為哈希地址
折疊法：將關鍵字分割成位數相同的幾部分(最後一部分可以不同)，然後取這幾部分的疊加和作為哈希地址

除留余數法（取模）
    把關鍵字對某個數p（不大於哈希表的表長m）取模，所得到的數作為哈希地址
     H(key) = key MOD p, p≤m

    利用這種方法的關鍵是p的選取，p選的不好，容易產生同義詞。
     根據經驗：若散列表表長為m，通常p為小於或等於表長（最好接近表長m）的 質數；或不包含小於20質因子的合數（如：23*29）。

隨機數法
    H(key) = random(key)，把產生的隨機數做為哈希地址。
     當散列表中關鍵字長度不等時，該方法比較合適。

哈希函數只能使哈希地址均勻分布，但不能避免沖突，因此沖突處理是不可避免的

    構造若干個哈希函數，當發生沖突時，利用不同的哈希函數再計算下一個新哈希地址，直到不發生沖突為止。即：Hi=RHi(key)     i=1, 2, …, k
    RHi ：一組不同的哈希函數。第一次發生沖突時，用RH1計算，第二次發生沖突時，用RH2計算…依此類推知道得到某個Hi不再沖突為止。