implement GetHashCode() for objects that contain collections

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.

GetHashCode()

GetHashCode

GetHashCode

List<Route>

List<>

GetHashCode

System.Object

5 Answers
5

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

Sum

checked

OverflowException

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.

Routing

Dictionary<Routing, Whatever>

HashSet<Routing>

Routing

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.

Dictionary<,>

Routing

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.

0

NotSupportedException

GetHashCode()

Equals

Equals

List<>

GetHashCode

Equals

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.

GetHashCode()

Route

GetHashCode()

Routing

As a guideline, the hash of an object must be the same over the object's entire lifetime. I would leave the GetHashCode function alone, and not overwrite it. The hash code is only used if you want to put your objects in a hash table.

GetHashCode

You should read Eric Lippert's great article about hash codes in .NET: Guidelines and rules for GetHashCode.

Quoted from that article:

Guideline: the integer returned by GetHashCode should never change

Rule: the integer returned by GetHashCode must never change while the object is contained in a data structure that depends on the hash code remaining stable

If an object's hash code can mutate while it is in the hash table then clearly the Contains method stops working. You put the object in bucket #5, you mutate it, and when you ask the set whether it contains the mutated object, it looks in bucket #74 and doesn't find it.

The GetHashCode function you implemented will not return the same hash code over the lifetime of the object. If you use this function, you will run into trouble if you add those objects to a hash table: the Contains method will not work.

GetHashCode

Contains

.NET now has HashCode.Combine, you can use Accumulator to combine hashcodes.

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

public override int GetHashCode() => Paths.Aggregate(GetType().GetHashCode(), (hash, i) => HashCode.Combine(hash, i));
}


Routing.GetHashCode will start an accumulator with the 'seed' being the hashcode of the type (Routing.GetHashCode()) and combine into it the hashcodes of all Path's elements

I don't think it's a right way to do, cause to dtermine the final hashcode it has to be unique for specifyed object. In your case you do a Sum(), which can produce the same result with different hashcodes in collection (at the end hashcodes are just integers).

hashcode

Sum()

If your intention is to determine equality based on the content of the collection, at this point just compare these cillections between two objects. It could be time consuming operation, by the way.

int

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.