3

我需要创建一个集合集合。该集合由多个线程调用以添加项目和查找项目。一旦添加，项目将不会被删除。目前，在添加元素时，我需要锁定整个集合。有没有办法让它无锁。或者我可以使用更好的数据结构或模式吗？这是我的代码的简化版本：

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>();

void AddUpdateItem(string s, int k, int v)
{
    ConcurrentDictionary<int, int> subDict;
    if (dict.TryGetValue(s, out subDict))
    {
        subDict[k] = v;
    }
    else
    {
        lock (dict)
        {
            if (dict.TryGetValue(s, out subDict))
            {
                subDict[k] = v;
            }
            else
            {
                subDict = new ConcurrentDictionary<int, int>();
                subDict[k] = v;
                dict[s] = subDict;
            }
        }
    }
}
4

5 回答 5

4

您可以通过使用不变性使哈希表无锁，但如果存在争用，它可能不会有效。基本上，您需要一个可以原子交换的字典内容类。您构建当前内容的副本，并进行一次更改，然后使用比较和交换原语将其与现有版本交换。如果比较和交换失败，请从复制步骤重新开始。

您也许可以原子地只交换一个哈希桶，这将使争用变得不那么常见，并且重试成本更低。（ConcurrentDictionary确实已经使用了这种优化，以减少锁争用）但是增加桶的数量仍然需要上面概述的方法。

看看 Eric Lippert 的博客，他在其中介绍了不可变数据结构。他有一个很好的二叉树示例，它应该向您展示制作无锁哈希表所需的技术。

于 2011-10-16T02:58:01.117 回答
3

方法ConcurrentDictionary.GetOrAdd是线程安全的（虽然不是原子的）。它保证返回的对象对于所有线程都是相同的。您的代码可以重写为：

void AddUpdateItem(string s, int k, int v)
{
    var subDict = dict.GetOrAdd(s, _ => new ConcurrentDictionary<int, int>());
    subDict[k] = v;
}
于 2011-10-16T11:16:16.387 回答
1

您是否在代码中使用任务或线程？在任何情况下，ConcurrentDictionary都被设计为线程安全的。添加或删除元素时不需要使用锁。来自 MSDN 的链接How to: Add and Remove Items from a ConcurrentDictionary 解释了如何使用它。

于 2011-10-16T02:49:40.057 回答
0

如果您投机地创建子字典，则有一个更简单的解决方案：

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>();

void AddUpdateItem( string s, int k, int v )
{
    ConcurrentDictionary<int, int> subDict;

    while ( true )
    {
        if ( dict.TryGetValue( s, out subDict ) )
        {
            subDict[ k ] = v;
            break;
        }

        // speculatively create new sub-dictionary
        subDict = new ConcurrentDictionary<int, int>();
        subDict[ k ] = v;

        // this can only succeed for one thread
        if ( dict.TryAdd( s, subDict ) ) break;
    }
}
于 2011-10-16T10:26:58.327 回答
0

在你走上实现无锁集合的道路之前，看看ReadWriteLock可以解决你的问题。如果没有（例如，因为您有大量的写入争用），那么实际上就没有一种万能的方法。

我过去使用的一种技术是拥有一个线程专用线程来管理集合并用于Interlocked.Exchange将新对象编组到该线程并输出不可变集合。使用这种方法，您的编写器线程在一个单独的列表中进行管理，您需要在创建或销毁编写器时锁定该列表，因此这仅适用于罕见事件。

于 2011-10-16T10:53:56.543 回答