Dictionary<TKey, TValue>的更快替代方案

Question

我需要一个快速替代 System.Collections.Generic.Dictionary<TKey, TValue> 的方法，我的应用程序需要非常高的运行速度。因此，替代方法应该支持以下功能：

• 泛型
• 添加（Add）
• 获取（Get）
• 包含（Contains）

......就是这样。我不需要在 LINQ 或其他任何方面提供支持。而且它应该快速。

像下面这样简单的代码：

Stopwatch stopWatch = Stopwatch.StartNew();

Dictionary<string, string> dictionary = new Dictionary<string, string>();
dictionary.Add("fieldName", "fieldValue");
dictionary.Add("Title", "fieldVaaaaaaaaaaaaaaaaalue");

Console.WriteLine(stopWatch.Elapsed);

... 打印出了 00:00:00.0001274，这对我来说是 相当长 的时间，因为我的应用程序正在执行许多其他任务，其中一些来自我必须使用且不受我控制的旧缓慢库。

有没有任何想法如何实现更快的方法呢？

谢谢。

- Alon Gubkin

---

你需要创建这样的词典有多频繁？你为什么要在时间安排中包括词典的构建？ - AnthonyWJones

你有在发布版本中测量时间，而非在调试器下运行吗？ - Erik Funkenbusch

定义“快速”（fast）。你是否实际分析过任何真实的代码，还是这只是一个人为制造的例子？ - Ed S.

如果您想要非常快的速度，请不要使用字符串作为键——它是性能瓶颈中的头号杀手。 - Oliver Friedrich

如果你可以使用枚举，那就用它吧。+1 给格伦德尔的杀手。 - Nick Vaccaro

提供您自己的比较器，var dictionary = new Dictionary<string, string>(StringComparer.Ordinal); 这样可以改进字典默认的比较器，并避免在字典 TKey 转换中进行双重转换。 - Walter Verhoeven

Answer 1

你很可能正在看到JIT编译。在我的电脑上，我看到：

00:00:00.0000360
00:00:00.0000060

如果在同一个进程中连续快速运行两次（确保不在调试器中运行，否则这是一个无意义的测试），会出现问题。

现在，测量任何如此短暂的时间都是不好的。您需要迭代数百万次才能更好地了解它所花费的时间。

您有充分的理由相信它实际上减慢了您的代码吗？还是您只是根据最初的计时来判断？

我怀疑您会发现比 Dictionary<TKey, TValue> 更快的解决方案，并且如果它成为瓶颈，我会非常惊讶。

编辑：我刚刚对向一个包含一百万个元素的 Dictionary<TKey, TValue> 添加的基于现有对象的键进行了基准测试（字符串在数组中），重复使用相同的值（因为它与结果无关），并在构造函数中指定容量为一百万 - 在我的两年旧笔记本电脑上大约需要 0.15 秒。

考虑到您已经说过您的应用程序中其他地方正在使用一些“旧慢库”，那么它真的很可能成为您的瓶颈吗？请记住，其他库越慢，改进的集合类对应用程序的影响就越小。如果字典更改仅占您总体应用程序时间的 1％，那么即使我们可以提供一个“瞬时”的字典，也只能将您的应用程序加速 1％。

像往常一样，使用分析器 - 这将为您提供关于时间去向的更好的了解。

- Jon Skeet

---

我基于我的原始计时来进行所有的操作。 - Alon Gubkin

如果哈希码实现不好，字典在处理自定义类甚至更可能是自定义结构体时会表现得非常糟糕。 - Reed Copsey

@Saar：也许他的机器更快，或者他运行的东西更少，或者有无数其他可能性。运行2个加法的时间会波动很大。你必须运行无数次加法才能得到稳定的测量结果。 - R. Martinho Fernandes

@Saar：连续运行相同的代码...你用的是什么机器，以及使用的是哪个版本的.NET？ - Jon Skeet

@Saar：不要在不同的进程中运行它，而是在同一进程中多次运行，即将其放入一个方法中并调用两次。否则，每次都会进行JIT编译。 - Jon Skeet

Answer 2

我认同Jon Skeet的假设，即这很可能是JIT编译引起的。

话虽如此，我想在这里补充一些其他信息：

与使用Dictionary<T,U>相关的大多数速度问题都与Dictionary的实现无关。默认情况下，Dictionary<T,U>非常快。很难超越它。

与Dictionary实例相关的速度问题几乎总是哈希码实现问题。如果您在使用Dictionary<MyCustomClass,MyValue>时遇到速度问题，请重新审视您在MyCustomClass上定义的GetHashCode()实现。如果您使用自定义结构作为键，则更加关键。

为了获得良好的Dictionary性能，GetHashCode()应该：

1. 快速
2. 能够提供生成冲突较少的哈希码。唯一的实例应尽可能生成唯一的哈希值。

如果做到了这一点，我认为您会对默认的Dictionary实现非常满意。

- Reed Copsey

---

如果您无法拥有唯一的哈希码值，则键类中Equals方法的性能也很重要。 - sweetfa

Answer 3

请不要忘记，在那段代码中你同时计时了字典构造函数。我进行了一项测试，将构造函数的调用移出测量范围，并循环执行10次。以下是我的测试代码：

for (int i = 0; i < 10; i++)
{
    Dictionary<string, string> test = new Dictionary<string, string>();

    System.Diagnostics.Stopwatch watch = System.Diagnostics.Stopwatch.StartNew();

    test.Add("fieldName", "fieldValue");
    test.Add("Title", "fieldavlkajlkdjflkjalkjslkdjfiajwelkrjelrkjavoijl");

    Console.WriteLine(watch.Elapsed);
}

Console.ReadKey();

以下是结果：

00:00:00.0000607
00:00:00.0000025
00:00:00.0000015
00:00:00.0000015
00:00:00.0000016
00:00:00.0000017
00:00:00.0000016
00:00:00.0000016
00:00:00.0000016
00:00:00.0000015

我不确定还有什么比这更快的方法...

更新

看起来这也反映了Jon Skeet的结果...JIT。

- Justin Niessner

Answer 4

最大化性能，将Ints用作键：

如果您想从一个字典中挤出最后一丝性能，则使用Ints作为键。这里有一个比较Int和String Keys的基准测试： https://jacksondunstan.com/articles/2527

文章的作者甚至提到了，如果您有这样的需要，将字符串转换为Ints是值得的。

另外，请注意，在一些其他语言（如PHP）中也存在同样的行为。PHP关联数组实际上就是字典，如果您在PHP7中按升序使用Ints，则它们的性能远远优于字符串键。

- JamesHoux

Answer 5

如果你真的需要更好的性能，你将不得不放弃一些重要的东西——比如泛型、动态内存分配等。所有这些特性都会牺牲一些性能。

如果可能的话，我会避免使用Contains，而是考虑使用TryGetValue等方法。

- Cade Roux

Answer 6

字典允许指定IEqualityComparer比较器。对于字符串或其他类型，通用比较器可能不是最佳性能选择。通过一些ILSpy可以发现，如果采用默认的==比较器，如果您的实现性能受到影响，您可以注入自己的IEqualityComparer比较器。最终，字典将比较您提供为键的哈希码与其现有条目列表中的现有哈希码。因此，如果您有特定需求的字典，可以专门使用FastDictionary类，以更高效的方式获取哈希码。在您的实现中，应该是这样的：

var dictionary = new Dictionary<string, string>(StringComparer.Ordinal); 

- Walter Verhoeven

Answer 7

很可能你找不到比字典更快的东西。我建议使用字典。当你发现无法达到性能目标，并且分析工具表明添加/删除操作是瓶颈时，可以考虑替换为更专门的类。

请注意，如果不使用LINQ等功能，则不会造成任何性能损失。

- Michael

Answer 8

你计划向字典中添加多少项？虽然Dictionary/Hashtable通常是最快的，但根据你的使用情况，可能会有比Hashtable更快（即更适合）的东西。根据使用情况，如果与某种Skip List或自平衡树或tries相结合，SortedList可能会更快，特别是如果您希望返回一系列值而不是单个值。

当满足以下条件时，Hashtable很适合：

1. 在填充表之前，您知道要存储多少项。动态调整大小将非常痛苦！
2. 您拥有良好的哈希算法，具有均匀分布，.NET具备此功能
3. 已经有了解决冲突的良好机制，.NET也具备此功能
4. 您正在寻找单个值
5. 您可以保证所有值都是唯一的

例如，如果您正在进行某些压缩，则RB-Tree比Hashtable更好。

来源：http://en.wikipedia.org/wiki/Hashtable#Dynamic_resizing

- Nate Zaugg

Answer 9

除了上述内容，请注意以下事项：

1. 您可以通过在构造函数中的括号中传递初始大小来{Pre}初始化字典对象中的哈希桶数组。例如：301？

Dictionary<string, string> dictionary = new Dictionary<string, string>( 301 );

2. 根据你需要更快的是add还是get，你可能还需要关注优化Add/Remove或者只是Retrieve。这意味着有时需要更快地定位和检索而不是添加或删除它们。在你的例子中，你提到了dictionary.Add方法，但问题也被问及整个类Dictionary<TKey, TValue>中更快的替换。因此我假设，你不仅对add方法感兴趣，也希望get方法更快。在这种情况下，下一个项目可以考虑作为特定键数据模式的更快解决方案。

3. 比Dictionary和SortedList(int)更快的只能是纯粹的静态/动态泛型数组Array<String>... 但这是时间/空间的大O(N)权衡。

解释： a.1)Dictionary可以在O(1)内获取值（如果哈希值没有太多冲突！） a.2)Dictionary的add有时是O(1)，有时是O(n)。因此，如果你一个接一个地添加元素，那么大致上对于每个下一个元素索引等于下一个质数，你会获得O(n)的时间复杂度，这比0(1)大。来源：深入理解泛型字典

b.1)Array元素通过预先分配的内存段中的int索引值简单访问... Array[Index]（时间复杂度=O(1)）。 因此，在dictionary的情况下，它总是比以下操作更快： LoopSearchInEntryListTargetElement(TransformToBucketArrayIndex(GetHashCode()))

在发生冲突的情况下，条目列表可能需要迭代1到100次。

b.2)将值设置为Array也只是内存中的int类型值分配操作（时间复杂度O(1)）。 在dictionary的情况下，这有时需要调整大小和/或重新组织。

在您的情况下：如果您知道所有密钥字符串的不同值都不超过某个uint.MaxValue（32位无符号整数）（在32位环境中），并且任何密钥的最大字符串长度都不超过4（假定字符集是从char（0）到char（255））- > 您可以轻松地将此类型的任何字符串转换为相应的int值（用作我们的Array<string>中的索引）以最快的方式编写或读取String值。

这将始终是O（1）的时间复杂度，用于获取和/或分配数组中的值。 (Contains（TKey）可以编写为TKeyValueArray [index]！= NULL！注意：如果TValues在您的情况下也可以为空，则创建类似于KeyValuePair的自定义类或通用类型的结构，但具有附加的boolean字段 - Flag Set或NotSet）

粗略示例（提示）：获取字节代码并对字符串索引[0、1、2、3]中的每个字符字节代码进行简单的数学运算。

(
      index =
          SomeKeyString [ 0 ] * 256 * 256 * 256
        + SomeKeyString [ 1 ] * 256 * 256
        + SomeKeyString [ 2 ] * 256
        + SomeKeyString [ 3 ] 
)

公式和方法可以根据情况进行优化（如果字符串仅包含拉丁字母表字符，则无需使用太多内存或者您可以在数组中表示更长的 TKey 字符串）。这是在迫切需要性能的情况下。

* 拉丁字母表使用 191 个字符 ISO 8859-1 对其称为“第一拉丁字母表”的 191 个字符进行编码，由拉丁字母表组成... *

抱歉只提供了未经详细解释的提示，如果感兴趣，我会尽力提供更详细的答案。

此外，请阅读此文 Initial capacity of collection types, e.g. Dictionary, List

- Gega Kakabadze

Answer 10

你能否使用一个列表并定义一个枚举，例如，fieldName = 0，Title = 1，并使用每个属性的唯一索引作为查找列表中的索引？这将是最快的解决方案，尽管最不灵活，因为您将被绑定到一个枚举。

- Paul Sasik