HashTable 和Dictionary資料結構比較

 

from https://dotblogs.com.tw/sunnylearning/2018/05/17/144428

HashTable 和Dictionary資料結構比較
Hashtable和Dictionary從資料結構上來說都屬於Hashtable（雜湊表），都是對關鍵字（鍵值）進行散列操作，將關鍵字散列到Hashtable的某一個槽位中去，不同的是處理碰撞的方法。 散列函數有可能將不同的關鍵字散列到Hashtable中的同一個槽中去，這個時候我們稱發生了碰撞，為了將資料插入進去，我們需要另外的方法來解決這個問題。
碰撞處理方法比較
Dictionary	鏈表法
HashTable	開放定址法(open addressing)-中雙重散列方法
使用時機比較
Dictionary	資料修改動作很多時。 說明:因為解決碰撞的方式是List.Add
HashTable	資料查詢的動作很多時。 說明:因為映射查找之後，只需要跳躍查找到，碰撞後移動資料即可，另外當增加資料太多時，開放定址的擴充很耗費性能。
Dictionary & HashTable使用比較
1單執行緒程式中	推薦使用Dictionary，有泛型優勢，且讀取速度較快，容量利用更充分.
2多執行緒程式中	多執行緒程式中推薦使用Hashtable，默認的Hashtable允許單執行緒寫入，多執行緒讀取，對Hashtable進一步調用Synchronized()方法可以獲得完全執行緒安全的類型。而Dictionary非執行緒安全，必須人為使用lock語句進行保護，效率大減。

 

Dictionary和HashTable使用比較

單執行緒程式中推薦使用Dictionary，有泛型優勢，且讀取速度較快，容量利用更充分。 多執行緒程式中推薦使用Hashtable，默認的Hashtable允許單執行緒寫入，多執行緒讀取，對Hashtable進一步調用Synchronized()方法可以獲得完全執行緒安全的類型。而Dictionary非執行緒安全，必須人為使用lock語句進行保護，效率大減。 Dictionary有按插入順序排列資料的特性(注:但當調用Remove()刪除過節點後順序被打亂)，因此在需要體現順序的情境中使用Dictionary能獲得一定方便. //Dic遍歷時  會採用插入時的遍歷，而hashTable採用遍歷時則是打亂的Hashtable類和Dictionary<TKey, TValue>泛型類實現IDictionary介Dictionary<TKey, TValue> 泛型類還實現 IDictionary<TKey, TValue>泛型介面。 因此，這些集合中的每個元素都是一個鍵/值對。 Dictionary<TKey, TValue> 類與 Hashtable 類的功能相同對於數值型別，特定類型（不包括 Object）的 Dictionary<TKey, TValue> 的性能優於 Hashtable，這是因為 Hashtable 的元素屬於 Object  類型，所以在存儲或檢索數值型別時通常發生裝箱和取消裝箱操作。

 

Dictionary和List<T>資料結構比較

List<T>是對陣列做了一層包裝，我們在資料結構上稱之為線性表，而線性表的概念是，在記憶體中的連續區域，除了首節點和尾節點外，每個節點都有著其唯一的前驅結點和後續節點。我們在這裡關注的是連續這個概念。 而HashTable或者Dictionary，他是根據Key而根據Hash演算法分析產生的記憶體位址，因此在宏觀上是不連續的，雖然微軟對其演算法也進行了很大的優化。 由於這樣的不連續，在遍歷時，Dictionary必然會產生大量的記憶體換頁操作，而List只需要進行最少的記憶體換頁即可，這就是List和Dictionary在遍歷時效率差異的根本原因。 所以根據value 的查找 dictionary的效率是高於 List 的 但是遍歷的話   則Dic 要差點。這就好比你要摘抄書裡邊的所有文字  是根據目錄 查一個找一篇文章 快，還是直接從正文開始 從頭到尾快遍歷快一樣。單獨的找某一篇知道題目(key)的文章 當然是從目錄快了

 

再談Dictionary

也許很多人說，既然Dictionary如此強大，那麼我們為什麼不用Dictionary來代替一切集合呢？ 在這裡我們除了剛才的遍歷問題，還要提到Dictionary的存儲空間問題，在Dictionary中，除了要存儲我們實際需要的Value外，還需要一個輔助變數Key，這就造成了記憶體空間的雙重浪費。 而且在尾部插入時，List只需要在其原有的位址基礎上向後延續存儲即可，而Dictionary卻需要經過複雜的Hash計算，這也是性能損耗的地方。

 

List<T>和DataTable性能比較

二進位序列化的情況 IList<T>序列化的檔大小比DataTable小得多，這意味著在資料傳輸中頻寬佔用小很多，所以在設計Remoting介面時儘量使用IList<T>作返回值。 XML序列化的情況 IList<T>序列化後的檔比同樣比DataTable小，但差距已經沒有二進位序列化那麼明顯了。而且IList<T>的二進位序列化和XML序列化相差很大，所以remoteing中建議使用二進位序列化。

 

操作性比較

DataTable有支援資料的提交、回滾、查詢等強大的方法，但訪問儲存格內容的時候不方便，還要類型轉換。   IList<T>則訪問項的屬性比較方便，有屬性自動提示，不用類型轉換，有LINQ的協助也能實現強大的查詢。