How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups?

nat — Tue, 21 Mar 2006 13:29:48 GMT

Hi Patel,

Will it actually slow things down as you have to concatenate two strings while have to get the hashcode from string? It seems to be an expensive operation. Would it be better to multiply the value with some prime value like in other sample?

public override int GetHashCode()
{
return a.GetHashCode() * 29 + b.GetHashCode();
}

Interesting Finds

Jason Haley — Tue, 21 Mar 2006 15:34:44 GMT

My Faq on "hashtable lookups for struct types" is published at http://blogs.msdn.com/CSharpFaq

C#, VS Deployment and all geek talk — Tue, 21 Mar 2006 18:53:22 GMT

&nbsp;
Check out
http://blogs.msdn.com/csharpfaq/archive/2006/03/20/556192.aspx&nbsp;
for a FAQ on...

re: How can I speed up hashtable lookups?

vipul — Tue, 21 Mar 2006 19:04:25 GMT

Hi Nat,

I agree that concatenate operations on strings are expensive.

But the lookup on struct if GetHashCode() is not overridden is very time-consuming. I got the idea of an faq about facing a real-life problem.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfsystemobjectclassgethashcodetopic.asp mentions the above point.

re: How can I speed up hashtable lookups?

mashiharu — Tue, 21 Mar 2006 21:20:12 GMT

After thinking about this for a while I wonder what you're trying to accomplish.

My first problem is your statement:

"Since you are generating hashcode explicitly which is guaranteed to be unique, it will boost the performance of your lookup."

Hashes are not unique.
http://en.wikipedia.org/wiki/Hash_function

re: How can I speed up hashtable lookups?

vipul — Tue, 21 Mar 2006 22:19:10 GMT

Hi mashiharu,

The purpose of this faq is to enable better lookup for structs. I will get in touch with the csharpfaq team to get the subject title of this post corrected.

Basically when you are trying to use struct objects as-is in the hashtable as a the key, the lookup is terrible. The purpose of the above code snippet is an example on how to generate hash code explicitly. Here, I have taken example of creating a string by concatenating all the fields of the struct and joining them using a predetermined key ':'.

Using string is just an example, you can use whatever mechanism you want, as long it guarantees
a. A hashcode generated for a struct type is unique and same, no matter how many times it is generated.
b. If your two struct objects are same, then the hash code generated should be the same.

Hope it clarifies. Please feel free to suggest any changes which will result in a better example. We are all here to learn and share.

Thanks
Vipul

re: How can I speed up hashtable lookups?

nat — Tue, 21 Mar 2006 22:27:18 GMT

My point is that using string to do hashing may actually slow your code down rather than making it faster especially in scenario of small data points or when the first field in the struct is well dispersed.

BTW, your perception on GetHashCode may be a little bit incorrect. GetHashCode on struct (or ValueType in C#) is overridden inside ValueType object. The default implementation is to get hash code from the first field only. Please read this for more detail... http://www.informit.com/content/images/0321245660/items/wagner_item10.pdf

But in Roter, it seems to use every field to calculate hash code though...
http://dotnet.di.unipi.it/Content/sscli/docs/doxygen/fx/bcl/valuetype_8cs-source.html

re: How can I speed up hashtable lookups?

vipul — Tue, 21 Mar 2006 22:27:25 GMT

Hi mashiharu,

Asnwering your original question, the string I am generating is bound to be unique as it is being generated from a set of struct objects which are used as a key for the hashtable. And since the string is unique, the GetHashCode on the string will definitely generate a unique hash code.

Thanks
Vipul

re: How can I speed up hashtable lookups with struct object as keys?

vipul — Tue, 21 Mar 2006 22:49:06 GMT

hi Nat,

<quote>
especially in scenario of small data points or when the first field in the struct is well dispersed.
<quote>

This is explicitly the condition which was not available to me for a real-life situation. My struct was composed of 11 fields(short, int, short, int,....)

and many(about 15%) of the value types had the same first field, they used to differ on the other fields. With 1,000,000+ records, my performance was dismal.

<quote>
GetHashCode on struct (or ValueType in C#) is overridden inside ValueType object. The default implementation is to get hash code from the first field only<quote>
In the reference, you have a string as the first member, which is quaranteed to be unique. That may not the case with other structs on other examples.

re: How can I speed up hashtable lookups with struct object as keys?

nat — Tue, 21 Mar 2006 22:58:33 GMT

btw, good news or not I don't know... .NET 2.0 seems to change the behavior to be what Rotor does. So you get the same behavior but it will be slower as it uses reflection to do the job.

re: How can I speed up hashtable lookups with struct object as keys?

mashiharu — Tue, 21 Mar 2006 23:27:02 GMT

"And since the string is unique, the GetHashCode on the string will definitely generate a unique hash code."

Wrong.

Try these examples:

Console.WriteLine("0:93121".GetHashCode());
Console.WriteLine("0:2546870".GetHashCode());

re: How can I speed up hashtable lookups with struct object as keys?

mashiharu — Tue, 21 Mar 2006 23:34:43 GMT

Or if you are on .net 1.1:

Console.WriteLine("0:22980214".GetHashCode());
Console.WriteLine("0:12538469".GetHashCode());

re: How can I speed up hashtable lookups with struct object as keys?

vipul — Tue, 21 Mar 2006 23:49:27 GMT

mashiharu,

yes, there is something fishy about ':'. I beleive it has something to do with the formating specifier.

I tried concatenating with '%' and '_' and it generated unique codes. Can you please verify, if they are also prone to a loop-hole. After your response, I will update the FAQ article accordingly. We need readers to have the best solution.

re: How can I speed up hashtable lookups with struct object as keys?

mashiharu — Tue, 21 Mar 2006 23:59:53 GMT

No, there is no problem with the ":" and it was a clever way to ensure the string are unique. The hash however is not (see wikipedia link above).

Example: You have a 2-bit number (0-3) which you want to generate a 1-bit (0-1) unique key for.

0 -> 0
1 -> 1
2 -> ?
3 -> ?

Can't be done.

You get the same problem when you try to take a 32 + 16 = 48 bit number and turn into a 32-bit unique key.

re: How can I speed up hashtable lookups with struct object as keys?

vipul — Wed, 22 Mar 2006 00:16:02 GMT

Mashiharu, can you please suggest a good workaround which can be used in the FAQ sample?

re: How can I speed up hashtable lookups with struct object as keys?

nat — Wed, 22 Mar 2006 00:19:52 GMT

why don't you use the way i suggest? It should work...and it performs much better.

public override int GetHashCode()
{
return a.GetHashCode() * 29*29 + b.GetHashCode()*29 + c.GetHashCode() + ....;
}

re: How can I speed up hashtable lookups with struct object as keys?

nat — Wed, 22 Mar 2006 00:23:03 GMT

If you say so, then you might need to change the wording in your blog that "Since you are generating hashcode explicitly which is guaranteed to be unique". The key to generate code may be unique in your case but not the hash code itself.

re: How can I speed up hashtable lookups with struct object as keys?

Omer van Kloeten — Thu, 23 Mar 2006 10:09:47 GMT

The Framework Design Guidelines specify that the maximum size of a struct should be around 16 bytes. That's around four integer fields, which is probably a lot less than the 11 fields you have.
Maybe the performance hit should be solved by changing the struct to a class...

.Net Performance pointers

Dotmad (on .Net) — Fri, 14 Mar 2008 15:33:50 GMT

After going this week to the Microsoft performance open house , here are few things to consider: Create

Great C# Resource! « Alexander The Great

Great C# Resource! « Alexander The Great — Tue, 15 Apr 2008 22:10:58 GMT

PingBack from http://alexandersarchive.wordpress.com/2008/04/15/great-c-sharp-resource/

re: How can I speed up hashtable lookups with struct object as keys?

Brian — Fri, 30 Oct 2009 13:57:52 GMT

The easiest way to speed up hashcode lookups on any object is to override the GetHashCode function to return an int that is generated at object creation time. This makes it so the HashCode only gets generated once (when the object is created) rather than every time the GetHashCode function is called. There are issues with using this technique with mutable objects...but this is true even if you don't use this technique.

How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups?

Interesting Finds

My Faq on &quot;hashtable lookups for struct types&quot; is published at http://blogs.msdn.com/CSharpFaq

re: How can I speed up hashtable lookups?

re: How can I speed up hashtable lookups?

re: How can I speed up hashtable lookups?

re: How can I speed up hashtable lookups?

re: How can I speed up hashtable lookups?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

re: How can I speed up hashtable lookups with struct object as keys?

.Net Performance pointers

Great C# Resource! « Alexander The Great

re: How can I speed up hashtable lookups with struct object as keys?

My Faq on "hashtable lookups for struct types" is published at http://blogs.msdn.com/CSharpFaq