在上面介绍过栈（Stack）的存储结构，接下来介绍另一种存储结构字典（Dictionary）。 字典（Dictionary）里面的每一个元素都是一个键值对(由二个元素组成：键和值) 键必须是唯一的,而值不需要唯一的,键和值都可以是任何类型。字典(Dictionary)是常用于查找和排序的列表。
接下来看一下Dictionary的部分方法和类的底层实现代码：
1.Add：将指定的键和值添加到字典中。
1public void Add(TKey key, TValue value) { 2 Insert(key, value, true); 3 } 4 5private void Insert(TKey key, TValue value, bool add) { 6 7 if( key == null ) { 8 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 9 } 10 11 if (buckets == null) Initialize(0); 12 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; 13 int targetBucket = hashCode % buckets.Length; 14 15#if FEATURE_RANDOMIZED_STRING_HASHING 16 int collisionCount = 0; 17#endif 18 19 for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) { 20 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { 21 if (add) { 22 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); 23 } 24 entries[i].value = value; 25 version++; 26 return; 27 } 28 29#if FEATURE_RANDOMIZED_STRING_HASHING 30 collisionCount++; 31#endif 32 } 33 int index; 34 if (freeCount > 0) { 35 index = freeList; 36 freeList = entries[index].next; 37 freeCount--; 38 } 39 else { 40 if (count == entries.Length) 41 { 42 Resize(); 43 targetBucket = hashCode % buckets.Length; 44 } 45 index = count; 46 count++; 47 } 48 49 entries[index].hashCode = hashCode; 50 entries[index].next = buckets[targetBucket]; 51 entries[index].key = key; 52 entries[index].value = value; 53 buckets[targetBucket] = index; 54 version++; 55 56#if FEATURE_RANDOMIZED_STRING_HASHING 57 if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 58 { 59 comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer); 60 Resize(entries.Length, true); 61 } 62#endif 63 64 }
2.Clear()：从 Dictionary<TKey, TValue> 中移除所有的键和值。
1public void Clear() { 2 if (count > 0) { 3 for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; 4 Array.Clear(entries, 0, count); 5 freeList = -1; 6 count = 0; 7 freeCount = 0; 8 version++; 9 } 10 }
3.Remove()：从 Dictionary<TKey, TValue> 中移除所指定的键的值。
1public bool Remove(TKey key) { 2 if(key == null) { 3 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 4 } 5 6 if (buckets != null) { 7 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; 8 int bucket = hashCode % buckets.Length; 9 int last = -1; 10 for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) { 11 if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { 12 if (last < 0) { 13 buckets[bucket] = entries[i].next; 14 } 15 else { 16 entries[last].next = entries[i].next; 17 } 18 entries[i].hashCode = -1; 19 entries[i].next = freeList; 20 entries[i].key = default(TKey); 21 entries[i].value = default(TValue); 22 freeList = i; 23 freeCount++; 24 version++; 25 return true; 26 } 27 } 28 } 29 return false; 30 }
4.GetEnumerator()：返回循环访问 Dictionary<TKey, TValue> 的枚举器。
1public Enumerator GetEnumerator() { 2 return new Enumerator(this, Enumerator.KeyValuePair); 3 } 4 5 [Serializable] 6 public struct Enumerator: IEnumerator<KeyValuePair<TKey,TValue>>, 7 IDictionaryEnumerator 8 { 9 private Dictionary<TKey,TValue> dictionary; 10 private int version; 11 private int index; 12 private KeyValuePair<TKey,TValue> current; 13 private int getEnumeratorRetType; // What should Enumerator.Current return? 14 15 internal const int DictEntry = 1; 16 internal const int KeyValuePair = 2; 17 18 internal Enumerator(Dictionary<TKey,TValue> dictionary, int getEnumeratorRetType) { 19 this.dictionary = dictionary; 20 version = dictionary.version; 21 index = 0; 22 this.getEnumeratorRetType = getEnumeratorRetType; 23 current = new KeyValuePair<TKey, TValue>(); 24 } 25 26 public bool MoveNext() { 27 if (version != dictionary.version) { 28 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 29 } 30 31 // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends. 32 // dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue 33 while ((uint)index < (uint)dictionary.count) { 34 if (dictionary.entries[index].hashCode >= 0) { 35 current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value); 36 index++; 37 return true; 38 } 39 index++; 40 } 41 42 index = dictionary.count + 1; 43 current = new KeyValuePair<TKey, TValue>(); 44 return false; 45 } 46 47 public KeyValuePair<TKey,TValue> Current { 48 get { return current; } 49 } 50 51 public void Dispose() { 52 } 53 54 object IEnumerator.Current { 55 get { 56 if( index == 0 || (index == dictionary.count + 1)) { 57 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 58 } 59 60 if (getEnumeratorRetType == DictEntry) { 61 return new System.Collections.DictionaryEntry(current.Key, current.Value); 62 } else { 63 return new KeyValuePair<TKey, TValue>(current.Key, current.Value); 64 } 65 } 66 } 67 68 void IEnumerator.Reset() { 69 if (version != dictionary.version) { 70 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 71 } 72 73 index = 0; 74 current = new KeyValuePair<TKey, TValue>(); 75 } 76 77 DictionaryEntry IDictionaryEnumerator.Entry { 78 get { 79 if( index == 0 || (index == dictionary.count + 1)) { 80 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 81 } 82 83 return new DictionaryEntry(current.Key, current.Value); 84 } 85 } 86 87 object IDictionaryEnumerator.Key { 88 get { 89 if( index == 0 || (index == dictionary.count + 1)) { 90 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 91 } 92 93 return current.Key; 94 } 95 } 96 97 object IDictionaryEnumerator.Value { 98 get { 99 if( index == 0 || (index == dictionary.count + 1)) { 100 ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 101 } 102 103 return current.Value; 104 } 105 } 106 }
上面主要是对字典(Dictionary)的一些常用方法进行一个简单的说明。接下来主要阐述如何创建安全的字典(Dictionary)存储结构。有关线程安全的部分，在这里就不再赘述了。
1/// <summary> 2 /// 线程安全通用字典 3 /// </summary> 4 /// <typeparam name="TKey"></typeparam> 5 /// <typeparam name="TValue"></typeparam> 6 public class TDictionary<TKey, TValue> : IDictionary<TKey, TValue> 7 { 8 /// <summary> 9 /// 锁定字典 10 /// </summary> 11 private readonly ReaderWriterLockSlim _lockDictionary = new ReaderWriterLockSlim(); 12 13 /// <summary> 14 ///基本字典 15 /// </summary> 16 private readonly Dictionary<TKey, TValue> _mDictionary; 17 18 // Variables 19 /// <summary> 20 /// 初始化字典对象 21 /// </summary> 22 public TDictionary() 23 { 24 _mDictionary = new Dictionary<TKey, TValue>(); 25 } 26 27 /// <summary> 28 /// 初始化字典对象 29 /// </summary> 30 /// <param name="capacity">字典的初始容量</param> 31 public TDictionary(int capacity) 32 { 33 _mDictionary = new Dictionary<TKey, TValue>(capacity); 34 } 35 36 /// <summary> 37 ///初始化字典对象 38 /// </summary> 39 /// <param name="comparer">比较器在比较键时使用</param> 40 public TDictionary(IEqualityComparer<TKey> comparer) 41 { 42 _mDictionary = new Dictionary<TKey, TValue>(comparer); 43 } 44 45 /// <summary> 46 /// 初始化字典对象 47 /// </summary> 48 /// <param name="dictionary">其键和值被复制到此对象的字典</param> 49 public TDictionary(IDictionary<TKey, TValue> dictionary) 50 { 51 _mDictionary = new Dictionary<TKey, TValue>(dictionary); 52 } 53 54 /// <summary> 55 ///初始化字典对象 56 /// </summary> 57 /// <param name="capacity">字典的初始容量</param> 58 /// <param name="comparer">比较器在比较键时使用</param> 59 public TDictionary(int capacity, IEqualityComparer<TKey> comparer) 60 { 61 _mDictionary = new Dictionary<TKey, TValue>(capacity, comparer); 62 } 63 64 /// <summary> 65 /// 初始化字典对象 66 /// </summary> 67 /// <param name="dictionary">其键和值被复制到此对象的字典</param> 68 /// <param name="comparer">比较器在比较键时使用</param> 69 public TDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) 70 { 71 _mDictionary = new Dictionary<TKey, TValue>(dictionary, comparer); 72 } 73 74 75 76 public TValue GetValueAddIfNotExist(TKey key, Func<TValue> func) 77 { 78 return _lockDictionary.PerformUsingUpgradeableReadLock(() => 79 { 80 TValue rVal; 81 82 // 如果我们有值，得到它并退出 83 if (_mDictionary.TryGetValue(key, out rVal)) 84 return rVal; 85 86 // 没有找到，所以做函数得到的值 87 _lockDictionary.PerformUsingWriteLock(() => 88 { 89 rVal = func.Invoke(); 90 91 // 添加到字典 92 _mDictionary.Add(key, rVal); 93 94 return rVal; 95 }); 96 97 return rVal; 98 }); 99 } 100 101 102 /// <summary> 103 /// 将项目添加到字典 104 /// </summary> 105 /// <param name="key">添加的关键</param> 106 /// <param name="value">要添加的值</param> 107 public void Add(TKey key, TValue value) 108 { 109 _lockDictionary.PerformUsingWriteLock(() => _mDictionary.Add(key, value)); 110 } 111 112 /// <summary> 113 ///将项目添加到字典 114 /// </summary> 115 /// <param name="item">要添加的键/值</param> 116 public void Add(KeyValuePair<TKey, TValue> item) 117 { 118 var key = item.Key; 119 var value = item.Value; 120 _lockDictionary.PerformUsingWriteLock(() => _mDictionary.Add(key, value)); 121 } 122 123 /// <summary> 124 /// 如果值不存在，则添加该值。 返回如果值已添加，则为true 125 /// </summary> 126 /// <param name="key">检查的关键，添加</param> 127 /// <param name="value">如果键不存在，则添加的值</param> 128 public bool AddIfNotExists(TKey key, TValue value) 129 { 130 bool rVal = false; 131 132 _lockDictionary.PerformUsingWriteLock(() => 133 { 134 // 如果不存在，则添加它 135 if (!_mDictionary.ContainsKey(key)) 136 { 137 // 添加该值并设置标志 138 _mDictionary.Add(key, value); 139 rVal = true; 140 } 141 }); 142 143 return rVal; 144 } 145 146 /// <summary> 147 /// 如果键不存在，则添加值列表。 148 /// </summary> 149 /// <param name="keys">要检查的键，添加</param> 150 /// <param name="defaultValue">如果键不存在，则添加的值</param> 151 public void AddIfNotExists(IEnumerable<TKey> keys, TValue defaultValue) 152 { 153 _lockDictionary.PerformUsingWriteLock(() => 154 { 155 foreach (TKey key in keys) 156 { 157 // 如果不存在，则添加它 158 if (!_mDictionary.ContainsKey(key)) 159 _mDictionary.Add(key, defaultValue); 160 } 161 }); 162 } 163 164 165 public bool AddIfNotExistsElseUpdate(TKey key, TValue value) 166 { 167 var rVal = false; 168 169 _lockDictionary.PerformUsingWriteLock(() => 170 { 171 // 如果不存在，则添加它 172 if (!_mDictionary.ContainsKey(key)) 173 { 174 // 添加该值并设置标志 175 _mDictionary.Add(key, value); 176 rVal = true; 177 } 178 else 179 _mDictionary[key] = value; 180 }); 181 182 return rVal; 183 } 184 185 /// <summary> 186 /// 如果键存在，则更新键的值。 187 /// </summary> 188 /// <param name="key"></param> 189 /// <param name="newValue"></param> 190 public bool UpdateValueIfKeyExists(TKey key, TValue newValue) 191 { 192 bool rVal = false; 193 194 _lockDictionary.PerformUsingWriteLock(() => 195 { 196 // 如果我们有密钥，然后更新它 197 if (!_mDictionary.ContainsKey(key)) return; 198 _mDictionary[key] = newValue; 199 rVal = true; 200 }); 201 202 return rVal; 203 } 204 205 /// <summary> 206 /// 如果键值对存在于字典中，则返回true 207 /// </summary> 208 /// <param name="item">键值对查找</param> 209 public bool Contains(KeyValuePair<TKey, TValue> item) 210 { 211 return _lockDictionary.PerformUsingReadLock(() => ((_mDictionary.ContainsKey(item.Key)) && 212 (_mDictionary.ContainsValue(item.Value)))); 213 } 214 215 216 public bool ContainsKey(TKey key) 217 { 218 return _lockDictionary.PerformUsingReadLock(() => _mDictionary.ContainsKey(key)); 219 } 220 221 /// <summary> 222 /// 如果字典包含此值，则返回true 223 /// </summary> 224 /// <param name="value">找到的值</param> 225 public bool ContainsValue(TValue value) 226 { 227 return _lockDictionary.PerformUsingReadLock(() => _mDictionary.ContainsValue(value)); 228 } 229 230 231 public ICollection<TKey> Keys 232 { 233 get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary.Keys); } 234 } 235 236 237 public bool Remove(TKey key) 238 { 239 return _lockDictionary.PerformUsingWriteLock(() => (!_mDictionary.ContainsKey(key)) || _mDictionary.Remove(key)); 240 } 241 242 243 public bool Remove(KeyValuePair<TKey, TValue> item) 244 { 245 return _lockDictionary.PerformUsingWriteLock(() => 246 { 247 // 如果键不存在则跳过 248 TValue tempVal; 249 if (!_mDictionary.TryGetValue(item.Key, out tempVal)) 250 return false; 251 252 //如果值不匹配，请跳过 253 return tempVal.Equals(item.Value) && _mDictionary.Remove(item.Key); 254 }); 255 } 256 257 /// <summary> 258 /// 从字典中删除与模式匹配的项 259 /// </summary> 260 /// <param name="predKey">基于键的可选表达式</param> 261 /// <param name="predValue">基于值的选项表达式</param> 262 public bool Remove(Predicate<TKey> predKey, Predicate<TValue> predValue) 263 { 264 return _lockDictionary.PerformUsingWriteLock(() => 265 { 266 // 如果没有键退出 267 if (_mDictionary.Keys.Count == 0) 268 return true; 269 270 //保存要删除的项目列表 271 var deleteList = new List<TKey>(); 272 273 // 过程密钥 274 foreach (var key in _mDictionary.Keys) 275 { 276 var isMatch = false; 277 278 if (predKey != null) 279 isMatch = (predKey(key)); 280 281 // 如果此项目的值匹配，请添加它 282 if ((!isMatch) && (predValue != null) && (predValue(_mDictionary[key]))) 283 isMatch = true; 284 285 // 如果我们有匹配，添加到列表 286 if (isMatch) 287 deleteList.Add(key); 288 } 289 290 // 从列表中删除所有项目 291 foreach (var item in deleteList) 292 _mDictionary.Remove(item); 293 294 return true; 295 }); 296 } 297 298 299 public bool TryGetValue(TKey key, out TValue value) 300 { 301 _lockDictionary.EnterReadLock(); 302 try 303 { 304 return _mDictionary.TryGetValue(key, out value); 305 } 306 finally 307 { 308 _lockDictionary.ExitReadLock(); 309 } 310 311 } 312 313 314 public ICollection<TValue> Values 315 { 316 get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary.Values); } 317 } 318 319 public TValue this[TKey key] 320 { 321 get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary[key]); } 322 323 set { _lockDictionary.PerformUsingWriteLock(() => _mDictionary[key] = value); } 324 } 325 326 /// <summary> 327 /// 清除字典 328 /// </summary> 329 public void Clear() 330 { 331 _lockDictionary.PerformUsingWriteLock(() => _mDictionary.Clear()); 332 } 333 334 335 public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) 336 { 337 _lockDictionary.PerformUsingReadLock(() => _mDictionary.ToArray().CopyTo(array, arrayIndex)); 338 } 339 340 /// <summary> 341 /// 返回字典中的项目数 342 /// </summary> 343 public int Count 344 { 345 get { return _lockDictionary.PerformUsingReadLock(() => _mDictionary.Count); } 346 } 347 348 349 public bool IsReadOnly 350 { 351 get { return false; } 352 } 353 354 355 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() 356 { 357 Dictionary<TKey, TValue> localDict = null; 358 359 _lockDictionary.PerformUsingReadLock(() => localDict = new Dictionary<TKey, TValue>(_mDictionary)); 360 361 return ((IEnumerable<KeyValuePair<TKey, TValue>>)localDict).GetEnumerator(); 362 } 363 364 365 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 366 { 367 Dictionary<TKey, TValue> localDict = null; 368 369 _lockDictionary.PerformUsingReadLock(() => localDict = new Dictionary<TKey, TValue>(_mDictionary)); 370 371 return localDict.GetEnumerator(); 372 } 373 374 }
以上创建安全的字典方法中，主要对字典的一些方法和属性进行重写操作，对某些方法进行锁设置。