Right way to implement GetHashCode for this struct

Question

I want to use a date range (from one date to another date) as a key for a dictionary, so I wrote my own struct:

   struct DateRange
   {
      public DateTime Start;
      public DateTime End;

      public DateRange(DateTime start, DateTime end)
      {
         Start = start.Date;
         End = end.Date;
      }

      public override int GetHashCode()
      {
         // ???
      }
   }

What's the best way to implement GetHashCode so no two objects of a differing range will generate the same hash? I want hash collisions to be as unlikely as possible, though I understand Dictionary<> will still check the equality operator which I will also implement, but didn't want to pollute the example code too much. Thanks!

Solution 1

You can use the method from Effective Java as Jon Skeet shows here. For your specific type:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        hash = hash * 23 + Start.GetHashCode();
        hash = hash * 23 + End.GetHashCode();
        return hash;
    }
}

Solution 2

In C# 7 you can do this:

public override int GetHashCode() => (Start, End).GetHashCode();

The ValueTuple is available in .NET Framework 4.7 and .NET Core, or via NuGet.

Not sure how well it performs, but I would be surprised if any custom code would beat it.

Solution 3

I would trust Microsoft's implementation of GetHashCode() at the tuples and use something like this without any stupid magic:

public override int GetHashCode()
{
    Tuple.Create(x, y).GetHashCode();
}

Solution 4

Since DateTime.GetHashCode is internally based on Ticks, what about this:

    public override int GetHashCode()
    {
        return unchecked((int)(Start.Ticks ^ End.Ticks));
    }

Or, since you seem to be interested by the date parts (year, month, day), not the whole thing, this implementation uses the number of days between the two dates and should give almost no collision:

        public override int GetHashCode()
        {
            return unchecked((int)Start.Date.Year * 366 + Start.Date.DayOfYear + (End.Date - Start.Date).Days);
        }

Solution 5

Not to reanimate the dead, but I came here looking for something, and for newer C# versions you can do

public override int GetHashCode()
{
    return HashCode.Combine(Start, End);
}

The source can currently be found here: https://github.com/dotnet/corert/blob/master/src/System.Private.CoreLib/shared/System/HashCode.cs

In my preliminary tests (using Jon Skeets micro benchmarking framework) it appears to be very similar if not the same as the accepted answer, in terms of performance.

View more solutions

Comments

[Jesse C. Slicer]

-1: while this is good, it's a pretty close to direct lift from here: stackoverflow.com/questions/263400/… without attribution.

[DarthVader]

very funny. attribution was to Joshua bloch which that links get this from.. thanks for the downvote.

[Jesse C. Slicer]

Your four retribution downvotes are also totally unnecessary.

[DarthVader]

i dont want to make it personal.but your comment was pointless, and i did give the credits to joshua bloch, who has pointed this hashcode impl. in his book.

[Joe White]

Why are people downvoting this and upvoting Mark Byers' answer, when they're essentially the same answer?

[DarthVader]

Because I m on the dark side. i guess that s why.

[Jesse C. Slicer]

I downvoted because, while perhaps originally discussed on Joshua Bloch's book, the C# code presented is clearly Jon Skeet's implementation (including the comment), which was not credited. Mark Byers' answer DID credit the code source.

[Jesse C. Slicer]

Now there you go. Removing my downvote. Next time, don't make Obi-Wan more powerful than we could possibly imagine.

[Jesse C. Slicer]

Of course, looking at it now, seems like it would be a good idea to override 'Equals()', 'operator==' and 'operator!=' too.

[Max Kilovatiy]

Could you please explain, why do you use 17 and 23?

[Martin]

@MaxKvt because they're prime numbers

[The incredible Jan]

@Martin And where is the benefit from multiplication with prime numbers?

[Herman]

@TheincredibleJan My guess is that it improves the distribution of values after the modulo is applied (in this case modulo is implicit when int overflows). I'm not sure about this but I think (x * prime) mod y will not generate a collision for values of x between 0 and y.

[l33t]

No!! You must absolutely NOT create heap objects in GetHashCode(). This code will eventually kill application performance.

[Benji Altman]

I'm not sure how new this solution is, but when I tried that Visual Studio gave me a code hint of System.HashCode.Combine(Start, End).

[dynamichael]

Note: System.HashCode is only available in .Net Core

[Mike Christensen]

Would be curious to know how it compares to the accepted answer in terms of perf..

[VisualBean]

I checked it out. And it appears to be VERY similar over 10000000 runs.

[Mike Christensen]

Cool, I bet the code is basically the same and the compiler inlines the function..

[WDUK]

If every hash has 17 and a factor of 23 then surely they can be factored out between all hashes wouldn't it be the same as just adding the hash codes of start and end together and be done with it ?

[dynamichael]

The Tuple class will add to the heap. Instead (with C# 8 up), use just (x, y).GetHashCode(), which goes on the stack it's a value type.

[WDUK]

Don't you need to implement an interface aswell for hash sets and dictionaries to use it?