Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

implement GetHashCode() for objects that contain collections

Tags:

c#

gethashcode

Consider the following objects:

class Route {    public int Origin { get; set; }    public int Destination { get; set; } } 

Route implements equality operators.

class Routing {    public List<Route> Paths { get; set; } } 

I used the code below to implement GetHashCode method for the Routing object and it seems to work but I wonder if that's the right way to do it? I rely on equality checks and as I'm uncertain I thought I'll ask you guys. Can I just sum the hash codes or do I need to do more magic in order to guarantee the desired effect?

public override int GetHashCode() => {     return (Paths != null                  ? (Paths.Select(p => p.GetHashCode())                         .Sum())                  : 0); } 

I checked several GetHashCode() questions here as well as MSDN and Eric Lippert's article on this topic but couldn't find what I'm looking for.

like image 951
Joanna Derks Avatar asked May 12 '12 21:05

Joanna Derks


People also ask

How is GetHashCode implemented?

For example, the implementation of the GetHashCode() method provided by the String class returns identical hash codes for identical string values. Therefore, two String objects return the same hash code if they represent the same string value.

Do I need to implement GetHashCode?

Yes, it is important if your item will be used as a key in a dictionary, or HashSet<T> , etc - since this is used (in the absence of a custom IEqualityComparer<T> ) to group items into buckets. If the hash-code for two items does not match, they may never be considered equal (Equals will simply never be called).

What is GetHashCode used for?

A hash code is a numeric value which is used to insert and identify an object in a hash-based collection. The GetHashCode method provides this hash code for algorithms that need quick checks of object equality.

Why do we need GetHashCode C#?

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 System.


2 Answers

I think your solution is fine. (Much later remark: LINQ's Sum method will act in checked context, so you can very easily get an OverflowException which means it is not so fine, after all.) But it is more usual to do XOR (addition without carry). So it could be something like

public override int GetHashCode() {   int hc = 0;   if (Paths != null)     foreach (var p in Paths)       hc ^= p.GetHashCode();   return hc; } 

Addendum (after answer was accepted):

Remember that if you ever use this type Routing in a Dictionary<Routing, Whatever>, a HashSet<Routing> or another situation where a hash table is used, then your instance will be lost if someone alters (mutates) the Routing after it has been added to the collection.

If you're sure that will never happen, use my code above. Dictionary<,> and so on will still work if you make sure no-one alters the Routing that is referenced.

Another choice is to just write

public override int GetHashCode() {   return 0; } 

if you believe the hash code will never be used. If every instace returns 0 for hash code, you will get very bad performance with hash tables, but your object will not be lost. A third option is to throw a NotSupportedException.

like image 171
Jeppe Stig Nielsen Avatar answered Sep 28 '22 02:09

Jeppe Stig Nielsen


The code from Jeppe Stig Nielsen's answer works but it could lead to a lot of repeating hash code values. Let's say you are hashing a list of ints in the range of 0-100, then your hash code would be guarnteed to be between 0 and 255. This makes for a lot of collisions when used in a Dictionary. Here is an improved version:

public override int GetHashCode() {   int hc = 0;   if (Paths != null)     foreach (var p in Paths) {         hc ^= p.GetHashCode();         hc = (hc << 7) | (hc >> (32 - 7)); //rotale hc to the left to swipe over all bits     }   return hc; } 

This code will at least involve all bits over time as more and more items are hashed in.

like image 38
usr Avatar answered Sep 28 '22 03:09

usr