当前位置 : 主页 > 编程语言 > c语言 >

C#创建安全的字典(Dictionary)存储结构

来源:互联网 收集:自由互联 发布时间:2021-06-04
在上面介绍过栈(Stack)的存储结构,接下来介绍另一种存储结构字典(Dictionary)。 字典(Dictionary)里面的每一个元素都是一个键值对(由二个元素组成:键和值) 键必须是唯一的,而值

在上面介绍过栈(Stack)的存储结构,接下来介绍另一种存储结构字典(Dictionary)。 字典(Dictionary)里面的每一个元素都是一个键值对(由二个元素组成:键和值) 键必须是唯一的,而值不需要唯一的,键和值都可以是任何类型。字典(Dictionary)是常用于查找和排序的列表。

  接下来看一下Dictionary的部分方法和类的底层实现代码:

  1.Add:将指定的键和值添加到字典中。

  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> 中移除所有的键和值。

 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> 中移除所指定的键的值。

 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> 的枚举器。

  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)存储结构。有关线程安全的部分,在这里就不再赘述了。

  /// <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();
    }
  }

    以上创建安全的字典方法中,主要对字典的一些方法和属性进行重写操作,对某些方法进行锁设置。

    以上就是本文的全部内容,希望对大家有所帮助,同时也希望多多支持易盾网络!

网友评论