哪种更有效率：字典的TryGetValue方法还是ContainsKey和Item组合？

Question

从MSDN对Dictionary.TryGetValue Method的介绍中可以得知：

此方法结合了ContainsKey方法和Item属性的功能。

如果未找到键，则值参数获取值类型TValue的适当默认值；例如，整数类型为0（零），布尔类型为false，引用类型为null。

如果您的代码经常尝试访问字典中不存在的键，请使用TryGetValue方法。使用此方法比捕获Item属性抛出的KeyNotFoundException异常更有效。

此方法接近O（1）操作。

从描述中不清楚它是否比调用ContainsKey然后查找更有效，或者只是更方便。 TryGetValue的实现是否只调用ContainsKey然后调用Item，还是通过单个查找实际上更有效？

换句话说，哪个更有效（即执行较少的查找）：

Dictionary<int,int> dict;
//...//
int ival;
if(dict.ContainsKey(ikey))
{
  ival = dict[ikey];
}
else
{
  ival = default(int);
}

或者

Dictionary<int,int> dict;
//...//
int ival;
dict.TryGetValue(ikey, out ival);

注意：我不是在寻找基准测试！

- Rado

Answer 1

TryGetValue 会更快。

ContainsKey 和 TryGetValue 使用相同的检查，都是内部引用实际条目位置。除了抛出异常而不是返回false之外，Item 属性实际上具有与 TryGetValue 几乎相同的代码功能。

在使用 ContainsKey 后调用 Item 实际上是复制了查找功能，这是此情况下计算的主要部分。

- Reed Copsey

---

这段话的意思是：这个问题更微妙：如果字典中包含ikey，则增加其值；否则，添加一个键为ikey，值为0的项。但我认为TryGetValue仍然更高效，因为它使用了索引器属性的获取和设置操作，不是吗？ - Tim Schmelter

@TimSchmelter 是的 - ContainsKey和访问器都会进行检查 - 如果您使用TryGetValue，您只需要执行一次“get”操作，而不是两次。 - Reed Copsey

现在你实际上可以查看.NET源代码了：http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,2e5bc6d8c0f21e67。你会发现，TryGetValue、ContainsKey和this[]这三个方法都调用同一个FindEntry方法，并且执行相同的工作，只是在回答问题的方式上略有不同：TryGetValue返回布尔值和值，ContainsKey仅返回true/false，而this[]返回值或抛出异常。 - John Gardner

@JohnGardner 是的，这正是我所说的——但如果你先用 ContainsKey 再用 getItem，那么你要做两次工作而不是一次。 - Reed Copsey

我完全同意 :) 我只是想指出现在实际的来源可用了。其他的答案等等都没有提供实际来源的链接 :D。 - John Gardner

有点离题，如果您在多线程环境中通过IDictionary访问数据，我建议始终使用TryGetValue方法，因为从您调用ContainsKey方法的时刻到实际访问数据的时刻，状态可能会发生变化（虽然无法保证TryGetValue内部锁定的正确性，但它可能更安全）。 - Chris Berry

Answer 2

一个快速的基准测试表明，TryGetValue 稍微更胜一筹：

    static void Main() {
        var d = new Dictionary<string, string> {{"a", "b"}};
        var start = DateTime.Now;
        for (int i = 0; i != 10000000; i++) {
            string x;
            if (!d.TryGetValue("a", out x)) throw new ApplicationException("Oops");
            if (d.TryGetValue("b", out x)) throw new ApplicationException("Oops");
        }
        Console.WriteLine(DateTime.Now-start);
        start = DateTime.Now;
        for (int i = 0; i != 10000000; i++) {
            string x;
            if (d.ContainsKey("a")) {
                x = d["a"];
            } else {
                x = default(string);
            }
            if (d.ContainsKey("b")) {
                x = d["b"];
            } else {
                x = default(string);
            }
        }
   }

这会生成什么结果

00:00:00.7600000
00:00:01.0610000

如果命中和未命中的情况大致相同，则使用ContainsKey + Item访问会慢约40％。

此外，当我更改程序始终未命中（即始终查找"b"）时，这两个版本���得一样快：

00:00:00.2850000
00:00:00.2720000

然而，当我将其设置为“全部命中”时，TryGetValue 仍然是明显的优胜者：

00:00:00.4930000
00:00:00.8110000

- Sergey Kalinichenko

---

@Luciano，你能解释一下你是如何使用 Any 的吗？就像这样：Any(i=>i.Key==key)。在这种情况下，是的，这是字典的一个糟糕的线性搜索。 - weston

DateTime.Now只能精确到几毫秒，建议使用System.Diagnostics中的Stopwatch类代替，它能够提供更高的精度，因为它在内部使用QueryPerformanceCounter。而且Stopwatch类也更易于使用。 - Alastair Maw

除了Alastair和Ed的评论之外，DateTime.Now可能会倒退，如果您获得时间更新，例如用户更新计算机时间、跨越时区或时区更改（例如夏令时）。尝试使用系统时钟与GPS或移动电话网络提供的时间同步工作。DateTime.Now将到处飞，而DateTime.UtcNow只修复其中一个原因。只需使用StopWatch即可。 - antiduh

@Dan 我要比较的两个操作都需要是O(1)，这不是基准测试的重点。 - Sergey Kalinichenko

@Dan 我的基准测试也迭代了一千万次操作以获得真实结果。此外，我的结果非常符合其他人的结果：例如，davisoa的45/26比率与我的0.811/0.493比率相差不到5%。 - Sergey Kalinichenko

Answer 3

迄今为止，由于没有一个答案实际回答了这个问题，所以在一些研究后，我找到了一个可接受的答案：

如果你反编译 TryGetValue，你会发现它正在做这件事：

public bool TryGetValue(TKey key, out TValue value)
{
  int index = this.FindEntry(key);
  if (index >= 0)
  {
    value = this.entries[index].value;
    return true;
  }
  value = default(TValue);
  return false;
}

而 ContainsKey 方法是：

public bool ContainsKey(TKey key)
{
  return (this.FindEntry(key) >= 0);
}

所以TryGetValue只是ContainsKey和一个数组查找的组合，如果该项存在。

来源

似乎TryGetValue将比ContainsKey +项目组合快近一倍。

- Rado

---

如果没有匹配的键，ContainsKey不需要访问任何Item[]。 - SHIN JaeGuk

Answer 4

谁在意呢 :-)

你可能问这个问题是因为TryGetValue很难使用 - 所以可以用扩展方法来封装它，就像这样。

public static class CollectionUtils
{
    // my original method
    // public static V GetValueOrDefault<K, V>(this Dictionary<K, V> dic, K key)
    // {
    //    V ret;
    //    bool found = dic.TryGetValue(key, out ret);
    //    if (found)
    //    {
    //        return ret;
    //    }
    //    return default(V);
    // }


    // EDIT: one of many possible improved versions
    public static TValue GetValueOrDefault<K, V>(this IDictionary<K, V> dictionary, K key)
    {
        // initialized to default value (such as 0 or null depending upon type of TValue)
        TValue value;  

        // attempt to get the value of the key from the dictionary
        dictionary.TryGetValue(key, out value);
        return value;
    }

那么只需要调用：

dict.GetValueOrDefault("keyname")

或者

(dict.GetValueOrDefault("keyname") ?? fallbackValue) 

- Simon_Weaver

---

@Hüseyin 我很困惑，我怎么这么蠢，竟然没有写 this 就发布了这个内容，但事实证明，在我的代码库中重复了两次我的方法 - 一次带有 this，一次没有，所以我从未发现它！谢谢你的修复！ - Simon_Weaver

如果键不存在，TryGetValue 会将默认值分配给输出值参数，因此这可以简化。 - Raphael Smit

public static TValue GetValueOrDefault<TKey, TValue>(this Dictionary<TKey, TValue> dict, TKey key) { TValue ret; dict.TryGetValue(key, out ret); return ret; } - Joshua

在C#7中，这真的很有趣：if(!dic.TryGetValue(key, out value item)) item = dic[key] = new Item(); - Shimmy Weitzhandler

具有讽刺意味的是，真正的源代码已经有一个GetValueOrDefault()例程，但它被隐藏了... https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,9680ab8ad8dfbf8d - Deven T. Corzine

Answer 5

为什么不试一下呢？

但我非常确定TryGetValue更快，因为它只进行一次查找。当然这并不是保证的，即不同的实现可能具有不同的性能特征。

我实现字典的方式是创建一个内部的Find函数来查找一个项目的插槽，然后在此基础上构建其余部分。

- CodesInChaos

---

我认为实现细节不可能改变这个保证，即执行动作X一次比执行动作X两次更快或相等。最好的情况是它们相同，最坏的情况是2X版本需要二倍的时间。 - Dan Bechard

Answer 6

到目前为止，所有的答案都很好，但遗漏了一个关键点。

API（例如.NET框架）中的类方法是接口定义的一部分（不是C#或VB接口，而是计算机科学意义上的接口）。

因此，通常问调用这样的方法是否更快是不正确的，除非速度是接口定义的一部分（在这种情况下它不是）。

传统上，这种快捷方式（组合搜索和检索）无论语言、基础设施、操作系统、平台还是机器架构都更有效率。而且它更易读，因为它明确地表达了您的意图，而不是暗示它（从您的代码结构中）。

所以答案（来自一个经验丰富的老手）绝对是“是”（TryGetValue比使用ContainsKey和Item [Get]从字典中检索值的组合更可取）。

如果你觉得这听起来很奇怪，就想象一下：即使当前的TryGetValue、ContainsKey和Item [Get]的实现没有任何速度差异，你可以假设未来的实现（例如.NET v5）会有（TryGetValue会更快）。考虑你的软件的生命周期。

顺便说一句，有趣的是，典型的现代接口定义技术仍然很少提供任何形式的正式定义时序约束的方法。也许.NET v5？

- debater

---

虽然我完全同意你的关于语义学的论点，但进行性能测试仍然是值得的。除非进行测试，否则您永远不会知道您正在使用的API是否具有次优实现，以至于在语义上正确的操作可能较慢。 - Dan Bechard

Answer 7

除了设计一个在实际环境中可以给出准确结果的微基准测试之外，您还可以检查.NET Framework的参考源代码。

• System.Collections.Generic.Dictionary<TKey, TValue>.TryGetValue(TKey, out TValue) - 尝试获取具有指定键的值。
• System.Collections.Generic.Dictionary<TKey, TValue>.ContainsKey(TKey) - 确定字典是否包含指定的键。
• System.Collections.Generic.Dictionary<TKey, TValue>.Item(TKey) - 获取或设置与指定键关联的值。

他们都调用FindEntry(TKey)方法，该方法完成大部分工作且不记忆其结果，因此调用TryGetValue几乎比ContainsKey+Item快两倍。

---

TryGetValue 的不便利接口可以使用扩展方法进行适应：

using System.Collections.Generic;

namespace Project.Common.Extensions
{
    public static class DictionaryExtensions
    {
        public static TValue GetValueOrDefault<TKey, TValue>(
            this IDictionary<TKey, TValue> dictionary,
            TKey key,
            TValue defaultValue = default(TValue))
        {
            if (dictionary.TryGetValue(key, out TValue value))
            {
                return value;
            }
            return defaultValue;
        }
    }
}

^{自C# 7.1以来，您可以用普通的default替换default(TValue)。 类型会被推断。}

用法：

var dict = new Dictionary<string, string>();
string val = dict.GetValueOrDefault("theKey", "value used if theKey is not found in dict");

它对查找失败的引用类型返回null，除非指定了显式的默认值。

var dictObj = new Dictionary<string, object>();
object valObj = dictObj.GetValueOrDefault("nonexistent");
Debug.Assert(valObj == null);

var dictInt = new Dictionary<string, int>();
int valInt = dictInt.GetValueOrDefault("nonexistent");
Debug.Assert(valInt == 0);

- Palec

---

请注意，扩展方法的用户无法区分不存在的键和存在但其值为default(T)的键。 - Lucas

在现代计算机上，如果你快速连续调用一个子程序两次，它不太可能比单次调用慢两倍。这是因为CPU和缓存架构很可能会缓存与第一次调用相关的许多指令和数据，所以第二次调用将会更快地执行。另一方面，连续调用两次几乎肯定会比调用一次稍微慢一些，因此，如果可能的话，消除第二次调用仍然有优势。 - debater

Answer 8

在我的电脑上，有大量的RAM，在RELEASE模式下运行（而不是DEBUG），如果字典中的所有条目都被找到，ContainsKey等于TryGetValue/try-catch。当只有少量的字典条目未被找到时（在下面的示例中，将MAXVAL设置为大于ENTRIES的任何值即可），ContainsKey远远优于它们：

结果：

Finished evaluation .... Time distribution:
Size: 000010: TryGetValue: 53,24%, ContainsKey: 1,74%, try-catch: 45,01% - Total: 2.006,00
Size: 000020: TryGetValue: 37,66%, ContainsKey: 0,53%, try-catch: 61,81% - Total: 2.443,00
Size: 000040: TryGetValue: 22,02%, ContainsKey: 0,73%, try-catch: 77,25% - Total: 7.147,00
Size: 000080: TryGetValue: 31,46%, ContainsKey: 0,42%, try-catch: 68,12% - Total: 17.793,00
Size: 000160: TryGetValue: 33,66%, ContainsKey: 0,37%, try-catch: 65,97% - Total: 36.840,00
Size: 000320: TryGetValue: 34,53%, ContainsKey: 0,39%, try-catch: 65,09% - Total: 71.059,00
Size: 000640: TryGetValue: 32,91%, ContainsKey: 0,32%, try-catch: 66,77% - Total: 141.789,00
Size: 001280: TryGetValue: 39,02%, ContainsKey: 0,35%, try-catch: 60,64% - Total: 244.657,00
Size: 002560: TryGetValue: 35,48%, ContainsKey: 0,19%, try-catch: 64,33% - Total: 420.121,00
Size: 005120: TryGetValue: 43,41%, ContainsKey: 0,24%, try-catch: 56,34% - Total: 625.969,00
Size: 010240: TryGetValue: 29,64%, ContainsKey: 0,61%, try-catch: 69,75% - Total: 1.197.242,00
Size: 020480: TryGetValue: 35,14%, ContainsKey: 0,53%, try-catch: 64,33% - Total: 2.405.821,00
Size: 040960: TryGetValue: 37,28%, ContainsKey: 0,24%, try-catch: 62,48% - Total: 4.200.839,00
Size: 081920: TryGetValue: 29,68%, ContainsKey: 0,54%, try-catch: 69,77% - Total: 8.980.230,00

以下是我的代码：

    using System;
    using System.Collections.Generic;
    using System.Diagnostics;

    namespace ConsoleApplication1
    {
        class Program
        {
            static void Main(string[] args)
            {
                const int ENTRIES = 10000, MAXVAL = 15000, TRIALS = 100000, MULTIPLIER = 2;
                Dictionary<int, int> values = new Dictionary<int, int>();
                Random r = new Random();
                int[] lookups = new int[TRIALS];
                int val;
                List<Tuple<long, long, long>> durations = new List<Tuple<long, long, long>>(8);

                for (int i = 0;i < ENTRIES;++i) try
                    {
                        values.Add(r.Next(MAXVAL), r.Next());
                    }
                    catch { --i; }

                for (int i = 0;i < TRIALS;++i) lookups[i] = r.Next(MAXVAL);

                Stopwatch sw = new Stopwatch();
                ConsoleColor bu = Console.ForegroundColor;

                for (int size = 10;size <= TRIALS;size *= MULTIPLIER)
                {
                    long a, b, c;

                    Console.ForegroundColor = ConsoleColor.Yellow;
                    Console.WriteLine("Loop size: {0}", size);
                    Console.ForegroundColor = bu;

                    // ---------------------------------------------------------------------
                    sw.Start();
                    for (int i = 0;i < size;++i) values.TryGetValue(lookups[i], out val);
                    sw.Stop();
                    Console.WriteLine("TryGetValue: {0}", a = sw.ElapsedTicks);

                    // ---------------------------------------------------------------------
                    sw.Restart();
                    for (int i = 0;i < size;++i) val = values.ContainsKey(lookups[i]) ? values[lookups[i]] : default(int);
                    sw.Stop();
                    Console.WriteLine("ContainsKey: {0}", b = sw.ElapsedTicks);

                    // ---------------------------------------------------------------------
                    sw.Restart();
                    for (int i = 0;i < size;++i)
                        try { val = values[lookups[i]]; }
                        catch { }
                    sw.Stop();
                    Console.WriteLine("try-catch: {0}", c = sw.ElapsedTicks);

                    // ---------------------------------------------------------------------
                    Console.WriteLine();

                    durations.Add(new Tuple<long, long, long>(a, b, c));
                }

                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.WriteLine("Finished evaluation .... Time distribution:");
                Console.ForegroundColor = bu;

                val = 10;
                foreach (Tuple<long, long, long> d in durations)
                {
                    long sum = d.Item1 + d.Item2 + d.Item3;

                    Console.WriteLine("Size: {0:D6}:", val);
                    Console.WriteLine("TryGetValue: {0:P2}, ContainsKey: {1:P2}, try-catch: {2:P2} - Total: {3:N}", (decimal)d.Item1 / sum, (decimal)d.Item2 / sum, (decimal)d.Item3 / sum, sum);
                    val *= MULTIPLIER;
                }

                Console.WriteLine();
            }
        }
    }

- AxD

---

我感觉这里有些不对劲。我想知道优化器是否会删除或简化您的ContainsKey()检查，因为您从未使用检索到的值。 - Dan Bechard

它就是不行。ContainsKey()在编译的DLL中。优化器并不知道ContainsKey()实际上做了什么。它可能会引起副作用，因此必须调用它，不能被省略。 - AxD

这里有些虚假的东西。事实是，检查 .NET 代码显示 ContainsKey、TryGetValue 和 this[] 都调用相同的内部代码，因此当条目存在时，TryGetValue 比 ContainsKey + this[] 更快。 - Jim Balter

Answer 9

制作一个快速的测试程序，在使用TryGetValue时，字典中有100万个项是明显提高了性能。

结果:

100万次ContainsKey + Item：45毫秒

100万次TryGetValue: 26毫秒

这是测试应用程序：

static void Main(string[] args)
{
    const int size = 1000000;

    var dict = new Dictionary<int, string>();

    for (int i = 0; i < size; i++)
    {
        dict.Add(i, i.ToString());
    }

    var sw = new Stopwatch();
    string result;

    sw.Start();

    for (int i = 0; i < size; i++)
    {
        if (dict.ContainsKey(i))
            result = dict[i];
    }

    sw.Stop();
    Console.WriteLine("ContainsKey + Item for {0} hits: {1}ms", size, sw.ElapsedMilliseconds);

    sw.Reset();
    sw.Start();

    for (int i = 0; i < size; i++)
    {
        dict.TryGetValue(i, out result);
    }

    sw.Stop();
    Console.WriteLine("TryGetValue for {0} hits: {1}ms", size, sw.ElapsedMilliseconds);

}

- davisoa

Answer 10

如果您想从字典中获取值，TryGetValue(key, out value)是最佳选项。但是，如果您需要检查键是否存在并进行新插入而不覆盖旧键，并且仅在该范围内，ContainsKey(key)是最佳选项。基准测试可以确认这一点：

using System;
using System.Threading;
using System.Diagnostics;
using System.Collections.Generic;
using System.Collections;

namespace benchmark
{
class Program
{
    public static Random m_Rand = new Random();
    public static Dictionary<int, int> testdict = new Dictionary<int, int>();
    public static Hashtable testhash = new Hashtable();

    public static void Main(string[] args)
    {
        Console.WriteLine("Adding elements into hashtable...");
        Stopwatch watch = Stopwatch.StartNew();
        for(int i=0; i<1000000; i++)
            testhash[i]=m_Rand.Next();
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- pause....", watch.Elapsed.TotalSeconds);
        Thread.Sleep(4000);
        Console.WriteLine("Adding elements into dictionary...");
        watch = Stopwatch.StartNew();
        for(int i=0; i<1000000; i++)
            testdict[i]=m_Rand.Next();
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- pause....", watch.Elapsed.TotalSeconds);
        Thread.Sleep(4000);

        Console.WriteLine("Finding the first free number for insertion");
        Console.WriteLine("First method: ContainsKey");
        watch = Stopwatch.StartNew();
        int intero=0;
        while (testdict.ContainsKey(intero))
        {
            intero++;
        }
        testdict.Add(intero, m_Rand.Next());
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- added value {1} in dictionary -- pause....", watch.Elapsed.TotalSeconds, intero);
        Thread.Sleep(4000);
        Console.WriteLine("Second method: TryGetValue");
        watch = Stopwatch.StartNew();
        intero=0;
        int result=0;
        while(testdict.TryGetValue(intero, out result))
        {
            intero++;
        }
        testdict.Add(intero, m_Rand.Next());
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- added value {1} in dictionary -- pause....", watch.Elapsed.TotalSeconds, intero);
        Thread.Sleep(4000);
        Console.WriteLine("Test hashtable");
        watch = Stopwatch.StartNew();
        intero=0;
        while(testhash.Contains(intero))
        {
            intero++;
        }
        testhash.Add(intero, m_Rand.Next());
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- added value {1} into hashtable -- pause....", watch.Elapsed.TotalSeconds, intero);
        Console.Write("Press any key to continue . . . ");
        Console.ReadKey(true);
    }
}
}

这是一个真实的例子，我有一个服务，每创建一个“Item”，就会关联一个递增的数字。每次创建新项目时，必须找到空闲的编号。如果删除一个项目，则空闲编号将变为空闲状态。当然，这并不是最优化的方法，因为我有一个静态变量缓存当前数字。但是，如果你用完所有的数字，你可以从0开始到UInt32.MaxValue重新开始。

执行的测试如下： 添加元素到哈希表中... 用时0.5908秒——暂停... 添加元素到字典中... 用时0.2679秒——暂停... 查找插入的第一个空闲号码 第一种方法：ContainsKey 用时0.0561秒——在字典中添加值1000000——暂停... 第二种方法：TryGetValue 用时0.0643秒——在字典中添加值1000001——暂停... 测试哈希表 用时0.3015秒——将值1000000添加到哈希表中——暂停... 按任意键继续...

如果有人问是否ContainsKeys有优势，我甚至尝试了使用TryGetValue和Contains key相反的方式，结果是一样的。

所以，对我来说，最终考虑取决于程序的行为方式。

- Fwiffo