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,TValue>，這兩者差別如下：

• 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深惡痛絕的問題。上帝總是公平的，任何事物都沒有絕對的好壞，就看你把它們用在什麼地方。

參考資料：

Hash函數的幾種

一緻性雜湊演算法應用及優化(最簡潔明了的教程)

三種基本的存儲引擎比較

NoSQL資料庫探讨之一 － 為什麼要用非關系資料庫？

轉載請注明本文出處：http://www.cnblogs.com/newton/p/4561273.html