Saturday, July 18, 2009

c# Override GetHashCode when using dictionary in .Net

In .Net, Dictionary is implemented as HashTable. As you might know, Hashtable rely on hash algorithm to perform. Last week, I was involved in a performance enhancement task. One of the key performance bottleneck was due to an unimplemented hash algorithm. The task was trying to insert object in dictionary and trying to retrieve it when necessary.
Originally since the object is quite uncertain, and even some of the objects had override the GetHashCode method, it only returns 0, which then every object will get the same hash code. When ContainsKey called, the result is the dictionary get iterated, the algorithm checks so many Equals method. It is quite hard for us to write a genric hash algorithm for object, so I simply change the algorithm to return the hash code of GetType. Further detection of whether an object had override its GetHashCode method is added using reflection. (When an object property changs, ContainsKey method doesn't return the desired value for some object unless GetHashCode was overriden)

Looking back at the solution, simple, override both method. Sometimes, it really comes down to understand what MSDN says.

GetHashCode returns a value based on the current instance that is suited for hashing algorithms and data structures such as a hash table. Two objects that are the same type and are equal must return the same hash code to ensure that instances of HashTable and Dictionary</TKEY,> work correctly. To fix a violation of this rule, provide an implementation of GetHashCode. For a pair of objects of the same type, you must ensure that the implementation returns the same value if your implementation of Equals returns true for the pair.

Here is some sample code.

            public int GetHashCode( object obj )
MethodInfo mi = obj.GetType( ).GetMethod( "GetHashCode" );
if( ((mi.Attributes & MethodAttributes.NewSlot) == MethodAttributes.NewSlot) )
ordinaryObjectMapping.Add( obj, true );
return obj.GetHashCode( );
ordinaryObjectMapping.Add( obj, false );
return obj.GetType( ).GetHashCode( );