哪种更有效:Dictionary TryGetValue还是ContainsKey+Item?

从MSDN的词条词典。TryGetValue方法:

This method combines the functionality of the ContainsKey method and the Item property. If the key is not found, then the value parameter gets the appropriate default value for the value type TValue; for example, 0 (zero) for integer types, false for Boolean types, and null for reference types. Use the TryGetValue method if your code frequently attempts to access keys that are not in the dictionary. Using this method is more efficient than catching the KeyNotFoundException thrown by the Item property. This method approaches an O(1) operation.

从描述中，不清楚它是否比调用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);

注意:我不是在寻找一个基准!

当前回答

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

System.Collections.Generic。字典< TKey, TValue >。TryGetValue(TKey, out TValue) System.Collections.Generic。字典< TKey, TValue > .ContainsKey (TKey) System.Collections.Generic。字典< 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(TValue)替换为plain default。类型是推断出来的。

用法:

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);

2018-05-25 07:56:41

其他回答

一个快速的基准测试显示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

然而，当我让它“all hits”时，TryGetValue仍然是一个明显的赢家:

00:00:00.4930000
00:00:00.8110000

2012-02-21 18:08:28

由于到目前为止没有一个答案真正回答了这个问题，下面是我在一些研究后找到的一个可以接受的答案:

如果你反编译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+Item组合的两倍。

2012-02-21 18:59:27

TryGetValue会更快。

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

在Item后面使用ContainsKey基本上重复了查找功能，这在本例中是计算的主要部分。

2012-02-21 18:06:23

在我的机器上，有RAM负载，当以RELEASE模式(不是DEBUG)运行时，如果找到Dictionary<>中的所有条目，则ContainsKey等于TryGetValue/try-catch。

到目前为止，当只有几个字典条目没有找到时，ContainsKey的性能比它们都要好(在下面的例子中，将MAXVAL设置为任何大于entries的值，以丢失一些条目):

结果:

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();
            }
        }
    }

2015-01-21 23:41:22