• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

浅析C#中 ConcurrentDictionary的实现

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

简单画了一张图 (灵魂画手 →_→)

如图 ConcurrentDictionary 其中有个tables 对象主要存储,而这个 tables 是一个 很多区块的 数组 ,每个区块 又是一个node的链表 (ps: 一个node 就是一个key value 对)

具体实现如下(ps 代码摘自 net4.5):

   private volatile ConcurrentDictionary<TKey, TValue>.Tables m_tables;

 private class Tables
    {
      internal readonly ConcurrentDictionary<TKey, TValue>.Node[] m_buckets;
      internal readonly object[] m_locks;
      internal volatile int[] m_countPerLock;
      internal readonly IEqualityComparer<TKey> m_comparer;

      internal Tables(ConcurrentDictionary<TKey, TValue>.Node[] buckets, object[] locks, int[] countPerLock, IEqualityComparer<TKey> comparer)
      {
        this.m_buckets = buckets;
        this.m_locks = locks;
        this.m_countPerLock = countPerLock;
        this.m_comparer = comparer;
      }
    }

    private class Node
    {
      internal TKey m_key;
      internal TValue m_value;
      internal volatile ConcurrentDictionary<TKey, TValue>.Node m_next;
      internal int m_hashcode;

      internal Node(TKey key, TValue value, int hashcode, ConcurrentDictionary<TKey, TValue>.Node next)
      {
        this.m_key = key;
        this.m_value = value;
        this.m_next = next;
        this.m_hashcode = hashcode;
      }
    }

看 这个Node类是一个带next 指针的结构 ,一个node就是链表  ,而Tables类中 m_buckets 变量便是一个 存储了n个链表的列表结构

其中Tables类中有个变量名为 countPerLock 类型为 int[] 便是图中最下面那个框 这个,这个变量 主要是用来 统计字典中数据的个数 ,这个 countPerLock 与m_buckets 数量 一一对应,一个node对应countPerLock 中的一个元素。Count()这个方法便是主要使用这个元素经行统计。这样的好处是不用遍历node链表。

最重要的是Tables 中m_locks的实现。 这是一个锁的列表 其中用来控制 多线程读取修改时 控制的区块 。

当字典初始化的时候 m_locks 的数量为 cpu内核数*4(ps:例如i7 就是8*4=32) 而  m_buckets 数量初始化是31(有个小条件是m_locks>=m_buckets 时 m_locks=m_buckets) 所以i7 下 m_buckets 和 m_locks 都是32个 ,理论上再,不添加新节点的时候 一个区块对应 一个锁。

m_locks 初始化时是默认值是 cpu内核数*4  最大值是 1024个

m_buckets初始化默认值 31  最大值是2146435071

也就是说 如果字典中数据量大的时候 是一个锁对象 对应n个Node链表。

 

关于ConcurrentDictionary中所有读取操作

例如Keys Values Count 这类的属性 会对锁定 m_locks 中所有的锁对象 所以需要谨慎使用。

而常用的索引器[]和 TryGetValue 等方法 未锁定任何锁对象,并通过 Volatile.Read 原子性读取 对应的Node链表 遍历中所有元素 直到找到 对应的key 为止。

 

关于ConcurrentDictionary中所有写操作

当添加一个新数据时 方法会计算key的hashcode  是放到哪个node里表中 然后锁定对应的锁对象,自后 通过 Volatile.Write 方法 替换新的Node的指向 , 这时node为新的值 它的next 指向原先的Node值。

 private void GetBucketAndLockNo(int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount)
    {
      bucketNo = (hashcode & int.MaxValue) % bucketCount; //Node的位置
      lockNo = bucketNo % lockCount; // 锁位置
    }  

Volatile.Write<ConcurrentDictionary<TKey, TValue>.Node>(ref tables.m_buckets[bucketNo], new ConcurrentDictionary<TKey, TValue>.Node(key, value, hashCode, tables.m_buckets[bucketNo]));

 

 

为什么这么设计?

对于多线程 这种多个链表 多个锁对象 可以提升 多个线程同时操作的可能性 ,因为很大的程度上写操作的数据  并不是一个锁对象负责的。

同时链式的存储 对于添加对象而言 内存的操作更方便

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C# 用鼠标框选屏幕一个范围进行录屏发布时间:2022-07-14
下一篇:
C#、ASP.NET获取当前应用程序的绝对路径发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap