How can I speed up hashtable lookups with struct object as keys?
When you have struct objects as the key in a hashtable, the lookup operation of the hashtable performs miserably. This can be attributes to the GetHashCode() function which is used internally to do the lookup.
If a struct contains only simple value types (int, short, etc.), the algorithm which computes the GetHashCode creates hashes which fall into mostly the same bucket.
Example, lets say, the hashtable creates 10 buckets. Then, most probably, all the keys are being put into the same bucket. Hence when a lookup is performed, the .NET runtime has to traverse through this entire bucket to get the value.
BUCKET1 - Value1, Value2, Value3,...,valuen
BUCKET2 - (empty)
BUCKET3 - (empty)
BUCKET4 - (empty)
BUCKET5 - (empty)
BUCKET6 - (empty)
BUCKET7 - (empty)
BUCKET8 - (empty)
BUCKET9 - (empty)
BUCKET10- (empty)
Hence, instead of the lookup operation being O(1), it becomes O(n) on an average case.
To overcome this drawback, consider overriding the GetHashCode() function and making the life easier for the .NET Runtime.
An example would be to create a string by merging all your value types in the struct and joining them by using a special character as a demarcator.
Since your struct is a lookup criteria, it is sure that all the struct values will be different, and hence the string generated is guaranteed unique.
Now the string generated has a method(GetHashCode()), since it is derived from System.Object (like all other objects). Just return the output of this API. A code example will help to understand better.
struct
{
int a;
short b;
public struct(int _a, short _b)
{
a = _a;
b = _b;
}
public override int GetHashCode()
{
string hash = a.ToString() + ":" b.ToString();
return hash.GetHashCode();
}
}
Since you are generating hashcode explicitly which is guaranteed to be unique, it will boost the performance of your lookup.
Reference: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfsystemobjectclassgethashcodetopic.asp
[author: Vipul Patel, C# MVP]
