Good resource for explaining how hash codes are used in collections

views:

answers:

+1 Q:

Good resource for explaining how hash codes are used in collections

Hi,

Can anyone give a good explanation and / or links to a good resource of how hash codes are used in storing and retrieving objects in hashtables, dictionaries etc, specifically in C# / .NET.

I'm interested to see how Equals and GetHashCode are used collectively when storing and retrieving items.

+1 A:

It depends on the collection, but for a dictionary the hash code is used to determine which bucket the object is added to, and Equals is used to find the item within the bucket, amongst other items which may have the same hash.

Mark Byers 2010-04-22 22:04:24

Could you give an example where two objects would have the same hash code (and therefore be in the same bucket), but are not considered equal with Equals?By bucket, what does this really mean? Areas of the container to group objects within?

Michael 2010-04-22 22:14:54

@Michael: Sure. Note that the GetHashCode() implementation is not specified and can in theory change between .NET versions, but you can try it for these two strings: "zqhrehjt" and "ogjhvzfp". I get `"zqhrehjt".GetHashCode() == "ogjhvzfp".GetHashCode()` the value being -1985547583 in both cases. And you are right that the objects are grouped inside the container. Ideally though each group should only contain one object. If objects end in the same bucket it is called a collision and can cause poor performance. If there are too many collisions the number of buckets is increased.

Mark Byers 2010-04-22 22:22:00

@Michael: Also note that two items can end up in the same bucket even if they have a different hash code because the number of buckets is always less than the number of possible hash codes. If the number of buckets is increased then they might then end up in different buckets.

Mark Byers 2010-04-22 22:26:50

try object.GetHashCode.

"A hash code is a numeric value that is used to identify an object during equality testing. It can also serve as an index for an object in a collection. The GetHashCode method is suitable for use in hashing algorithms and data structures such as a hash table."

James Westgate 2010-04-22 22:04:52

+1 A:

This is a pretty good demo: http://research.cs.vt.edu/AVresearch/hashing/buckethash.php

codekaizen 2010-04-22 22:07:20

ansaurus

tags:

views:

answers:

Good resource for explaining how hash codes are used in collections

related questions