Best way to check if a key exists in a Dictionary before adding it?

Question

When getting a key from a Dictionary you're not sure exists, you would usually use TryGetValue instead of ContainsKey + the get indexer to avoid the overhead of checking the key twice. In other words, this:

string password;
if (accounts.TryGetValue(username, out password))
{
    // use the password
}

would be preferred to this:

if (accounts.ContainsKey(username))
{
    string password = accounts[username];
}

What if I wanted to check if a key already existed before setting it to a value? For example, I would want to check if a username existed before overwriting it with a new password:

if (!accounts.ContainsKey(username))
{
    accounts.Add(username, password);
}
else
{
    Console.WriteLine("Username is taken!");
}

vs

// this doesn't exist
if (!accounts.TrySetValue(username, password))
{
    Console.WriteLine("Username is taken!");
}

Is there a more performant alternative to ContainsKey and Add that does this?

var password = keyValue.Where(entry => entry.Key.Contains("password")) .Select(item => item.Key).FirstOrDefault(); — Sanjeev S, Aug 07 '15 at 05:03
@SanjeevS Thank you for your answer, but LINQ would be much more inefficient than even the fallback solution I posted above. — James Ko, Aug 07 '15 at 05:05
I'm not sure there is much to be gained here, because dictionary is internally based on a hash table so that getting a value by key (e.g. using the indexer) is of O(1) complexity. — Grx70, Aug 07 '15 at 05:12
@Grx70 True, but if you take a look [here](https://github.com/dotnet/coreclr/blob/4cf8a6b082d9bb1789facd996d8265d3908757b2/src/mscorlib/src/System/Collections/Generic/Dictionary.cs#L316-L390) you'll see that there's a lot of work to be done every time you index a Dictionary. — James Ko, Aug 07 '15 at 05:23
@JamesKo: You are chasing shadows. `TryGetValue` calls the private function `FindEntry`. `ContainsKey` ALSO calls the same private `FindEntry` function. The indexer also calls `FindEntry`. From what I can tell, `FindEntry` looks pretty darn quick. Have you profiled your code? What issue are you trying to solve? — Sam Axe, Aug 07 '15 at 05:55
@SamAxe Then why did Microsoft add a `TryGetValue` method at all? `FindEntry` looks small, but it's an [O(n) operation](https://github.com/dotnet/coreclr/blob/4cf8a6b082d9bb1789facd996d8265d3908757b2/src/mscorlib/src/System/Collections/Generic/Dictionary.cs#L301-L303). Calling `ContainsKey` and the indexer on a large Dictionary would have a noticeable perf difference from `TryGetValue`. — James Ko, Aug 07 '15 at 06:03
@JamesKo: have you profiled your code? Tested how large a dictionary needs to be before that performance it "not good enough"? I think its likely you will never run into an issue. — Sam Axe, Aug 07 '15 at 06:08
@JamesKo That's why you call `ContainsKey` beforehand. Keys collection is hashed and lookup has expected complexity of O(1). The worst-case complexity is O(n), but that's only the case if you have A LOT of hash collisions (that's why it's important to carefully override `GetHashCode`). I'll join others and advise you to profile your code. Unless you're trying to do "theoretical optimization", in which case there are no definite answers. — Grx70, Aug 07 '15 at 06:31

score 6 · Answer 1 · answered Aug 08 '15 at 00:43

6

If you think inserting a new name will be the common case and attempting to insert a duplicate will be the rare case you may just want to use the overhead of catching a exception.

try
{
    accounts.Add(username, password);
}
catch (ArgumentException)
{
    Console.WriteLine("Username is taken!");
}

If you call Add with a existing key a ArgumentException will be thrown. Even if you have frequent duplicates this will still be likely more performant than your ContainsKey check.

answered Aug 08 '15 at 00:43

Scott Chamberlain

124,994
33
282
431

2

Numbers in this [answer](https://stackoverflow.com/a/13194904/804797) show that if "the rare case", happens more than 0.16% of the time (1 out of every 625) it is slower to just try-catch & gets significantly worse with more exceptions, while a ContainsKey check will add negligible overhead to **most** code. Also... If there is a simple way to avoid exceptions in regular program flow it is always the preferred practice. See readings: https://msdn.microsoft.com/en-us/library/ms229009(v=vs.100).aspx , https://stackoverflow.com/a/891230/804797 , https://stackoverflow.com/a/161965/804797 – Arkaine55 May 30 '17 at 19:23

Backs · Answer 2 · 2015-08-07T05:45:27.860

5

If you don't want to override, I think it's better to write your own extension-method like TryGetValue. There is no standard method.

OR

Use CuncurrentDictionary, it has TryAdd method, but you'll have overhead on sync.

So, simple answer - no, there is no such method.

edited Aug 07 '15 at 05:45

answered Aug 07 '15 at 04:56

Backs

24,430
5
58
85

1

You can't write an extension method like that unless you have access to `Dictionary`'s private members. – James Ko Aug 07 '15 at 05:11
@JamesKo which private methods do you need? You have ContainsKey. It's enough – Backs Aug 07 '15 at 05:18
1

Backs, this question is about perf. If you call `ContainsKey`, and then `Add`, you are checking if the key exists twice. That is why `TryGetValue` exists, and that is why it doesn't fulfill this question. – James Ko Aug 07 '15 at 05:21
@JamesKo ContainsKey is O(1) operation. And there is no perfomace problems with it. And method TryGetValue was NOT created because of perfomance of getting. It's created instead of this[key] way and checking KeyNotFoundException https://msdn.microsoft.com/en-us/library/bb347013(v=vs.110).aspx – Backs Aug 07 '15 at 05:25
Backs, you only get a `KeyNotFoundException` if you didn't check if it contains the key beforehand. Which is why people call `ContainsKey` beforehand. Which checks if the key exists twice. Which is why `TryGetValue` was created, quoting the link you provided, to **"combine the functionality of the ContainsKey method and the Item property."** – James Ko Aug 07 '15 at 05:29
@JamesKo so, I really don't understand, why you cannot use extension method with checking key exists and setting after... – Backs Aug 07 '15 at 05:32
Backs: Because [this huge block of code](https://github.com/dotnet/coreclr/blob/4cf8a6b082d9bb1789facd996d8265d3908757b2/src/mscorlib/src/System/Collections/Generic/Dictionary.cs#L316-L390) gets called when you check it exists and when you add it. **My goal in this question is to call it once.** – James Ko Aug 07 '15 at 05:36
2

@JamesKo what the reason? Do you really have perfomance problems? Or it's just to proof it's possible? I think, Dictionary<,> is very very optimized class. So, if you have perfomance problems - add graphics or smth else to see that problem is here, in checking. And short answer - no, you can't :) – Backs Aug 07 '15 at 05:41
...So I'm not allowed to ask questions about performance here if I'm not writing absolutely speed-critical code for the Linux kernel? Please don't get angry at me, I'm just asking a question. – James Ko Aug 07 '15 at 05:46
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/85376/discussion-between-backs-and-james-ko). – Backs Aug 07 '15 at 05:48
Great! Also, your new answer with `TryAdd` is very relevant, although yes it still has synchronization overhead. Thank you. – James Ko Aug 07 '15 at 05:49
BTW, @Backs mentions *override* as a way to solve this. However, to be clear, looking at the linked code, I see no *override* that would solve the (theoretical) performance question that James Ko asks. If `FindEntry` (and a couple of other methods) were `protected` instead of `private`, it would be possible to solve this (w/o extra overhead) in a subclass of Dictionary (because that would be able to access `protected` members). But one wouldn't override, one would simply add the missing `TrySetValue`, calling appropriate (but currently private) methods including `FindEntry`. – ToolmakerSteve Jan 22 '18 at 03:22

Enigmativity · Answer 3 · 2015-08-08T00:30:58.433

5

I tend to write my own extensions as needed.

For example, GetValueOrDefault like this:

public static V GetValueOrDefault<K, V>(this IDictionary<K, V> @this, K key, Func<V> @default)
{
    return @this.ContainsKey(key) ? @this[key] : @default();
}

It can be used like this:

var password = accounts.GetValueOrDefault(username, () => null);
if (password != null)
{
    //do stuff
}

Or SetValueIfExists:

public static V SetValueIfExists<K, V>(this IDictionary<K, V> @this, K key, V value)
{
    if (@this.ContainsKey(key))
    {
        @this[key] = value;
    }
}

Or SetValueIfNotExists:

public static V SetValueIfNotExists<K, V>(this IDictionary<K, V> @this, K key, V value)
{
    if (!@this.ContainsKey(key))
    {
        @this[key] = value;
    }
}

edited Aug 08 '15 at 00:30

answered Aug 07 '15 at 05:12

Enigmativity

113,464
11
89
172

@Enigmativity Haha thank you, but if you'll notice your extension method is the exact same thing I mentioned in my question. – James Ko Aug 07 '15 at 05:38
@JamesKo - Yes, but as an extension method it makes its usage neater. Isn't that what you wanted? Or did you want something baked into the language? – Enigmativity Aug 07 '15 at 07:41
1

@Enigmativity ContainsKey + indexer indexes the key twice. As I said in my question, I want to know if there's a way to do this indexing the key only once. Also, your new extension method still isn't what I was asking for in my question- I want `SetValueIfNotExists`. – James Ko Aug 07 '15 at 14:34
@JamesKo - Then you must be asking for something built-in to the dictionary itself. That you could check using intellisense. There is no way to avoid the double check. I was suggesting ways to remove the perceived double check from code, but there's no way to actually remove it. – Enigmativity Aug 08 '15 at 00:30
@Enigmativity, why do you use @ before @this? or you simply call this your dictionary? it's a bit confusing having 2 this words on the same line referring to two different things – Kris Nov 09 '19 at 19:31
@Kris - the use of `@` before a variable name allows the use of C# keywords as variable names. In extension methods I quite often use the `@this` to make it clear to me what variable is the `this` of the extension method. I find it the opposite of confusing. – Enigmativity Nov 09 '19 at 22:56

MaximGurschi · Answer 4 · 2017-05-26T09:43:40.047

2

I know i am late to this, but you can use a trick and store the count before the indexer set and check the count after the indexer set. If the counts are the same then you have overridden the key otherwise you have added a new mapping:

public static bool AddOrUpdate<TKey, TValue>(this IDictionary<TKey, TValue> 
    dictionary, TKey key, TValue value)
{
    var countBefore = dictionary.Count;
    dictionary[key] = value;
    return countBefore != dictionary.Count;
}

edited May 26 '17 at 09:43

answered May 26 '17 at 09:36

MaximGurschi

21
4

Interesting idea. But note that this doesn't help in the "usual" case, which is that you are checking whether it exists because you *don't* want to override an existing entry. OR if you are overwriting, you want to return the overwritten value (e.g. you need to Dispose the old one). In the second case, `AddOrUpdate` would return `TValue`, and would do: `var valueBefore;` `dictionary.TryGetValue(key, out value);` `dictionary[key] = value;` `return valueBefore;` Of course, this has the overhead James Ko was trying to avoid, just mentioning it as a useful alternative. – ToolmakerSteve Jan 22 '18 at 03:54
That is true (i only read the title). Think you meant to use valueBefore in the TryGet... – MaximGurschi Jan 29 '18 at 18:24

Best way to check if a key exists in a Dictionary before adding it?

4 Answers4