Hashtable expand [http://www.]private void expand() { int prime = HashHelpers.GetPrime(this.buckets.Length * 2); this.rehash(prime); } private void rehash(int newsize) { this.occupancy = 0; Hashtable.bucket[] newBuckets = new Hashtable.bucket[newsize]; for (int i = 0; i < this.buckets.Length; i ) { Hashtable.bucket bucket = this.buckets[i]; if ((bucket.key != null) && (bucket.key != this.buckets)) { this.putEntry(newBuckets, bucket.key, bucket.val, bucket.hash_coll & 0x7fffffff); } } Thread.BeginCriticalRegion(); this.isWriterInProgress = true; this.buckets = newBuckets; this.loadsize = (int) (this.loadFactor * newsize); this.UpdateVersion(); this.isWriterInProgress = false; Thread.EndCriticalRegion(); }HashTable數(shù)據(jù)結(jié)構(gòu)存在問題：空間利用率偏低、受填充因子影響大、擴(kuò)容時(shí)所有的數(shù)據(jù)需要重新進(jìn)行散列計(jì)算。雖然Hash具有O(1)的數(shù)據(jù)檢索效率，但它空間開銷卻通常很大，是以空間換取時(shí)間。所以Hashtable適用于讀取操作頻繁，寫入操作很少的操作類型。

文章來自學(xué)IT網(wǎng)：http://www./cshare/show-6804-2.aspx

而Dictionary<K, V> 也是用的Hash算法，通過數(shù)組實(shí)現(xiàn)多條鏈?zhǔn)浇Y(jié)構(gòu)。不過它是采用分離鏈接散列法。采用分離鏈接散列法不受到裝填因子的影響，擴(kuò)容時(shí)原有數(shù)據(jù)不需要重新進(jìn)行散列計(jì)算。
采用分離鏈接法的 Dictionary<TKey, TValue> 會(huì)在內(nèi)部維護(hù)一個(gè)鏈表數(shù)組。對(duì)于這個(gè)鏈表數(shù)組 L0,L1,...，LM-1, 散列函數(shù)將告訴我們應(yīng)當(dāng)把元素 X 插入到鏈表的什么位置。然后在 find 操作時(shí)告訴我們哪一個(gè)表中包含了 X。 這種方法的思想在于：盡管搜索一個(gè)鏈表是線性操作，但如果表足夠小，搜索非?？?事實(shí)也的確如此，同時(shí)這也是查找，插入，刪除等操作并非總是 O(1) 的原因)。特別是，它不受裝填因子的限制。
這種情況下，常見的裝填因子是 1.0。更低的裝填因子并不能明顯的提高性能，但卻需要更多的額外空間。
 Dictionary .ctor [http://www.]public Dictionary() : this(0, null) { } public Dictionary(int capacity, IEqualityComparer<TKey> comparer) { if (capacity < 0) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); } if (capacity > 0) { this.Initialize(capacity); } if (comparer == null) { comparer = EqualityComparer<TKey>.Default; } this.comparer = comparer; } private void Resize() { int prime = HashHelpers.GetPrime(this.count * 2); int[] numArray = new int[prime]; for (int i = 0; i < numArray.Length; i ) { numArray[i] = -1; } Entry<TKey, TValue>[] destinationArray = new Entry<TKey, TValue>[prime]; Array.Copy(this.entries, 0, destinationArray, 0, this.count); for (int j = 0; j < this.count; j ) { int index = destinationArray[j].hashCode % prime; destinationArray[j].next = numArray[index]; numArray[index] = j; } this.buckets = numArray; this.entries = destinationArray; }Dictionary的插入算法：1、計(jì)算key的hash值，并且找到buckets中目標(biāo)桶的鏈?zhǔn)姿饕?、從鏈上依次查找是否key已經(jīng)保存，3、如果沒有的話，判斷是否存在freeList，4、如果存在freeList，從freeList上摘下結(jié)點(diǎn)保存數(shù)據(jù)，否則追加在count位置上。

文章來自學(xué)IT網(wǎng)：http://www./cshare/show-6804-3.aspx

Dictionary Add [http://www.]private void Insert(TKey key, TValue value, bool add) { int freeList; if (key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } if (this.buckets == null) { this.Initialize(0); } int num = this.comparer.GetHashCode(key) & 0x7fffffff; int index = num % this.buckets.Length; for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next) { if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key)) { if (add) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } this.entries[i].value = value; this.version ; return; } } if (this.freeCount > 0) { freeList = this.freeList; this.freeList = this.entries[freeList].next; this.freeCount--; } else { if (this.count == this.entries.Length) { this.Resize(); index = num % this.buckets.Length; } freeList = this.count; this.count ; } this.entries[freeList].hashCode = num; this.entries[freeList].next = this.buckets[index]; this.entries[freeList].key = key; this.entries[freeList].value = value; this.buckets[index] = freeList; this.version ; }buckets數(shù)組保存所有數(shù)據(jù)鏈的鏈?zhǔn)?，Buckets[i]表示在桶i中數(shù)據(jù)鏈的鏈?zhǔn)自?。entries結(jié)構(gòu)體數(shù)組用于保存實(shí)際的數(shù)據(jù)，通過next值作為鏈?zhǔn)浇Y(jié)構(gòu)的向后索引。刪除的數(shù)據(jù)空間會(huì)被串入到freeList鏈表的首部，當(dāng)再次插入數(shù)據(jù)時(shí)，會(huì)首先查找freeList鏈表，以提高查找entries中空閑數(shù)據(jù)項(xiàng)位置的效率。在枚舉器中，枚舉順序?yàn)閑ntries數(shù)組的下標(biāo)遞增順序。
 Dictionary Remove [http://www.]public bool Remove(TKey key) { if (key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } if (this.buckets != null) { int num = this.comparer.GetHashCode(key) & 0x7fffffff; int index = num % this.buckets.Length; int num3 = -1; for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next) { if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key)) { if (num3 < 0) { this.buckets[index] = this.entries[i].next; } else { this.entries[num3].next = this.entries[i].next; } this.entries[i].hashCode = -1; this.entries[i].next = this.freeList; this.entries[i].key = default(TKey); this.entries[i].value = default(TValue); this.freeList = i; this.freeCount ; this.version ; return true; } num3 = i; } } return false; } 而SortedDictionary，MSDN是這樣描述的：
SortedDictionary<(Of <(TKey, TValue>)>) 泛型類是檢索運(yùn)算復(fù)雜度為 O(log n) 的二叉搜索樹，其中 n 是字典中的元素?cái)?shù)。就這一點(diǎn)而言，它與 SortedList<(Of <(TKey, TValue>)>)  泛型類相似。這兩個(gè)類具有相似的對(duì)象模型，并且都具有 O(log n) 的檢索運(yùn)算復(fù)雜度。這兩個(gè)類的區(qū)別在于內(nèi)存的使用以及插入和移除元素的速度：

文章來自學(xué)IT網(wǎng)：http://www./cshare/show-6804-4.aspx

SortedList<(Of <(TKey, TValue>)>)  使用的內(nèi)存比 SortedDictionary<(Of <(TKey, TValue>)>) 少。
SortedDictionary<(Of <(TKey, TValue>)>) 可對(duì)未排序的數(shù)據(jù)執(zhí)行更快的插入和移除操作：它的時(shí)間復(fù)雜度為 O(log n)，而 SortedList<(Of <(TKey, TValue>)>) 為 O(n)。
如果使用排序數(shù)據(jù)一次性填充列表，則 SortedList<(Of <(TKey, TValue>)>) 比 SortedDictionary<(Of <(TKey, TValue>)>) 快。
SortedDictionary<K, V>是按照K有序排列的(K, V)數(shù)據(jù)結(jié)構(gòu)，以紅黑樹作為內(nèi)部數(shù)據(jù)結(jié)構(gòu)對(duì)K進(jìn)行排列保存– TreeSet<T>，紅黑樹是一棵二叉搜索樹，每個(gè)結(jié)點(diǎn)具有黑色或者紅色的屬性。它比普通的二叉搜索樹擁有更好的平衡性。2-3-4樹是紅黑樹在“理論”上的數(shù)據(jù)結(jié)構(gòu)。
2-3-4樹插入算法：類似于二叉搜索樹的插入（插入數(shù)據(jù)插入到樹的葉子結(jié)點(diǎn)） ，如果插入位置是2-結(jié)點(diǎn)或者3-結(jié)點(diǎn)，那么直接插入到當(dāng)前結(jié)點(diǎn)，如果插入位置是4-結(jié)點(diǎn)，需要將當(dāng)前的4-結(jié)點(diǎn)進(jìn)行拆分，然后再執(zhí)行后繼的插入操作。
 SortedDictionary Add [http://www.]public void Add(T item) { if (this.root == null) { this.root = new Node<T>(item, false); this.count = 1; } else { Node<T> root = this.root; Node<T> node = null; Node<T> grandParent = null; Node<T> greatGrandParent = null; int num = 0; while (root != null) { num = this.comparer.Compare(item, root.Item); if (num == 0) { this.root.IsRed = false; ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } if (TreeSet<T>.Is4Node(root)) { TreeSet<T>.Split4Node(root); if (TreeSet<T>.IsRed(node)) { this.InsertionBalance(root, ref node, grandParent, greatGrandParent); } } greatGrandParent = grandParent; grandParent = node; node = root; root = (num < 0) ? root.Left : root.Right; } Node<T> current = new Node<T>(item); if (num > 0) { node.Right = current; } else { node.Left = current; } if (node.IsRed) { this.InsertionBalance(current, ref node, grandParent, greatGrandParent); } this.root.IsRed = false; this.count ; this.version ; } }我們來測(cè)試一下Hashtable、Dictionary和SortedDictionary的插入和查找性能。

文章來自學(xué)IT網(wǎng)：http://www./cshare/show-6804-5.aspx

性能測(cè)試代碼 [http://www.]using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Linq; namespace DictionaryTest { class Program { private static int totalCount = 10000; static void Main(string[] args) { HashtableTest(); DictionaryTest(); SortedDictionaryTest(); Console.ReadKey(); } private static void HashtableTest() { Hashtable hastable = new Hashtable(); Stopwatch watch = new Stopwatch(); watch.Start(); for (int i = 1; i < totalCount; i ) { hastable.Add(i, 0); } watch.Stop(); Console.WriteLine(string.Format("Hashtable添加{0}個(gè)元素耗時(shí)：{1}ms",totalCount, watch.ElapsedMilliseconds)); Console.WriteLine("Hashtable不做查找測(cè)試"); hastable.Clear(); } private static void DictionaryTest() { Dictionary<int, int> dictionary = new Dictionary<int, int>(); Stopwatch watch = new Stopwatch(); watch.Start(); for (int i = 1; i < totalCount; i ) { dictionary.Add(i, 0); } watch.Stop(); Console.WriteLine(string.Format("Dictionary添加{0}個(gè)元素耗時(shí)：{1}ms",totalCount, watch.ElapsedMilliseconds)); watch.Reset(); watch.Start(); dictionary.Select(o => o.Key % 1000 == 0).ToList().ForEach(o => { }); watch.Stop(); Console.WriteLine(string.Format("Dictionary查找能被1000整除的元素耗時(shí)：{0}ms", watch.ElapsedMilliseconds)); dictionary.Clear(); } private static void SortedDictionaryTest() { SortedDictionary<int, int> dictionary = new SortedDictionary<int, int>(); Stopwatch watch = new Stopwatch(); watch.Start(); for (int i = 1; i < totalCount; i ) { dictionary.Add(i, 0); } watch.Stop(); Console.WriteLine(string.Format("SortedDictionary添加{0}個(gè)元素耗時(shí)：{1}ms",totalCount, watch.ElapsedMilliseconds)); watch.Reset(); watch.Start(); dictionary.Select(o => o.Key % 1000 == 0).ToList().ForEach(o => { }); watch.Stop(); Console.WriteLine(string.Format("SortedDictionary查找能被1000整除的元素耗時(shí)：{0}ms", watch.ElapsedMilliseconds)); dictionary.Clear(); } } }最終結(jié)果如圖：
 

文章來自學(xué)IT網(wǎng)：http://www./cshare/show-6804-6.aspx
文章來自學(xué)IT網(wǎng)：http://www./cshare/show-6804-6.aspx