侧边栏壁纸
博主头像
Komi博主等级

WizMan Komi

  • 累计撰写 30 篇文章
  • 累计创建 43 个标签
  • 累计收到 3 条评论

目 录CONTENT

文章目录

阅读源码:C#中的ConcurrentDictionary为什么能够保证线程安全地插入数据

Komi
2022-09-19 / 1 评论 / 0 点赞 / 49 阅读 / 4,612 字
温馨提示:
内容仅供参考,实际使用需根据自身条件进行调整与删改

什么是ConcurrentDictionary?

Represents a thread-safe collection of key/value pairs that can be accessed by multiple threads concurrently.

简单来说是ConcurrentDictionary类相对于Dictionary类的线程安全版本,位于System.Collections.Concurrent的命名空间下

上源码

TryAdd方法

/// <summary>
/// Attempts to add the specified key and value to the <see cref="ConcurrentDictionary{TKey,
/// TValue}"/>.
/// </summary>
/// <param name="key">The key of the element to add.</param>
/// <param name="value">The value of the element to add. The value can be a null reference (Nothing
/// in Visual Basic) for reference types.</param>
/// <returns>true if the key/value pair was added to the <see cref="ConcurrentDictionary{TKey,
/// TValue}"/>
/// successfully; otherwise, false.</returns>
/// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="T:System.OverflowException">The <see cref="ConcurrentDictionary{TKey, TValue}"/>
/// contains too many elements.</exception>
public bool TryAdd(TKey key, TValue value)
{
    if (key == null) ThrowKeyNullException();
    TValue dummy;
    return TryAddInternal(key, _comparer.GetHashCode(key), value, false, true, out dummy);
}

这里没什么好说的,在Key不为Null的情况下正常将方法委托给了TryAddInternal.
但是需要说下这里给出的各个参数含义

  • key : 也就是需要插入的键
  • _comparer.GetHashCode(key) : bucket中对应Key的位置,也就是hashcode
  • value : 需要插入的值
  • false: 对应下面updateIfExists参数,这里使用false代表只是插入数据
  • true : 对应下面acquireLock参数,会锁住当前的Table
  • out dummy : 这个其实只是作为引用参数返回,也就是插入的值

TryAddInternal

/// <summary>
/// Shared internal implementation for inserts and updates.
/// If key exists, we always return false; and if updateIfExists == true we force update with value;
/// If key doesn't exist, we always add value and return true;
/// </summary>
private bool TryAddInternal(TKey key, int hashcode, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue)
{
    Debug.Assert(_comparer.GetHashCode(key) == hashcode)
    while (true)
    {
        int bucketNo, lockNo
        Tables tables = _tables;
        GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, tables._buckets.Length, tables._locks.Length)
        bool resizeDesired = false;
        bool lockTaken = false;
        try
        {
            if (acquireLock)
                Monitor.Enter(tables._locks[lockNo], ref lockTaken)
            // If the table just got resized, we may not be holding the right lock, and must retry.
            // This should be a rare occurrence.
            if (tables != _tables)
            {
                continue;
            
            // Try to find this key in the bucket
            Node prev = null;
            for (Node node = tables._buckets[bucketNo]; node != null; node = node._next)
            {
                Debug.Assert((prev == null && node == tables._buckets[bucketNo]) || prev._next == node);
                if (hashcode == node._hashcode && _comparer.Equals(node._key, key))
                {
                    // The key was found in the dictionary. If updates are allowed, update the value for that key.
                    // We need to create a new node for the update, in order to support TValue types that cannot
                    // be written atomically, since lock-free reads may be happening concurrently.
                    if (updateIfExists)
                    {
                        if (s_isValueWriteAtomic)
                        {
                            node._value = value;
                        }
                        else
                        {
                            Node newNode = new Node(node._key, value, hashcode, node._next);
                            if (prev == null)
                            {
                                Volatile.Write(ref tables._buckets[bucketNo], newNode);
                            }
                            else
                            {
                                prev._next = newNode;
                            }
                        }
                        resultingValue = value;
                    }
                    else
                    {
                        resultingValue = node._value;
                    }
                    return false;
                }
                prev = node;
            
            // The key was not found in the bucket. Insert the key-value pair.
            Volatile.Write<Node>(ref tables._buckets[bucketNo], new Node(key, value, hashcode, tables._buckets[bucketNo]));
            checked
            {
                tables._countPerLock[lockNo]++;
            
            //
            // If the number of elements guarded by this lock has exceeded the budget, resize the bucket table.
            // It is also possible that GrowTable will increase the budget but won't resize the bucket table.
            // That happens if the bucket table is found to be poorly utilized due to a bad hash function.
            //
            if (tables._countPerLock[lockNo] > _budget)
            {
                resizeDesired = true;
            }
        }
        finally
        {
            if (lockTaken)
                Monitor.Exit(tables._locks[lockNo]);
        }
        //
        // The fact that we got here means that we just performed an insertion. If necessary, we will grow the table.
        //
        // Concurrency notes:
        // - Notice that we are not holding any locks at when calling GrowTable. This is necessary to prevent deadlocks.
        // - As a result, it is possible that GrowTable will be called unnecessarily. But, GrowTable will obtain lock 0
        //   and then verify that the table we passed to it as the argument is still the current table.
        //
        if (resizeDesired)
        {
            GrowTable(tables);
        }
        resultingValue = value;
        return true;
    }
}

这里一步一步来说

  1. 首先再次确认bucket中的hashcode是否等同于传入的hashcode
  2. 进入轮询多次尝试
  3. 新引用Table并获取当前的bucketNo以及lockNo(bucketNo代表当前的Node的位置,lockNo指定的是当前Node匹配的锁)
  4. 初始化resizeDesired以及lockTaken(就是是否将当前的字典进行扩容和是否释放当前锁)
  5. 若acquireLock为true的情况下获得当前锁,进入Moniter.Enter()方法,其实这个方法也就是lock关键字用到的一个地方,将当前的对象锁住
  6. 判断tables是否和_tables引址相同,这里其实是为了防止扩容导致的Tables不相等,但是这种情况算是少见的
  7. 接下来就是将Table中对应的Node进行遍历,查看是否存在当前key,因为updateIfExists为false则当找到对应key的时候,直接返回当前对应的值,返回false
  8. Volatile.Write,这里就是在没有当前key的情况下进行写入,而为什么要使用这个方法呢,主要是为了能够保证线程同步(你也看到了ref关键字),详细参考这里
  9. 之后就是再判断当前的Tables是否需要进行扩容并且释放当前的锁
0

评论区