What Is More Efficient: Dictionary Trygetvalue or Containskey+Item

What is more efficient: Dictionary TryGetValue or ContainsKey+Item?

TryGetValue will be faster.

ContainsKey uses the same check as TryGetValue, which internally refers to the actual entry location. The Item property actually has nearly identical code functionality as TryGetValue, except that it will throw an exception instead of returning false.

Using ContainsKey followed by the Item basically duplicates the lookup functionality, which is the bulk of the computation in this case.

Is there a reason why one should use ContainsKey over TryGetValue

It depends for what are you using the methods. If you open Reference source you will see.

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

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

Like you see TryGetValue is same as ContainsKey + one array lookup.

If your logic is only to check if the key is existing in the Dictionary and nothing else related to this key (taking the value for the key) you should use ContainsKey.

If you want to take the value for the specific key, TryGetValue is faster than

if(dic.ContainsKey(keyValue))
{
    dicValue = dic[keyValue]; // here you do more work!
}

Logic about Dictionary[key]

    public TValue this[TKey key] 
    {
        get {
            int i = FindEntry(key);
            if (i >= 0) return entries[i].value;
            ThrowHelper.ThrowKeyNotFoundException();
            return default(TValue);
        }
        set {
            Insert(key, value, false);
        }
    }

So pretty much you will go 2 times in FindEntry method + array lookup, if you use the key with ContainsKey and after that take the value with dic[key]. You have overhead of calling FindEntry one additional time.

Why is it faster to check if dictionary contains the key, rather than catch the exception in case it doesn't?

On the one hand, throwing exceptions is inherently expensive, because the stack has to be unwound etc.

On the other hand, accessing a value in a dictionary by its key is cheap, because it's a fast, O(1) operation.

BTW: The correct way to do this is to use TryGetValue

obj item;
if(!dict.TryGetValue(name, out item))
    return null;
return item;

This accesses the dictionary only once instead of twice.

If you really want to just return null if the key doesn't exist, the above code can be simplified further:

obj item;
dict.TryGetValue(name, out item);
return item;

This works, because TryGetValue sets item to null if no key with name exists.

Dictionary Direct access vs TryGetValue

I don't think you should use try/catch to form a logical path like that. Exceptions are supposed to be exceptional cases, where something has "gone wrong".

Personally, I prefer ContainsKey:

if (myDic.ContainsKey("test")) {
   MyCustomType value = myDic["test"];
   // do something with the value
}

If you think that not finding the key means that something has "gone wrong", then I would omit the test, and let an exception be thrown if the key is not found.

EDIT: these days I try to use TryGetValue instead. It's slightly more clumsy, but once you get used to it, it's not so bad.

MyCustomType value;
if (myDic.TryGetValue("test", out value)) {
   // do something with value
}

EDIT2: Now with out var I definitely use TryGetValue a lot more. Similarly you can write a CantGetValue method (same thing with opposite boolean result), since most of the time you want to do something extra when there isn't a value, not when there is.

if (dict.TryGetValue("test", out var value)) {
   // do something with value
}

// or

if (cache.CantGetValue("test", out var cachedValue)) {
   // cache value
}
// make use of value

Difference between ContainsKey and ContainsValue in Dictionary?

Dictionarys are mappings from a key to a value.

ContainsKey() checks if your dictionary contains a certain key, it is very fast - looking up keys (and finding the data associated with that key) is the main strength of dictionaries. You might need this, to avoid accessing a non-existent Key - read about TryGetValue() in that case - it might be a better choice to avoid accessing non existing keys data.

ContainsValue() iterates over all values and checks if it is in the dictionary, it is a slow and cumbersome procedure because it needs to go to all values until the first one matches. Accessing values not by its key, but by iterating all is not what dictionaries are about.

Doing a ContainsKey() is fine, if you feel you need to do a ContainsValue() you are probably operating on the wrong kind of data structure.

Doku:

• ContainsKey() vs. TryGetValue()
• ContainsValue()

linq vs ToDictionary() and TryGetValue() - what is more efficient?

If you're just doing one lookup, the non-dictionary one is faster because it avoids the overhead of building the dictionary.

If you're going to do a lot of lookups on the same dataset, the dictionary one is faster because it is a data structure specifically design for fast look up by a single key. The more lookups you do, the more it is worth the overhead of building the dictionary.

Why is TryGetValue on a Dictionary who's key is also a dictionary returning Null?

SOLVED:

I tried to make my own IEqualitycomparer but couldn't get my dictionaries to use the Equals I defined in there. So I made a Recipe class instead and overrode the Equals there.

public class Recipe : ICraftable
    {
        public string Name { get; set; }
        public string Description { get; set; }
        public Dictionary<ICombinable, int> RequiredComponents { get; set; }
        public bool Unlocked { get; set; }

        public override bool Equals(object obj)
        {
            var otherDict = obj as Dictionary<ICombinable, int>;
            if (ReferenceEquals(otherDict, RequiredComponents)) return true;
            if (ReferenceEquals(otherDict, null)) return false;
            if (ReferenceEquals(RequiredComponents, null)) return false;
            if (otherDict.GetType() != RequiredComponents.GetType()) return false;
            return otherDict.Count == RequiredComponents.Count && AreValuesEqual(otherDict, RequiredComponents);
        }
        
        private bool AreValuesEqual(Dictionary<ICombinable, int> x, Dictionary<ICombinable, int> y)
        {
            var matches = 0;
            //Goal is to check if all ingredients have the same name on both sides. Then I'll check if they have the same amount
            foreach (var xKvp in x)
            {
                foreach (var yKvp in y)
                {
                    if (xKvp.Key.Name == yKvp.Key.Name && xKvp.Value == yKvp.Value)
                        matches++;
                }
            }
            return matches == x.Count;
        }
    }

I copied the first 4 lines from the default Equals you get with an IEqualityComparer and made a custom one for the 5th. My AreValuesEqual bool just checks if all the ingredients are present in the other dictionary by name and count.

I changed my Combiner class to use a Recipe object as key instead of a Dictionary and adjusted the methods for AddRecipe and Craft accordingly:

public class Combiner
    {
        private Dictionary<Recipe, ICraftable> _recipebook;

        public Combiner()
        {
            _recipebook = new Dictionary<Recipe, ICraftable>(); // <Recipe, Item it unlocks>
        }

        public void AddRecipe(Recipe recipe, ICraftable item) =>  _recipebook.Add(recipe, item);
        
        public ICraftable Craft(Dictionary<ICombinable, int> ingredientsAndAmount) =>
            _recipebook.FirstOrDefault(kvp=> kvp.Key.Equals(ingredientsAndAmount)).Value;
    }

And this is how I set up my unit test:

[Test]
    public void combiner_should_return_healing_potion()
    {
        // Use the Assert class to test conditions
        var combiner = new Combiner();
        var potion = new Item
        {
            Name = "Healing Potion",
            Unlocked = false
        };

        combiner.AddRecipe(new Recipe
            {
                Name = "Healing potion recipe",
                Description = "Invented by some sage",
                RequiredComponents = new Dictionary<ICombinable, int>
                {
                    {new Ingredient() { Name = "Herb", Description = "Has healing properties", Effect = Effect.Heal} , 3},
                    {new Ingredient {Name = "Water", Description = "Spring water", Effect = default}, 1},
                    {new Ingredient {Name = "Sugar", Description = "Sweetens", Effect = default}, 2}

                }
            },
            potion);

        var userGivenIngredientsAndAmount = combiner.Craft(new Dictionary<ICombinable, int>()
        {
            {new Ingredient() { Name = "Herb", Description = "Has healing properties", Effect = Effect.Heal} , 3},
            {new Ingredient {Name = "Water", Description = "Spring water", Effect = default}, 1},
            {new Ingredient {Name = "Sugar", Description = "Sweetens", Effect = default}, 2}
        });
        
        Assert.That(userGivenIngredientsAndAmount, Is.EqualTo(potion));
    }

And it is functioning as intended. Changing the Name or count in one of the dictionaries causes it to return null like it should. It's probably very inefficient! But I'm still at the 'make it work' stage. I will get to'make it nice, make it fast' soon.

Thanks everyone for putting me on the right track! I'd be happy to accept any advice on making this more efficient. But since it's working as intended, I'm marking this question as solved tomorrow.

Adding an item to a dictionary efficiently but doing += instead of =

The following code defines (and tests, if you paste it into LinqPad) a class that will let you do this using +=. However, if you are passing the dictionary around to lots of places, it won't work, because it has to hide the indexer with new rather than overriding it (the Dictionary's indexer isn't virtual).

One way to get around this would be by creating the DefaultingDictionary as an implementer of IDictionary<TKey, TValue> and within the class having a private member that's a Dictionary, and delegating all the calls to the methods on IDictionary through to that - except for the indexer, which you would do yourself. You still can't pass this to things expecting a Dictionary, but you could change those things to accept an IDictionary instead.

void Main()
{
    var dict = new DefaultingDictionary<string, double>();

    dict["one"] = 1;

    dict["one"] += 1;
    dict["two"] += 1;

    Console.WriteLine(dict["one"]);
    Console.WriteLine(dict["two"]);
}

class DefaultingDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
    public new TValue this[TKey key]
    {
        get
        {
            TValue v;
            if(TryGetValue(key, out v))
            {
                return v;
            }
            return default(TValue);
        }

        set
        {
            base[key] = value;
        }
    }
}

Honestly, this is all a lot of work just to be able to do the += thing. Really you should just do the check. There's no performance benefit to this, it just makes your code more complicated. If you do the check, somebody reading it will understand exactly what's going on.

What is the complexity of these Dictionary methods?

This routine, as a whole, is, effectively, O(m) time complexity, with m being the number of strings in your search.

This is because Dictionary.Contains and Dictionary.Add are both (normally) O(1) operations.

(It's slightly more complicated than that, as Dictionary.Add can be O(n) for n items in the Dictionary, but only when the dictionary capacity is small. As such, if you construct your dictionary with a large enough capacity up front, it would be O(m) for m string entries.)

That being said, if you're only using the Dictionary for existence checking, you could use a HashSet<string>. This would allow you to write:

  public void DistinctWords(String s)
  {
     HashSet<string> hash = new HashSet<string>(s.Split(' '));

     // Use hash here...

As your dictionary is a local variable, and not stored (at least in your code), you could also use LINQ:

 var distinctWords = s.Split(' ').Distinct();

Dictionary ContainsKey and get value in one function

You can use TryGetValue

int value;
bool exists = _dictionary.TryGetValue("key", out value);

TryGetValue returns true if it contains the specified key, otherwise, false.

---

Related Topics