.NET框架 - 有没有办法让Dictionary<>变得更快一些？

Question

我正在一个O(n^2)的循环中进行Dictionary<>查找，但速度并不快。有人能解释一下Dictionary<>是如何实现的吗？在通过分析器运行我的代码并确定Dictionary查找占用了大量CPU时间后，我使用隔离测试案例测试Dictionary性能。我的测试代码如下：

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相同。以下是一些有趣的事实…

一个Dictionary<Guid, T>大约比一个Dictionary<Int32, T>慢两倍。Dictionary<String, T>大约比Guid dictionary慢两倍。与使用Ints相比，Dictionary<Byte, T>要快50％左右。这让我相信Dictionary正在做一个O(log n)二进制搜索来查找键，并且键上的比较运算符是瓶颈。出于某种原因，我不认为它被实现为Hashtable，因为.NET已经有一个Hashtable类，在我的经验中它甚至比Dictionary还要慢。

我正在构建的字典每次只能被一个线程访问，所以读取锁定不是问题。RAM也不是问题。字典很可能只有大约10个桶，但是每个桶可以指向约2,000个可能的内容之一。有人有关于如何使其更快的反馈吗？谢谢！

Mike

- Mike Christensen

---

如果我添加一个TryGetValue，它的速度几乎与ContainsKey相同。TryGetValue的速度与ContainsKey相同，但同时返回项，节省了获取值的第二个查找。您没有看到这种改进吗？ - Will

你可以使用.NET反编译器查看实际的实现。但说实话，也许你的算法才是问题所在。你需要执行那么多查询吗？ - siride

Answer 1

这段内容是关于字典实现的技术讨论。使用哈希表来实现字典，这意味着可以很快地找到要找的项。但是，如果桶中有太多元素，那么在桶中查找的时间将会很长。因此，我们需要改进哈希算法来提高性能，至少应该是每个桶只存放10个元素、而总共有2000个桶的比例。

- Guffa

---

+1 - 正是问题所在。哈希算法完全失效了（即：低效且未正确实现）。 - TomTom

所以让我来澄清一下.. 当多个键“哈希”到同一个桶时，字典会变慢，对吗？ 一旦你解决了这个问题，查找就是O(1)？ 这基本上回答了我的问题.. - Mike Christensen

Mike：在你上面的例子中，使用的是 .Net 4.0，map 是一个大小为17的哈希表，其中填充了7个桶。这意味着对于每10个查找的键，将有3个碰撞。在你的情况下，碰撞分别是在第9个桶内的98405、109574以及在第7个桶内的38294394、398和38784。这意味着38784需要3次比较，109574和398需要2次比较，而所有其他查找只需要1次比较。 - Gabe

如果我没记错的话，bucket将会通过hashvalue % n计算出来，其中n是桶的数量，对吗？如果是这样，Dictionary<>如何知道n是多少呢？它是否会在添加更多内容时尝试动态调整n的大小？有没有一种方法可以设置n？我想要防止所有碰撞...在这种情况下，我不关心内存。谢谢！ - Mike Christensen

@Mike：不，它只设置了容量。这会影响实际桶的数量，但这是一个你不应该尝试篡改的实现细节。字典减少桶的数量以使内存占用更小，这使得字典更有可能适合缓存，从而使其速度更快。 - Guffa

Answer 2

关于基于数据创建自己的实现的评论之外，这里有一个示例，它将没有任何冲突。这可能会根据对象的大小引发 OutOfMemoryExceptions。我尝试使用 int 索引器，但那会引发 OutOfMemoryException。如果返回 null，则表示该项不存在。

我还没有分析过这个，但我希望有轻微的速度提升，但更大的内存使用。

public class QuickLookup<T> where T : class
{
    private T[] _postives = new T[short.MaxValue + 1];
    private T[] _negatives = new T[short.MaxValue + 1];
    public T this[short key]
    {
        get
        {
            return key < 0 ? _negatives[(key * -1) - 1] : _postives[key];
        }
        set
        {
            if (key < 0)
                _negatives[key * -1] = value;
            else
                _postives[key] = value;
        }
    }
}

- Tim Carter

Answer 3

如果你只有10个桶，每个桶里有2000件物品，你是否可以建立一个包含所有20000件物品的单一列表，并通过循环已知的键直接索引它们？例如：

List<MyData> = new List(); 

//add all items to list indexed by their key (RAM is not an issue right?)

item = ItemList[key];

这样你可以直接引用它们，而无需使用字典或哈希查找。

- Joshua

---

是的，但是构建那个列表将需要太长时间。我要做几十万次这样的操作。 - Mike Christensen

List<>是如何实现的？如果它没有使用哈希，那么查找的时间复杂度是O(N)吗？ - Mike Christensen

哦，这是一个愚蠢的问题，List<>通过偏移量索引就像数组一样。但我猜当你传入一个比较函数时，Contains的时间复杂度是O(N)或O(log N)。 - Mike Christensen

Mike：Contains的时间复杂度为O(N)；BinarySearch的时间复杂度为O(lgN)。 - Gabe

是的，我想这就是为什么List.Contains()有一个重载来传递一个比较器，然后他们可以进行二分查找.. 这很有道理.. - Mike Christensen

Answer 4

听起来你说的是你的字典里只有10个项。如果是这样的话，哈希表可能是不必要的。你可以将数据存储在列表/数组中，并对其进行迭代或使用二分查找来查找键（尝试两种方法以查看哪一种更快）。

如果您使用二分查找，则您的列表必须已排序；如果您只是迭代列表，并且有一些键比其他键更频繁地被查找，您可以将它们放在列表的开头以加速查找过程。

另一方面，如果您的键事先已知，您可以编写自己的哈希表实现，其中包含快速和完美的哈希函数（即无冲突），那应该是无法击败的。

- Gabe

---

你怎么看？散列表不应该是O(1)吗？这比迭代大约10个项目要好...使用二分查找来查找键意味着对数据结构进行排序，虽然可能做到，但需要有点工作..理论上，散列表仍应更快...如果构建字典很慢，我会在剖析时看到的.. - Mike Christensen

你只有10个键，对吧？这意味着你的查找将是O(10)，与O(1)相同。换句话说，你的计算机可能能够比调用哈希函数并执行所需的整数除法来索引哈希表更快地迭代包含10个项目的列表。 - Gabe

哦，我明白了...好的观点，字典中可能要有一定数量的键才能真正体现哈希的优势...我一定会运行一些测试来证实这个理论... - Mike Christensen

哦，另外，我的速度大约是发布构建的两倍.. JIT 应该做了一些聪明的内联或其他什么东西.. - Mike Christensen

我期望哈希表会更快，但这取决于你的哈希函数。无论如何，很难相信比437毫秒快两倍的速度对你来说还不够快。 - Gabe

Answer 5

对哈希表内部工作原理的洞察是准确的。你应该在整个内部循环中使用TryGetValue：

  map.TryGetValue(keys[j], out item);

使用ContainsKey和Item[]会使查找过程重复进行。额外的if语句和keys[j]虽然很小，但在紧密循环中会逐渐累积。使用foreach遍历键可能会更慢，但根据循环的实际内容，值得进行性能分析。

- Dolphin