c# - .NET Framework - 有什么方法可以让 Dictionary<> 更快一点？

Question

我正在做 Dictionary<>在 O(n^2) 循环中查找并需要它快得离谱。它不是。有没有人知道如何Dictionary<>实现了吗？在通过探查器运行我的代码并确定字典查找占用了大部分 CPU 时间后，我正在使用一个独立的测试用例测试字典性能。我的测试代码是这样的:

Int32[] keys = new Int32[10] { 38784, 19294, 109574, 2450985, 5, 398, 98405, 12093, 909802, 38294394 };

Dictionary<Int32, MyData> map = new Dictionary<Int32, MyData>();
//Add a bunch of things to map


timer.Start();
Object item;
for (int i = 0; i < 1000000; i++)
{
   for (int j = 0; j < keys.Length; j++)
   {
      bool isFound = map.ContainsKey(keys[j]);
      if (isFound)
      {
         item = map[keys[j]];
      }
   }
}
timer.Stop();

ContainsKey 和 map[] 是两个慢的部分(同样慢)。如果我添加一个 TryGetValue，它的速度几乎与 ContainsKey 相同。这里有一些有趣的事实..

A Dictionary<Guid, T>大约是 Dictionary<Int32, T> 的两倍. Dictionary<String, T>大约是 Guid 字典的两倍。 Dictionary<Byte, T>比使用 Ints 快 50%。这使我相信 Dictionary 正在执行 O(log n) 二进制搜索来查找键，键上的比较运算符是瓶颈。出于某种原因，我不相信它是作为 Hashtable 实现的，因为 .NET 已经有一个 Hashtable 类，而且根据我的经验，它甚至比 Dictionary 还要慢。

我正在构建的词典一次只能由一个线程访问，因此读取锁定不是问题。 RAM 也不是问题。字典很可能只有大约 10 个桶，但每个桶可以指向大约 2,000 个可能的事物中的一个。有没有人对如何加快速度有任何反馈？谢谢!

迈克

Answer 1

字典是使用哈希表实现的，我前段时间看过使用 Reflector 的代码。

"The dictionary will most likely only have about 10 buckets, but each bucket can point to one of about 2,000 possibly things."

这是你的问题。字典使用散列来定位桶，但桶中的查找是线性的。

您必须实现具有更好分布的哈希算法以获得更好的性能。这种关系至少应该是相反的，即 2000 个桶，每个桶有 10 个项目。