.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字典的两倍.A Dictionary<Byte, T>比使用Ints快50%.这使我相信,一个字典是做一个O(log n)的二进制搜索来查找键,按键上的比较运营商的瓶颈.出于某种原因,我不相信这是实现为哈希表,因为.NET已经有一个Hashtable类,在我的经验,它比字典还要慢.

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

麦克风

Answer 1

字典是使用哈希表实现的,我稍后使用Reflector查看了代码.

"字典很可能只有大约10个桶,但每个桶可以指向大约2,000个可能的东西中的一个."

有你的问题.字典使用散列来定位存储桶,但存储桶中的查找是线性的.

您必须实现具有更好分布的哈希算法才能获得更好的性能.这种关系应至少相反,即2000桶,每桶10件.