實際開發中Hashtable的特性原理.NET, JAVA, PHP

.Net - HashTable特性原理 轉貼自http://blog.csdn.net/arturya/archive/2006/08/19/1096139.aspx

原作者 arturya

Hashtable是現代大多數程序員居家旅行,不可不備的利器.如ASP.NET程序員天天要打交道的Application Items, Cache Items均由Hashtable實現.日常存儲配置參數,數據列,我們也會用到Hashtable或是基於其的結構如NameValueCollection等等, .NET 2.0推出後更增加了一個System.Collections.Generic.Dictionary,用法乍一看和Hashtable差不多,甚至還有泛型的優勢.那麼是否能說Dictionary將會取代Hashtable? Hashtable是如何實現的?究竟適用於哪些場合?有何優劣值得玩味之處? Microsoft官方文檔交待得不甚明確.我們不妨自己來進行一些初步研究.同時也結合Java和PHP中的實現做一些比較.



從狹義上來看, Hashtable可以是一種具體類型名稱,比如.NET中的System.Collections.Hashtable類,或是JAVA中的java.util.Hashtable類.從廣義上來看,她指的是一種數據結構,即哈希表,她牽涉了多種具體類型,像HashMap,文章開頭提到的Dictionary等等雖然稱謂五花八門,都屬於哈希表的範疇.下文中將出現的名詞Hashtable,除非特別說明,也是指廣義上的哈希表.



哈希表的原始定義和基本原理各種數據結構教程上都有闡述.簡而言之,哈希表之所以能夠實現根據關鍵字(典型的例子是一個字符串鍵值)來獲取記錄,是因為她在內部建立了記錄存儲位置-即內部數組中的索引號和關鍵字的一套對應關係f,因而在查找時,只需根據這個映射關係f找到給定鍵值K對應的數f( K),就可直接從數組中取得目的數據Hashtable[K] = Hashtable.InternalArray[f(K)],而不必對數組進行遍歷和比較.這個對應關係f我們稱為哈希函數.



哈希函數f的兩個重要特點:

[1]哈希函數可以自定義,只要使得整數f(K)的範圍不超出哈希表內部存儲數組的上下界即可.

[2] K的取法有任意種,但f(K)只能固定在一個範圍,因此不同的關鍵字可能對應了相同的哈希值,形成了衝突.



需要注意的是哈希函數的運算和衝突的處理都需要係統開銷,尤其後者代價不菲.因此產生了兩個關鍵問題:如何設計函數f的算法,以及如何處理衝突,才能使得哈希表更加高效.



不同語言,不同運行環境的解決方案都有所不同,思路上甚至差別很大.比如.NET的System.Collections.Hashtable和Java的java.util.Hashtable雖然稱呼完全一樣,但內部算法是不盡相同的,應此也產生了使用性能的差異.



這裡我們選擇幾個常見的實例來深入分析:

[1] .NET 2.0, System.Collections.Hashtable

[2] .NET 2.0, System.Collections.Generic.Dictionary<K, V>

[3] Java, java.util.HashMap (java.util.Hashtable的輕量級實現)

[4] PHP5, PHP是弱類型語言, Hashtable對編程者是透明的,在後台運行時實現.



注:以上.NET源代碼來自Reflector反編譯, Java源代碼參見jdk, PHP源代碼參見PHP sdk.同時為便於說明,下文采用了部分偽代碼.



.NET中的System.Collecitons.Hashtable (以下簡稱Hashtable)是一種忠於傳統的實現,很有代表風格.各類數據結構的教科書上一般就是採用類似的原理作為開篇教學. (當然書中的要簡單,原始得多,離現實還有一定差距)



Hashtable中的實際數據都存儲在一個內部Array中(當然和普通數組一樣,有固定容量,上下標,以數字索引存取),當用戶希望取得Hashtable[K]值的時候, Hashtable進行如下處理:



[1]為了保證f(K)的取值範圍在0 <= f(K) < Array.Length,函數f的關鍵步驟是取模運算,算得實際數據存儲位置為f(K) = HashOf(K ) % Array.Length,至於這個HashOf(K)怎麼算出來的,簡單舉例來說她可以取關鍵字的ASCII碼根據一定規則運算得到.



[2]如果發生多個K值的哈希值重複,即f(K1) = f(K2),而f(K1)位置已經有數據佔用了, Hashtable採用的是"開放定址法"處理衝突,具體行為是把HashOf(K2) % Array.Length改為(HashOf(K2) + d(K2)) % Array.Length ,得出另外一個位置來存儲關鍵字K2所對應的數據, d是一個增量函數.如果仍然衝突,則再次進行增量,依此循環直到找到一個Array中的空位為止.將來查找K2的時候先搜索HashOf(K2)一檔,發現不是K2,那麼增量d(K2)繼續搜索,直到找到為止.連續衝突次數越多,搜索次數也越多,效率越低.


[3]當插入數據量達到Hashtable容量上限時,對內部Array進行擴容(重新new一個更大的數組,然後把數據copy過去),不僅如此,由於Array.Length發生了變化,擴容後要對所有現存數據重新計算f(K).所以說擴容是個耗能比較驚人的內部操作. Hashtable之所以寫入效率僅為讀取效率的1/10數量級,頻繁的擴容是一個因素.



f(K)的取法是哈希表的關鍵所在,從根本上決定了該哈希表的許多重要特徵,例如.NET中System.Collections.Hashtable的哈希函數f其算法決定了這樣一些方面:



[1]數組容量Array.Length越大,衝突的機會越小.由於f(K)的取值範圍等於Array.Length,因此隨著Array.Length的增長, f(K)的值也更加多樣性,不容易重複.



[2]數組容量Array.Length期望是一個"比較大的質數",這樣f(K) = HashOf(K) % Array.Length取模運算之後得出的數衝突機會較小.想像一個極端例子,假設Array.Length = 2,則只要HashOf(K)是偶數, f(k)都為0.所以說哈希表的實際容量一般都是有規律的,和數組不一樣,不能任意設置.



[3]隨著插入的數據項逐漸增多, Hashtable內部數組剩餘的空位也越來越少,下一次沖突的可能性也越來越多嚴重影響效率.因此不能等到數組全部塞滿後才進行擴容處理.在.NET中,當插入數據個數和數組容量之比為0.72時,就開始擴容.這個0.72稱為裝填因子- Load Factor.這是一個要求苛刻的數字,某些時刻將裝填因子增減0.01,可能你的Hashtable存取效率就提高或降低了50%,其原因是裝填因子決定Array.Length, Array.Length影響f(K)的衝突機率,進而影響了性能. 0.72是Microsoft經過長期實驗得出的一個比較平衡的值. (取什麼值合適和f(K)的算法也有關, 0.72不一定適合其他結構的哈希表)



[4] Hashtable的初始容量Array.Length至少為11,再次擴容的容量至少為"不小於2倍於當前容量的一個質數".這裡舉一個例子,方便大家看看Hashtable是多麼浪費空間.



假設以默認方式初始化一個Hashtable,依次插入8個值,由於8 / 0.72 > 11,因此Hashtable自動擴容,新的容量為不小於11 * 2的質數,即23.所以,實際僅有8個人吃飯,卻不得不安排一桌23個座兒的酒席,十分奢侈.避免如此鋪張的途徑是在初始化Hashtable時用帶參構造方式直接指定capacity為17,但即便這樣仍浪費了9個空間.



有心的讀者經過計算,可能會問為什麼不是指定初始容量為13, 13是質數啊, 13 * 0.72 > 8啊.確實理想情況是這樣,但實際上由於動態計算並判斷一個數是否質數需要大量時間,故.NET Hashtable中的capacity值是內部預設的一個數列,只能為3, 7, 11, 17, 23...所以十分遺憾. (注:只有當Array.Length > 0x6DDA89時動態計算擴容容量,正常情況下我們不會存如此多的數據進去)



.NET的Hashtable就是以這種方式來減少衝突,以犧牲空間為代價換取讀寫速度.假設你在實際開發中對內存空間要求很敏感,譬如開發ASP.NET超大型B/S網站時,就十分有必要檢討使用Hashtable的場景需求,有的時候能否換個方式,採取自定義struct,或者數組來高效實現呢?

上一篇談到.NET的Hashtable屬於比較傳統的算法.並籍此復習了哈希表這種數據結構的經典原理.下面我們來看看Java和PHP中又是如何實現Hashtable的.之所以把Java和PHP的場景結合一起,是因為他們倆的處理方式非常相似.論述將以java.util.HashMap為主,該原理同樣也適於PHP. HashMap是java.util.Hashtable的輕量級實現,且允許NULL作為關鍵字.



通過前文,我們已知由於.NET Hashtable哈希函數f(K)的取模運算特徵決定了其容量大小必然是某個質數(若不明白請回顧第一篇).而Java HashMap則恰恰相對,她們要求哈希表的容量是一個偶數,且為2的N次冪.即Array.Length = 2, 4, 8, 16, 32, 64... (轉化為二進制恰好為1111 ... 110形式).這是由於Java HashMap的哈希算法核心為與(&)運算, f(K) = HashOf(K) & (Array.Length - 1),運算時HashOf(K)的高位同0相與被丟棄,低位同1相與被保留,以次保證0 <= f(K) < Array.Length.



HashMap的衝突處理方式也區別於.NET Hashtable的開放定址法,為"鏈地址法".當後插入的K2, K3, K4等與先插入的K1位置衝突時,在K1位置建立一個鍊錶,把K2, K3, K4...另存至鍊錶中,即一個位置可以對應"一串"數據.搜索K2, K3, K4的時候先查找f(K1)位置本身,若不符則順序遍歷鍊錶.這樣處理的好處是不會產生如同.NET Hashtable中開放定址法的二次聚集現象(在探測空位時產生連續衝突).



HashMap也存在一個Load Factor,其值為0.75.我們看到HashMap的衝突處理方式不會產生二次聚集,因此裝填因子可以適當放大一些.其初始默認容量為16,當實際裝入數據和容量之比超過0.75時開始自動擴容,新的容量為原始容量的2倍(32, 64, 128...依此類推).乘2運算通過左移直接實現,沒有.NET那般運算判斷質數的困擾.



PHP的Hashtable構造和Java HashMap基本相通,只是Load Factor值為1.



從理論上來說, .NET Hashtable的平均搜索步長約為-ln(1-x)/x,而Java HashMap的平均搜索步長約為1 + x/2,這裡x為實際裝入數據個數和容量之比,由此看出一個哈希表的平均查找長度為x的函數,且0 <= x < Load Factor,而非插入數據個數N的函數,因此她的查找複雜度為O(1 ).



從實際運算來看,性能評估是比較複雜的事情,不僅僅取決於理論搜索步長,還取決於實際Load Factor的取值, HashOf(K)的效率, Resize()的效率,探測數組和拆鏈裝鏈的效率,甚至函數的壓參傳值這種微小開銷累積起來也對總體性能有可觀的影響.在C#中仿照Java HashMap簡單寫了一個採用鏈地址法的哈希表,初步測試顯示其與.NET原始的Hashtable相比讀取速度較快但寫入較慢,互有勝負.考慮到Hashtable還有線程安全處理,慢一點可以理解,情況要比想像的好.



下面我們從Java回到.NET,介紹一下2.0新推出的System.Collections.Generic.Dictionary<K, V>類型(以下簡稱Dictionary).



Dictionary的用法與Hashtable差不多, f(K)也採用相同的取模算法,但其餘內部結構無論同Hashtable還是HashMap都有很大區別.體現在:

[1] Dictionary沒有Load Factor變量,或可理解為Load Factor = 1,插入數據可以最大限度填滿容量空間.

[2]大體上, Dictionary內的元素有按照先後插入順序排列的特性.區別於Hashtable及HashMap的離散型.



Dictionary內部擁有兩列數組,姑且成為"狀態串"和"數據串",數據串按順序接受插入的數據並加以封裝(封裝了一個next指針,方便今後裝鏈),狀態串以f (K)為索引,存放f(K)到K在數據串內的位置映射.查找時先訪問狀態串找f(K),然後根據映射關係找到數據串中的實際數據.當有多個f (K)重複時,狀態串裡面保留第一個f(K),在數據串內對沖突的數據建立鏈關係.







由圖我們可以看出,數據串忠實按照K1, K2, K3 ...的插入順序排列,直至排滿數據串,這個過程中自然不會發生衝突,衝突只出現在狀態串中,同時,發生衝突時並不需探測空位和挪動數據本身,只需將衝突的數據鏈在一起即可.



Dictionary默認初始大小為3,擴容方式和Hashtable一樣,為不小於當前容量的2倍的一個質數.在速度方面, Dictionary讀取快於Hashtable,但不如用C#自寫的鏈地址法的哈希表,寫入要慢於Hashtable,但快於鏈地址法的哈希表.考慮到Dictionary隱含的裝填因子為1,可以最大限度利用空間,是一種以速度換空間的做法,這個結果是可以接受的.



由於Hashtable和Dictionary同時存在,在使用場景上必然存在選擇性,並不任何時刻都能相互替代.

[1]單線程程序中推薦使用Dictionary,有泛型優勢,且讀取速度較快,容量利用更充分.

[2]多線程程序中推薦使用Hashtable,默認的Hashtable允許單線程寫入,多線程讀取,對Hashtable進一步調用Synchronized()方法可以獲得完全線程安全的類型.而Dictionary非線程安全,必須人為使用lock語句進行保護,效率大減.

[3] Dictionary有按插入順序排列數據的特性(注:但當調用Remove()刪除過節點後順序被打亂),因此在需要體現順序的情境中使用Dictionary能獲得一定方便.



以上分別談到了Hashtable, HashMap和Dictionary三種類型,介紹告一段落,下面增加一些不成熟的觀點:



[1]三種哈希表均允許任意object做關鍵字,但實際使用中我們一般只用string做鍵值,對string做HashOf(string)處理比較單純,速度較快,而對object取HashOf( object)則情況復雜.若想進一步提高速度,可以考慮自定義一個只允許string作為關鍵字的哈希表.



[2] Java HashMap由於f(K)取與運算的特性,每次擴容必須是2倍,沒有價錢可講.但.NET Hashtable和Dictionary的容量理論上只要求是質數,新容量不一定要達到舊容量的2倍以上,因而想進一步提高內存利用率,可以考慮重寫Resize()方法,使得每次擴容變成稍大一點的質數即可.當然這樣一來插入效率會降低,自行取捨.



[3]對Hashtable初始化時直接指定capacity是個好主意,減少了Resize()的次數,降低開銷.