計劃寫幾篇文章專門介紹HashTable,Dictionary,HashSet,SortedList,List 等集合對象，從內部剖析原理，以便在實際應用中有針對性的選擇使用。 這篇文章先介紹HashTable 。 先例舉幾個問題：1，Hashtable為什麼速度查詢速度快，而添加速度相對慢，且其添加和查詢速度之比相差一個數量等級？ 2，裝填因子（ Load Factor）是什麼，hashtable默認的裝填因子是多少？ 3，hashtable裡的元素是順序排序的嗎？ 4，hashtable內部的數據桶（數組）默認長度多少，其長度為什麼只能是素數？ Hashtable中的數據實際存儲在內部的一個數據桶裡（bucket結構數組），其和普通的數組一樣，容量固定，根據數組索引獲取值。 下面從正常使用Hashtable場景看內部是如何實現的，內部都做了哪些工作。 一，new一個Hashtable，Hashtable ht=new Hashtable(); Hashtable有多個構造函數，常用的是無參構造函數：Hashtable ht=new Hashtable(),在new一個hashtable時，其內部做了如下工作：調用Hashtable(int capacity,float loadFactor),其中capacity為：0，loadFactor為：1，然後初始化bocket數組大小為3，裝載因子為0.72（該值是微軟權衡後給的值）,如下圖所示，該圖截取Reflector 二,向Hashtable添加一個元素，ht.Add("a","123") 1，判斷當前Hashtable :ht的元素個數與bucket數組之比是否超過裝載因子0.72， 1）小於0.72：對a進行哈希取值，然後將得到的值與bucket數組長度進行取模計算，將取模的結果插入到bucket數組對應索引，將“123”賦值其value. 因為哈希值可能會重復(不明白的百度一下)，從而導致地址沖突，Hashtable 采用的是 "開放定址法" 處理沖突, 具體行為是把 HashOf(k) % Array.Length 改為 (HashOf(k) + d(k)) % Array.Length , 得出另外一個位置來存儲關鍵字 "a" 所對應的數據, d 是一個增量函數. 如果仍然沖突, 則再次進行增量, 依此循環直到找到一個 Array 中的空位為止。 2) 大於0.72：對bucket數組進行擴容，a， 新建一個數組（該數組的大小為兩倍於當前容量最小的素數，比如當前數組長度是3，那麼新數組長度為7）。 b，將原來數組元素拷貝到新的數組中，因為bocket數組長度變了，所以需要對所有key重新哈希計算（這是影響hashtable性能的重要因素）。 c， 進行上面a步驟。 三，通過key獲取Hashtable對應的value，var v=ht["a"]; 1) 計算"a"的哈希值。 2）將計算的結果與bocket數組長度進行取模計算，因為哈希值可能會沖突，所以類似定位索引上的key可能與輸入的key不相同，這時繼續查找下一個位置。。。。。 3）取模計算結果即是存儲在bocket數組上"123"的索引。 Hashtable還有很多方法，比如Clear ,Remove ,ContainsKey,ContainsValue等方法，因篇幅有限這裡就不一一介紹了。 寫到這裡來回答一下篇幅開頭的幾個問題。 1，Hashtable查詢速度快是因為內部是基於數組索引定位的，稍微消耗性能的是取KEY的哈希值，添加性能相對查詢慢是因為：a，添加元素時可能會地址沖突，需要重新定位地址 。 b，擴容後 數組拷貝，重新哈希計算舊數組所有key。 2, 裝填因子是Hashtable“已存元素個數/內部bucket數組長度”，這個比值太大會造成沖突概率增大，太小會造成空間的浪費。默認是0.72，該值是微軟經過大量實驗得出的一個比較平衡的值，裝填因子范圍 0.1<loadFactor<1，否則拋出ArgumentOutOfRangeException異常。 3，不是順序的（各位看了文章應該知道為什麼不是順序的了吧？） 4，默認長度是3，我看的是.net framework 4.5版本反編譯的代碼，其他版本的.net framework不確定是不是這個值。為什麼擴容的數組長度一定要是素數呢？因為素數有一個特點，只能被自己和1整除，如果不是素數那麼在進行取模計算的時候可能會出現多個值。 今天就寫到這，有很多不對或不合理的地方希望各位看到了及時指出，本菜鳥知錯就改！！！ 先介紹Hashtable，下篇介紹dictionary，到時綜合分析在項目中選擇使用他們的場景。
