Dictionary<,> 索引器中离散键并发写入的线程安全性

Question

假设您有以下代码

var dictionary = new Dictionary<int, object>(capacity: 2500);

var uniqueKeys = Enumerable.Range(0, 1000).ToArray();

Parallel.ForEach(uniqueKeys, key => dictionary[key] = new object());

请注意，所有键都是唯一的，并且字典容量远远超过键的数量。

问题：是否有任何条件会导致此代码不成功？

鉴于当前的实施情况Dictionary<,> 并且不假设未来假设的内部变化，您能提供任何不安全访问的证据吗？

---

备注：这不是.Net中的线程安全Dictionary<int,int>或a 的线程安全的Dictionary<TKey, TValue>重复，我不需要任何人告诉我ConcurrentDictionary，等等。

Answer 1

首先，我想指出，我在最近的项目中遇到了类似的情况，我们有一个带有键 a DateTimes（唯一）的字典，并行处理它，在初始化它之后，我们有时会遇到问题KeyNotFoundException，但我们没有\'不要像你一样预先分配内存。也许问题就可以解决了？让我们谈谈您链接的代码。

\n\n

每次我们遇到有关并发的问题时，我的多线程编程老师总是告诉我们同样的事情：

\n\n

\n

如果此刻有数十亿个线程会怎样？

\n

\n\n

因此，让我们尝试看看Dictionary.
\ndictionary[key] = new object()引导我们到

\n\n

set {\n    Insert(key, value, false);\n}\n

\n\n

Insert是主要的添加方法，从类中的许多地方调用Dictionary。当您声明对象是唯一的时，我假设那里不会发生哈希冲突，并且不会覆盖方法第一个循环中的值，所以让我们看看其余的代码：

\n\n

int index;\nif (freeCount > 0) {\n    index = freeList;\n    freeList = entries[index].next;\n    freeCount--;\n}\nelse {\n    if (count == entries.Length)\n    {\n        Resize();\n        targetBucket = hashCode % buckets.Length;\n    }\n    index = count;\n    count++;\n}\n

\n\n

当您使用容量初始化字典时2500，else在这种情况下子句似乎根本没有被调用，所以让我们检查一下if部分：\n\n1. if (freeCount > 0) {\n2. // atomic assign\n3. index = freeList;\n4. // some calculation and atomic assign\n5. freeList = entries[index].next;\n6. // not threadsafe operation\n7. freeCount--;\n8. }

\n\n

看起来我们这里有多个多线程问题：

\n\n

\n
1. freeList并且freeCount字段不是volatile，因此读/写它可能容易出错。
\n

2. 如果此时此刻有数十亿个线程会怎样？: \xc2\xa9
   \n 3. index = freeList;
   \n数十亿个线程将获得相同的索引，因为该字段的读写之间没有同步freeList！之后，他们将通过竞争条件覆盖彼此的值：

   \n\n

   entries[index].hashCode = hashCode;\nentries[index].next = buckets[targetBucket];\nentries[index].key = key;\nentries[index].value = value;\nbuckets[targetBucket] = index;\nversion++;\n

\n
3. decrement操作不是线程安全的（来自 @EricLippert 的非常有趣的答案），因此我们的字典状态可能会损坏。
\n
4. 如果此时此刻有数十亿个线程会怎样？: \xc2\xa9
   \n 5. freeList = entries[index].next;
   \n某个线程将freeList值放入index变量中，假设我们在5那里（条目包含其中的链表，头等于-1）并成为在覆盖之前处于非活动状态freeList。数十亿个线程逐个推进链表位置，现在我们的第一个线程开始活动。他很高兴地用过freeList时的数据覆盖了 ，在链表中创建了一个幽灵，并且那里的数据可以被覆盖。
\n

\n\n

因此，在代码执行过程中可能会发生很多问题，我个人不建议您Dictionary在这种情况下使用类。

\n