談談 Hash Table

在我們編程的世界里數據的基本組織可以說有三種形式。

1. 結構體(或對象)
2. 數組
3. 鏈表

其他任何的數據組織形式都可以看作是這三種數據組織形式的組合變體。

結構體(或對象)可以是基本數據類型或者其他結構體(或對象)的組合。結構體或對象一般用來描述一個復雜數據實體。

數組一般是一組同類型的變量的集合，在內存中表現為一片連續的空間，因為空間是連續的，且每一個數據單元占的內存空間的大小是相等的，所以可以根據地址的偏移對數據元素實現快速訪問，但是當需要插入或者刪除一個元素的時候，則需要對目標元素的之后的所有元素進行移動了。

鏈表的單個節點一般為結構體或者對象，因為鏈表的單個節點除了需要保存數據之外還需要維護它的相鄰節點的關系，如果想獲得鏈表中的某個節點的值，需要從鏈表的頭結點開始遍歷，直到找到需要的東西，而插入或者刪除某個節點的話，需要找到相應的節點，修改其以及其相鄰節點的相關指針的引用即可。

像其他的數據結構，比如 隊列，棧，樹，都可以通過數組或者鏈表來組織，并實現相應的操作功能。

這個世界上沒有十全十美的東西，所以我們要學會取舍。任何技術的實現都沒有最好的只要最合適的，也就說實現的最佳方案是和應用場景息息相關的。
很多時候，我們想對數據進行快速的存取（比如緩存的實現），并用一個key來標記自己存取的數據。我們可以把它叫做key-value的結構。
說到“快速”我們很快想到數組，因為數組可以在O(1)的時間復雜內完成指定位置元素的讀寫操作。
所以在理想狀態，如果一個數組足夠長，且存在一個函數可以將每一個key映射到唯一的一個數組下標，那么我們就可以很完美的解決問題。但往往資源都是有限的，我們沒有那么大的空間，也不能設計一個無比負責的映射算法保證每一個key對應到一個唯一的數組下標。所以我們會選擇一些折中的方案。

hash table便是為解決這類問題而存在的。

Hash或者你可以翻譯成散列或者雜湊，hash操作其本質上就是將一個數據映射成另一個數據，通常情況下原數據的長度比hash后的數據容量大。
這種映射的關系我們叫做哈希函數。

一般情況下 哈希函數的輸入可能的總數要遠遠多于哈希值所能表示的總數，所以就有可能兩個不同的輸入對應同一個哈希值，通常把具有不同關鍵碼而具有相同哈希值的記錄稱作“同義詞”。
在信息安全領域中也經常使用到哈希函數，不過需要使用的是單向哈希函數，就是無法通過哈希的結果反推出輸入，所以經常應用于密碼的加密，傳輸內容的完整性檢查，在安全領域常用的哈希算法有 MD5，SHA1等。
在哈希表的應用中，哈希函數常用余數法進行，也就是通過求模的方式算出哈希值。

哈希表是一種數據結構，實現key-value的快速存取。之前說過數組可以實現快速存取，所以哈希表肯定會使用到數組。在這里，我們把每一個數組的單元叫做一個bucket（桶）。

這里哈希函數的作用就是將key映射到一個存儲地址。所以構造一個哈希表我們得先構造哈希函數。
如果一個key哈希后對應地址中已經存放了值了，這種情況我們叫做哈希沖突（Hash collisions）。
如果存在一個哈希函數，使得每一個輸入都能對應到唯一的一個存儲單元中（沒有沖突），那么這樣的哈希函數我們可以叫它完美哈希函數（Perfect Hash Function，簡稱PHF)。
但為了哈希函數簡單，運行速度快，往往不會使用完美哈希函數。所以沖突肯定會存在的，為了減少沖突，我們希望哈希函數的結果均勻的分布在地址單元的空間中。這樣可以有效的減少沖突。

裝填因子Load factor a=哈希表的實際元素數目(n)/ 哈希表的容量(m) a越大，哈希表沖突的概率越大，但是a越接近0，那么哈希表的空間就越浪費。
一般情況下建議Load factor的值為0-0.7，Java實現的HashMap默認的Load factor的值為0.75，當裝載因子大于這個值的時候，HashMap會對數組進行擴張至原來兩倍大。

既然沖突不可避免，那么我們就必須對沖突進行解決(總不能把之前的內容覆蓋掉把),
解決沖突的方式主要分兩類
開放定址法(Open addressing)這種方法就是在計算一個key的哈希的時候，發現目標地址已經有值了，即發生沖突了，這個時候通過相應的函數在此地址后面的地址去找，直到沒有沖突為止。這個方法常用的有線性探測，二次探測，再哈希。
這種解決方法有個不好的地方就是，當發生沖突之后，會在之后的地址空間中找一個放進去，這樣就有可能后來出現一個key哈希出來的結果也正好是它放進去的這個地址空間，這樣就會出現非同義詞的兩個key發生沖突。


鏈接法(Separate chaining)鏈接法是通過數組和鏈表組合而成的。當發生沖突的時候只要將其加到對應的鏈表中即可。

與開放定址法相比，鏈接法有如下幾個優點：
①鏈接法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
②由于鏈接法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而鏈接法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；
④在用鏈接法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之后填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

當然鏈接法也有其缺點，拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

posted on 2010-10-25 12:57 葉子 閱讀(4177) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構