本文部分內容摘自網絡，參考資料鏈接會在文后給出，在此感謝原作者的分享。

計算理論中，沒有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值沖突（重復）的概率。

沖突解決技術可分為兩大類：開散列法（又稱為鏈地址法）和閉散列法（又稱為開發地址法）?？杉僭O實現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的一些個人見解?，F在NoSql可謂風生水起，恰如當年web2.0、ajax剛興起的時候，其實都不是非常高深的技術，但卻能打破傳統，一領風騷好多年，所以說技術是其次，思想才是最重要的。ok扯遠了，NoSql和Sql存儲引擎差不多，總歸就那么幾種，文中說到的Hash是一種，B數是一種，還有LSM樹之類的，頂多在局部稍作改進以適應場景。它們真正的區別在于，NoSql不必非常顧忌數據庫范式的約束，從而極大提高了讀寫速度和擴展能力，比如寫操作不care事務，在每秒寫幾萬幾十萬的數據量下，光這點就能甩Sql幾條街。可以說各類NoSql的爭奇斗艷，其實都是以取消或部分取消數據庫范式的約束為前提，看似很小的改變，能換來性能的巨大提升，當然這也伴隨著數據冗余、安全性不高等Sqls深惡痛絕的問題。上帝總是公平的，任何事物都沒有絕對的好壞，就看你把它們用在什么地方。

參考資料：

Hash函數的幾種

一致性哈希算法應用及優化(最簡潔明了的教程)

三種基本的存儲引擎比較

NoSQL數據庫探討之一 － 為什么要用非關系數據庫？

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