combining hash codes

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

Zachary Turner - 08 Nov 2006 02:57 GMT

I want to use a custom object as a key in a Dictionary or SortedList,
and uniqueness is determined by more than just a specific field. I
know the "suggested" method is to xor all the hash codes together, but
this doesn't seem safe? For example, say

Key1 = (A, B)
Key2 = (C, D)

Is it possible to have the following situation?
A != C
B != D
A.GetHashCode() ^ B.GetHashCode() == C.GetHashCode() ^ D.GetHashCode()

Actually, I take that back. I know it's possible. For example, 1 ^ 2
== 5 ^ 6. But how serious of a problem is this in reality? There must
be some mitigating factor here that I'm missing, otherwise why would
examples of using XOR be strewn throughout the MSDN documentation?

Thanks for any insight.

Reply to this Message

Mattias Sjögren - 08 Nov 2006 05:52 GMT

>Actually, I take that back. I know it's possible. For example, 1 ^ 2
>== 5 ^ 6. But how serious of a problem is this in reality? There must
>be some mitigating factor here that I'm missing, otherwise why would
>examples of using XOR be strewn throughout the MSDN documentation?

Well hash codes don't have to be unique (they can't be), just have
"good enough" distribution. XORing is easy to understand and
implement, that's probably why it's used in MSDN. There are other
algorithms, see for example

http://groups.google.com/group/comp.lang.java.help/browse_thread/thread/3c34d38e
f488221a/50d54e5e2b16b564#50d54e5e2b16b564

Mattias

Signature

Mattias Sjögren [C# MVP] mattias @ mvps.org
http://www.msjogren.net/dotnet/ | http://www.dotnetinterop.com
Please reply only to the newsgroup.

Reply to this Message

Zachary Turner - 08 Nov 2006 19:39 GMT

> >Actually, I take that back. I know it's possible. For example, 1 ^ 2
> >== 5 ^ 6. But how serious of a problem is this in reality? There must
[quoted text clipped - 7 lines]
>
> http://groups.google.com/group/comp.lang.java.help/browse_thread/thread/3c34d38e
f488221a/50d54e5e2b16b564#50d54e5e2b16b564

Hmm, I was about to ask another question, but I think I just realized
that for quite a while I've been misunderstanding how the HashCode
based .NET Collections work. I know how hashtables work, and that in
typical Hashtable implementations you can have multiple entries with
the same hash code. When I read the .NET Documentation for Hashtables
a long time ago I (somehow) mistakenly interpreted it as saying that
you cannot insert two items with the same hash code. Instead, it just
says you cannot insert two entries A and B where A.Equals(B) is true,
which is what I expect anyway. Call me crazy, glad I cleared that up
though, what a major oversight :)

Reply to this Message

combining hash codes

Free Magazines