Dictionary/Hashset build optimisation

Question

Is there any way to not check every time if the key is already there?

Assuming that

• we don't know all the possible keys before we iterate through list

• the new way should work faster

  var list = new List<Person>(); // { int Id; int DepartmentId; string Name; }
  ... // let's imagine that list is getting filled
  
  var dict = new Dictionary<int, List<Person>>();
  
  foreach (var p in list)
  {
     if(!dict.ContainsKey(p.DepartmentId))
          dict.Add(p.DepartmentId, new List<int>());
  
     dict[p.DepartmentId].Add(p);
  }
  

Answer 1

I can see two improvements, however each of them inherently still checks for key presence.

First one reduces the number of accesses to the dictionary. It is theoretically possible that this will be faster, but computational complexity remains the same, and in practice the difference will probably be negligible:

1)

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

foreach (var p in list)
{
    List<Person> value = null;

    if(!dict.TryGetValue(p.DepartmentId, out value))
    {
        value = new List<int>();
        dict.Add(p.DepartmentId, value);
    }

    value.Add(p);
}

Second improvement adds some syntactic sugar:

2)

public static class DictionaryExtensions
{
    public static TValue GetOrAdd<TKey, TValue>(
        this IDictionary<TKey, TValue> dictionary,
        TKey key) where TValue : new()
    {
        TValue value;
        if (!dictionary.TryGetValue(key, out value))
        {
            value = new TValue();
            dictionary.Add(key, value);
        }

        return value;
    }
}

And then:

foreach (var p in list)
{
    dict
        .GetOrAdd(p.DepartmentId)
        .Add(p.DepartmentId);
}

As Servy pointed out, you may want to add a parameter for GetOrAdd extension to have more control over creation of the default value.