我想知道为什么ConcurrentDictionary getOrAdd随着条目数的增加方法会严重减慢。
我在 3 个嵌套循环中调用它，并打印以记录每个 innest 循环的时间，我可以看到每个 innest 循环的执行时间线性增长，我不知道为什么，因为每个 innest 循环的大小相同。我猜这是一些问题ConcurrentDictionary，但这就是我在这里问的原因。
有什么建议吗？
1 回答
1
这是因为碰撞。ConcurrentDictionary维护一个存储桶列表，由GetHashCode方法返回的结果确定将条目放置在哪个存储桶中。理想情况下，每个条目都应该在单独的存储桶中。然而，在实践中这是不可能的。如果GetHashCode为 2 个不同的键返回相同的值，则会出现冲突，并且越来越多的条目被放置在同一个存储桶中。
在底层，每个存储桶都实现为链表。每次，当检测到冲突时，字典必须扫描一些链表以检查给定条目是否已经存在。这个字典中的元素越多，链表就越长，遍历它们所需的时间就越多。
顺便说一句，标准字典以不同的方式实现，但会以类似的方式运行。可以在此处找到对两种数据结构内部的详细描述
于 2013-12-08T12:49:43.470 回答