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