Hash函數及其應用

計算理論中，沒有Hash函數的說法，只有單向函數的說法。所謂的單向函數，是一個複雜的定義，大家可以去看計算理論或者密碼學方面的數據。用“人類”的語言描述，單向函數就是：如果某個函數在給定輸入的時候，很容易計算出其結果來；而當給定結果的時候，很難計算出輸入來，這就是單向函數。各種加密函數都可以被認為是單向函數的逼近。Hash函數（或者稱為散列函數）也可以看成是單向函數的一個逼近。即它接近於滿足單向函數的定義。

Hash函數還有另外的含義。實際中的Hash函數是指把一個大範圍映射到一個小範圍。把大範圍映射到一個小範圍的目的往往是為了節省空間，使得數據容易保存。除此以外，Hash函數往往應用於查找上。所以，在考慮使用Hash函數之前，需要明白它的幾個限制：

Hash的主要原理就是把大範圍映射到小範圍；所以，你輸入的實際值的個數必須和小範圍相當或者比它更小。不然衝突就會很多。

由於Hash逼近單向函數；所以，你可以用它來對數據進行加密。

不同的應用對Hash函數有著不同的要求；比如，用於加密的Hash函數主要考慮它和單項函數的差距，而用於查找的Hash函數主要考慮它映射到小範圍的衝突率。

由於實現了Hash的數據結構支持隨機讀取（即直接定位，而不需要涉及各類查找算法），檢索效率非常高，成為了很多存儲引擎的首選，著名的有redis、memcache等，但是Hash的特性決定了一些應用場景下的不足：

Hash 索引僅僅能滿足"=","IN"和"<=>"查詢，不能使用範圍查詢。

Hash 索引無法被用來避免數據的排序操作。（即Hash函數並不會自排序，相對的如B樹，本身帶有排序信息，在節點增刪改時按規則維護）

Hash 索引不能利用部分索引鍵查詢。

稍加擴展的話，我們還可以將Hash應用在各種數據分佈式技術中，這方面說的比較多的是“一致性哈希算法”，著名的開源分佈式NoSQL數據庫系統Cassandra就應用了這一算法。

對於數據檢索的低層面應用，主要是各類集合類型。在設計相關類型時，要考慮適當的Hash算法，考慮因素主要是以下幾個方面：

計算Hash值所需的時間。

Hash表長度。

Hash值分佈情況。

數據的查找頻率。

Hash值衝突（重複）的概率。

衝突解決技術可分為兩大類：開散列法（又稱為鏈地址法）和閉散列法（又稱為開發地址法）。可假設實現Hash結構時，數據存放在預先用數組實現的一片連續的地址空間，兩種衝突解決技術的區別在於發生衝突的元素是存儲在這片數組的空間之外（開散列法，一般為附加鏈表形式）還是空間之內（閉散列法）。與閉散列法相比，開散列法有如下優缺點：

開散列法處理衝突無二次聚集現象，因此平均查找時間較短。

由於開散列法中各鏈表上的節點空間是動態申請的，因此適合無法確定表長的情況。

指針需要額外空間，故當記錄規模較小時，閉散列法較為節省空間。

在.NET中，鏈表的各個元素分散於託管堆各處，這會給垃圾回收帶來壓力，影響程序性能。

在C#中，實現了Hash函數的集合類我知道的有兩個：System.Collections.Hashtable和System.Collections.Generic.Dictionary<tkey>，這兩者區別如下：/<tkey>

Hashtable採用閉散列法來解決衝突，而Dictionary採用開散列法來解決衝突。

Hashtable在空間不夠時，會自動擴容，在擴容時會重新計算所有元素的哈希碼和哈希地址，會消耗大量時間進行計算，Dictionary不存在這個問題（自然Dictionary在空間不夠時也要開闢新的空間，不過不需要重新計算和安排原有數據的哈希值和哈希地址，這方面內容可看Dictionary的源碼便一清二楚了。

Hashtable的線程安全包含幾個層次，默認可由多個讀取器線程或一個寫入線程使用；若要允許多線程寫入（在沒有線程讀取的情況下），則需要通過Synchronized方法返回的包裝完成；如果使用一個或多個讀取器以及一個或多個編寫器，則Synchronized包裝不提供線程安全的訪問，此時應使用SyncRoot鎖定集合。（MSDN說了這麼多，然後告訴我說Hashtable是線程安全的，難道不是在玩我？）Dictionary沒這麼複雜，只要Lock(SyncRoot)即可。

ps：關於NoSql，文中涉及了若干NoSql數據庫，博主就在此簡單說下對NoSql的一些個人見解。現在NoSql可謂風生水起，恰如當年web2.0、ajax剛興起的時候，其實都不是非常高深的技術，但卻能打破傳統，一領風騷好多年，所以說技術是其次，思想才是最重要的。ok扯遠了，NoSql和Sql存儲引擎差不多，總歸就那麼幾種，文中說到的Hash是一種，B數是一種，還有LSM樹之類的，頂多在局部稍作改進以適應場景。它們真正的區別在於，NoSql不必非常顧忌數據庫範式的約束，從而極大提高了讀寫速度和擴展能力，比如寫操作不care事務，在每秒寫幾萬幾十萬的數據量下，光這點就能甩Sql幾條街。可以說各類NoSql的爭奇鬥豔，其實都是以取消或部分取消數據庫範式的約束為前提，看似很小的改變，能換來性能的巨大提升，當然這也伴隨著數據冗餘、安全性不高等Sqls深惡痛絕的問題。上帝總是公平的，任何事物都沒有絕對的好壞，就看你把它們用在什麼地方。