Optimizing a Dictionary for comparison when the key is based upon several identifying attributes.

Question

I have the following code:

if (!this._masterAccountDefinitions.ContainsKey(
     outletName.ToLower(CultureInfo.CurrentCulture) + "/" +
     officeName.ToLower(CultureInfo.CurrentCulture))
   ) {
     //Add new item to list
}

Essentially, the dictionary is keyed by the combination of an Outlet Name and Office Name. This code will be called extensively and it just seems to do some pretty harsh string transformation. I'm looking for suggestions on a more efficient way of keying the dictionary than simply concatenating the string values.

Answer 1

Do you have evidence of this causing a problem? I wouldn't expect it to cause any issues - and I can't think of anything that is really like to help much, unless you want to key by one name to get a "sub-dictionary" that is keyed by the other name - but that's going to make the code uglier and I can't see it improving performance in most cases.

Answer 2

Assuming that by efficiency you mean performance - it's hard to speculate what changes to the approach of concatenating strings as a key will yield better performance - you have to first understand what the bottlenecks are.

However, one idea that comes to mind is to create a separate class to just represent the key and override its Equals() and GetHashCode() methods. They would use the individual fields using case-insensitive comparison in Equals() and XOR'ing the hash codes in GetHashCode().

This may help avoid the cost of converting the strings to lower-case and eliminate the need to concatenate them. However, it introduces the cost of keying the collection with a custom class that needs to be instantiated for each item stored in the dictionary. Also, the hashing algorithm may be less optimal (ie cause more collisions) than hashing a concatenated string.

I would strongly advise you to spend some time profiling your code to determine that just concatenating the strings isn't efficient enough in your case - before converting to a more complicated alternative.

Here's a very crude prototype to start with:

public class AccountKey
{
   private readonly string m_OutletName;
   private readonly string m_OfficeName;

   public AccountKey( string outlet, string office )
   {
      m_OutletName = outlet;
      m_OfficeName = office;
   }

   public string OutletName { get { return m_OutletName; } }
   public string OfficeName { get { return m_OfficeName; } }

   public override bool Equals( object otherKey )
   { 
      AccountKey otherAccountKey = otherKey as AccountKey;      
      if( otherAccountKey == null )
         return false;

      // uses Compare( s1, s2, ignoreCase ) overload - which assumes current culture
      // alternative culture can be passed in as another parameter after ignore case
      // uses short-circuit and to avoid comparing both strings if one already differs
      // you could order these based on your domain knowledge more optimally - for
      // example if Offices vary more frequently than Outlet, make that compare first.
      return String.Compare( m_OutletName, otherAccountKey.OutletName, true ) == 0 &&
             String.Compare( m_OfficeName, otherAccountKey.OfficeName, true ) == 0;
   }

   public override int GetHasCode()
   {
      // this may not be optimal, but it's a starting point
      return OutletName.GetHashCode() ^ OfficeName.GetHashCode();
   }
}