Proposal: Add System.HashCode to make it easier to generate good hash codes.

[jamesqo]

Update 6/16/17: Looking for volunteers

The API shape has been finalized. However, we're still deciding on the best hash algorithm out of a list of candidates to use for the implementation, and we need someone to help us measure the throughput/distribution of each algorithm. If you'd like to take that role up, please leave a comment below and @karelz will assign this issue to you.

Update 6/13/17: Proposal accepted!

Here's the API that was approved by @terrajobst at https://github.com/dotnet/corefx/issues/14354#issuecomment-308190321:

// Will live in the core assembly
// .NET Framework : mscorlib
// .NET Core      : System.Runtime / System.Private.CoreLib
namespace System
{
    public struct HashCode
    {
        public static int Combine<T1>(T1 value1);
        public static int Combine<T1, T2>(T1 value1, T2 value2);
        public static int Combine<T1, T2, T3>(T1 value1, T2 value2, T3 value3);
        public static int Combine<T1, T2, T3, T4>(T1 value1, T2 value2, T3 value3, T4 value4);
        public static int Combine<T1, T2, T3, T4, T5>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5);
        public static int Combine<T1, T2, T3, T4, T5, T6>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6);
        public static int Combine<T1, T2, T3, T4, T5, T6, T7>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6, T7 value7);
        public static int Combine<T1, T2, T3, T4, T5, T6, T7, T8>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6, T7 value7, T8 value8);

        public void Add<T>(T value);
        public void Add<T>(T value, IEqualityComparer<T> comparer);

        [Obsolete("Use ToHashCode to retrieve the computed hash code.", error: true)]
        [EditorBrowsable(Never)]
        public override int GetHashCode();

        public int ToHashCode();
    }
}

The original text of this proposal follows.

Rationale

Generating a good hash code should not require use of ugly magic constants and bit twiddling on our code. It should be less tempting to write a bad-but-concise GetHashCode implementation such as

class Person
{
    public override int GetHashCode() => FirstName.GetHashCode() + LastName.GetHashCode();
}

Proposal

We should add a HashCode type to enscapulate hash code creation and avoid forcing devs to get mixed up in the messy details. Here is my proposal, which is based off of https://github.com/dotnet/corefx/issues/14354#issuecomment-305019329, with a few minor revisions.

// Will live in the core assembly
// .NET Framework : mscorlib
// .NET Core      : System.Runtime / System.Private.CoreLib
namespace System
{
    public struct HashCode
    {
        public static int Combine<T1>(T1 value1);
        public static int Combine<T1, T2>(T1 value1, T2 value2);
        public static int Combine<T1, T2, T3>(T1 value1, T2 value2, T3 value3);
        public static int Combine<T1, T2, T3, T4>(T1 value1, T2 value2, T3 value3, T4 value4);
        public static int Combine<T1, T2, T3, T4, T5>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5);
        public static int Combine<T1, T2, T3, T4, T5, T6>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6);
        public static int Combine<T1, T2, T3, T4, T5, T6, T7>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6, T7 value7);
        public static int Combine<T1, T2, T3, T4, T5, T6, T7, T8>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6, T7 value7, T8 value8);

        public void Add<T>(T value);
        public void Add<T>(T value, IEqualityComparer<T> comparer);
        public void AddRange<T>(T[] values);
        public void AddRange<T>(T[] values, int index, int count);
        public void AddRange<T>(T[] values, int index, int count, IEqualityComparer<T> comparer);

        [Obsolete("Use ToHashCode to retrieve the computed hash code.", error: true)]
        public override int GetHashCode();

        public int ToHashCode();
    }
}

Remarks

See @terrajobst's comment at https://github.com/dotnet/corefx/issues/14354#issuecomment-305019329 for the goals of this API; all of his remarks are valid. I would like to point out these ones in particular, however:

• The API does not need to produce a strong cryptographic hash
• The API will provide "a" hash code, but not guarantee a particular hash code algorithm. This allows us to use a different algorithm later or use different algorithms on different architectures.
• The API will guarantee that within a given process the same values will yield the same hash code. Different instances of the same app will likely produce different hash codes due to randomization. This allows us to ensure that consumers cannot persist hash values and accidentally rely on them being stable across runs (or worse, versions of the platform).

[AlexRadch]

Proposal: add hash randomization support

public static HashCode Randomized<T> { get; } // or CreateRandomized<T>
or 
public static HashCode Randomized(Type type); // or CreateRandomized(Type type)

T or Type type is needed to get the same randomized hash for the same type.

[AlexRadch]

Proposal: add support for collections

public HashCode Combine<T>(T[] values);
public HashCode Combine<T>(T[] values, IEqualityComparer<T> comparer);
public HashCode Combine<T>(Span<T> values);
public HashCode Combine<T>(Span<T> values, IEqualityComparer<T> comparer);
public HashCode Combine<T>(IEnumerable<T> values);
public HashCode Combine<T>(IEnumerable<T> IEqualityComparer<T> comparer);

[AlexRadch]

I think there is no need in overloads Combine(_field1, _field2, _field3, _field4, _field5) because next code HashCode.Empty.Combine(_field1).Combine(_field2).Combine(_field3).Combine(_field4).Combine(_field5); should be inline optimized without Combine calls.

[jamesqo]

@AlexRadch

Proposal: add support for collections

Yes, that was part of my eventual plan for this proposal. I think it's important to focus on how we want the API to look like before we go about adding those methods, though.

[CyrusNajmabadi]

He wanted to use a different algorithm, like the Marvin32 hash which is used for strings in coreclr. This would require expanding the size of HashCode to 8 bytes.

What about having Hash32 and Hash64 types that would internally store 4 or 8 bytes worth of data? Document the pros/cons of each. Hash64 being good for X, but being potentially slower. Hash32 being faster, but potentially not as distributed (or whatever the tradeoff actually is).

He wanted to randomize the hash seed, so hashes would not be deterministic.

This seems like useful behavior. But i could see people wanting to control this. So perhaps there should be two ways to create the Hash, one that takes no seed (and uses a random seed) and one that allows the seed to be provided.

[CyrusNajmabadi]

Note: Roslyn would love if this could be provided in the Fx. We're adding a feature to spit out a GetHashCode for the user. Currently, it generates code like:

        public override int GetHashCode()
        {
            var hashCode = -1923861349;
            hashCode = hashCode * -1521134295 + this.b.GetHashCode();
            hashCode = hashCode * -1521134295 + this.i.GetHashCode();
            hashCode = hashCode * -1521134295 + EqualityComparer<string>.Default.GetHashCode(this.s);
            return hashCode;
        }

This is not a great experience, and it exposes many ugly concepts. We would be thrilled to have a Hash.Whatever API that we could call through instead.

Thanks!

[tannergooding]

What about MurmurHash? It is reasonably fast and has very good hashing properties. There is also two different implementations, one that spits out 32-bit hashes and another that spits out 128-bit hashes.

[tannergooding]

There is also vectorized implementations for both the 32-bit.and 128-bit formats.

[jamesqo]

@tannergooding MurmurHash is fast, but not secure, from the sounds of this blog post.

[jamesqo]

@jkotas, has there been any work in the JIT around generating better code for >4-byte structs on 32-bit since our discussions last year? Also, what do you think of @CyrusNajmabadi's proposal:

What about having Hash32 and Hash64 types that would internally store 4 or 8 bytes worth of data? Document the pros/cons of each. Hash64 being good for X, but being potentially slower. Hash32 being faster, but potentially not as distributed (or whatever the tradeoff actually is).

I still think this type would be very valuable to offer to developers and it would be great to have it in 2.0.

[tannergooding]

@jamesqo, I don't think this implementation needs to be cryptographically secure (that is the purpose of the explicit cryptographically hashing functions).

Also, that article applies to Murmur2. The issue has been resolved in the Murmur3 algorithm.

[jkotas]

the JIT around generating better code for >4-byte structs on 32-bit since our discussions last year

I am not aware of any.

what do you think of @CyrusNajmabadi's proposal

The framework types should be simple choices that work well for 95%+ of cases. They may not be the fastest ones, but that's fine. Having you to choose between Hash32 and Hash64 is not a simple choice.

[CyrusNajmabadi]

That's fine with me. But can we at least have a good-enough solution for those 95% cases? Right now there's nothing... :-/

[jkotas]

hashCode = hashCode * -1521134295 + EqualityComparer.Default.GetHashCode(this.s);

@CyrusNajmabadi Why are you calling EqualityComparer here, and not just this.s.GetHashCode()?

[CyrusNajmabadi]

For non-structs: so that we don't need to check for null.

This is close to what we generate for anonymous types behind the scenes as well. I optimize the case of known non-null values to generate code that would be more pleasing to users. But it would be nice to just have a built in API for this.

[jkotas]

The call to EqualityComparer.Default.GetHashCode is like 10x+ more expensive than check for null... .

[CyrusNajmabadi]

The call to EqualityComparer.Default.GetHashCode is like 10x+ more expensive than check for null..

Sounds like a problem. if only there were good hash code API we could call in the Fx that i could defer to :)

(also, we have that problem then in our anonymous types as that's what we generate there as well).

Not sure what we do for tuples, but i'm guessing it's similar.

[jkotas]

Not sure what we do for tuples, but i'm guessing it's similar.

System.Tuple goes through EqualityComparer<Object>.Default for historic reasons. System.ValueTuple calls Object.GetHashCode with null check - https://github.com/dotnet/coreclr/blob/master/src/mscorlib/shared/System/ValueTuple.cs#L809.

[CyrusNajmabadi]

Oh no. Looks like tuple can just use "HashHelpers". Could that be exposed so that users can get the same benefit?

[CyrusNajmabadi]

Great. I'm happy to do something similar. I started from our anonymous types because i figured they were reasonable best practices. If not, that's fine. :)

But that's not why i'm here. I'm here to get some system that actually combines the hashes effectively. If/when that can be provided we'll gladly move to calling into that instead of hardcoding in random numbers and combining hash values ourselves.

[jkotas]

What would be the API shape that you think would work best for the compiler generated code?

[CyrusNajmabadi]

Literally any of the 32bit solutions that were presented earlier would be fine with me. Heck, 64bit solutions are fine with me. Just some sort of API that you can get that says "i can combine hashes in some sort of reasonable fashion and produce a reasonably distributed result".

[CyrusNajmabadi]

I can't reconcile these statements:

We had an immutable HashCode struct that was 4 bytes in size. It had a Combine(int) method, which mixed in the provided hash code with its own hash code via a DJBX33X-like algorithm, and returned a new HashCode.

@jkotas did not think the DJBX33X-like algorithm was robust enough.

And

The framework types should be simple choices that work well for 95%+ of cases.

Can we not come up with a simple 32bit accumulating hash that works well enough for 95% of cases? What are the cases that aren't handled well here, and why do we think they're in the 95% case?

[jamesqo]

@jkotas, is performance really that critical for this type? I think on average things like hashtable lookups and this would take up way more time than a few struct copies. If it does turn out to be a bottleneck, would it be reasonable to ask the JIT team to optimize 32-bit struct copies after the API is released so they have some incentive, rather than blocking this API on that when nobody is working on optimizing copies?

[jkotas]

Can we not come up with a simple 32bit accumulating hash that works well enough for 95% of cases?

We have been burnt really badly by default 32bit accumulating hash for strings, and that's why Marvin hash for strings in .NET Core - https://github.com/dotnet/corert/blob/87e58839d6629b5f90777f886a2f52d7a99c076f/src/System.Private.CoreLib/src/System/Marvin.cs#L25. I do not think we want to repeat same mistake here.

@jkotas, is performance really that critical for this type?

I do not think the performance is critical. Since it looks like that this API is going to be used by auto-generated compiler code, I think we should be preferring smaller generated code over how it looks. The non-fluent pattern is smaller code.

[CyrusNajmabadi]

We have been burnt really badly by default 32bit accumulating hash for string

That doesn't seem like the 95% case. We're talking about normal developers just wanting a "good enough" hash for all those types where they manually do things today.

Since it looks like that this API is going to be used by auto-generated compiler code, I think we should be preferring smaller generated code over how it looks. The non-fluent pattern is smaller code.

This is not for use by the Roslyn compiler. This is for use by the Roslyn IDE when we help users generate GetHashCodes for their types. THis is code that the user will see and have to maintain, and having something sensible like:

   return Hash.Combine(this.A?.GetHashCode() ?? 0,
                       this.B?.GetHashCode() ?? 0,
                       this.C?.GetHashCode() ?? 0);

is a lot nicer than a user seeing and having to maintain:

            var hashCode = -1923861349;
            hashCode = hashCode * -1521134295 + this.b.GetHashCode();
            hashCode = hashCode * -1521134295 + this.i.GetHashCode();
            hashCode = hashCode * -1521134295 + EqualityComparer<string>.Default.GetHashCode(this.s);
            return hashCode;

[CyrusNajmabadi]

I mean, we already have this code in the Fx:

https://github.com/dotnet/roslyn/blob/master/src/Compilers/Test/Resources/Core/NetFX/ValueTuple/ValueTuple.cs#L5

We think it's good enough for tuples. It's unclear to me why it would be such a problem to make it available for users who want it for their own types.

Note: we've even considered doing this in roslyn:

return (this.A, this.B, this.C).GetHashCode();

But now you're forcing people to generate a (potentially large) struct just to get some sort of reasonable default hashing behavior.

[jkotas]

We're talking about normal developers just wanting a "good enough" hash for all those types where they manually do things today.

The original string hash was a "good enough" hash that worked well for normal developers. But then it was discovered that ASP.NET webservers were vulnerable to DoS attacks because they tend to store received stuff in hashtables. So the "good enough" hash basically turned into a bad security issue.

We think it's good enough for tuples

No necessarily. We made a back stop measure for tuples to make the hashcode randomized that gives us option to modify the algorithm later.

[jkotas]

     return Hash.Combine(this.A?.GetHashCode() ?? 0,
                         this.B?.GetHashCode() ?? 0,
                         this.C?.GetHashCode() ?? 0);

This looks reasonable to me.

[jnm2]

How awful would it be to add the HashCode source to the project like Roslyn does (with IL) with (the much simpler) compiler attribute class definitions when they aren't available through any referenced assembly?

[CyrusNajmabadi]

How awful would it be to add the HashCode source to the project like Roslyn does with (the much simpler) compiler attribute class definitions when they aren't available through any referenced assembly?

1. Does the HashCode source not need overflow behavior?
2. I've skimmed the HashCode source. It's non trivial. Generating all that goop into the user's project would be pretty heavyweight.

I'm just surprised there are no good ways to get overflow math to work in VB at all :(

[CyrusNajmabadi]

So, at a minimum, even if we were hashing two values together, it seems like we would have to create:

            var hc1 = (uint)(value1?.GetHashCode() ?? 0); // can overflow
            var hc2 = (uint)(value2?.GetHashCode() ?? 0); // can overflow

            uint hash = MixEmptyState();
            hash += 8; // can overflow

            hash = QueueRound(hash, hc1);
            hash = QueueRound(hash, hc2);

            hash = MixFinal(hash);
            return (int)hash; // can overflow

Note that this code already has 4 lines that can overflow. It also has two helper functions you need to call (i'm ignoring MixEmptyState as that seems more like a constant). MixFinal can definitely overflow:

        private static uint MixFinal(uint hash)
        {
            hash ^= hash >> 15;
            hash *= Prime2;
            hash ^= hash >> 13;
            hash *= Prime3;
            hash ^= hash >> 16;
            return hash;
        }

as can QueueRound:

        private static uint QueueRound(uint hash, uint queuedValue)
        {
            hash += queuedValue * Prime3;
            return Rol(hash, 17) * Prime4;
        }

So i don't honestly see how this would work :(

[CyrusNajmabadi]

How awful would it be to add the HashCode source to the project like Roslyn does (with IL) with (the much

How do you envision this working? What would customers write, and what would the compilers then do in response?

[CyrusNajmabadi]

Also, something that would address all of this is if .Net already has public helpers exposed on the surface API that convert from uint to int32 (and vice versa) without overflow.

Do those exist? If so, i can easily write the VB versions, just using these for the situations where we need to go between the types without overflowing.

[CyrusNajmabadi]

Is table-generation code also unpalatable?

I would think so. I mean, think about this from a customer perspective. They just want a decent GetHashCode method that is nicely self contained and gives reasonable results. Having that feature go and bloat up their code with auxiliary crap is going to be pretty unpleasant. It's also pretty bad given that the C# experience will be just fine.

[morganbr]

You might be able to get roughly the right overflow behavior by casting to and from some combination of signed and unsigned 64-bit types. Something like this (untested and I don't know VB casting syntax):

Dim hashCode = -252780983
hashCode = (Int32)((Int32)((Unt64)hashCode * -1521134295) + (UInt64)i.GetHashCode())

[CyrusNajmabadi]

How do you knwo the following doesn't overflow?

(Int32)((Unt64)hashCode * -1521134295)

Or the final (int32) cast for that matter?

[morganbr]

I didn't realize it would use overflow-checked conv operations. I guess you could mask it down to 32 bits before casting:

(Int32)(((Unt64)hashCode * -1521134295) & 0xFFFFFFFF)

[CyrusNajmabadi]

presumably 31 bits, as a value of uint32.Max would also overflow on conversion to Int32 :)

That's def possible. Ugly... but possible :) There's gunna be a lot of casts in this code.

[CyrusNajmabadi]

Ok. I think i have a workable solution. The core of the algorithm we generate today is:

        hashCode = hashCode * -1521134295 + j.GetHashCode();

Let's say that we're doing 64bit math, but "hashCode" has been capped to 32 bits. Then <largest_32_bit> * -1521134295 + <largest_32_bit> will not overflow 64 bits. So we can always do the math in 64 bits, then clamp down to 32 (or 32bits) to ensure that the next round won't overflow.

[CyrusNajmabadi]

Thanks!

[CyrusNajmabadi]

@MaStr11 @morganbr @sharwell and everyone here. I've updated my code to generate the following for VB:

        Dim hashCode As Long = 2118541809
        hashCode = (hashCode * -1521134295 + a.GetHashCode()) And Integer.MaxValue
        hashCode = (hashCode * -1521134295 + b.GetHashCode()) And Integer.MaxValue
        Return CType(hashCode And Integer.MaxValue, Integer)

Can someone sanity check me to make sure that this makes sense and should not overflow even with checked mode on?

[morganbr]

@CyrusNajmabadi , that won't overflow (because Int64.Max = Int32.Max*Int32.Max and your constants are much smaller than that) but you're masking the high bit to zero, so it's only a 31-bit hash. Is leaving the high bit on considered an overflow?

[jnm2]

@CyrusNajmabadi hashCode is a Long that can be anywhere from 0 to Integer.MaxValue. Why am I getting this?

But no, it can't actually overflow.

[jnm2]

Btw- I'd rather have Roslyn add a NuGet package than add a suboptimal hash.

[CyrusNajmabadi]

but you're masking the high bit to zero, so it's only a 31-bit hash. Is leaving the high bit on considered an overflow?

That's a good point. I think i was thinking about another algorithm that was using uints. So in order to safely convert from the long to a uint, i needed to not include the sign bit. However, as this is all signed math, i think it would be fine to just mask against 0xffffffff ensuring we only keep the bottom 32bit after adding each entry.

[CyrusNajmabadi]

I'd rather have Roslyn add a NuGet package than add a suboptimal hash.

Users can already do that if they want. This is about what to do when users do not, or can not, add those dependencies. This is also about providing a reasonably 'good enough' hash for users. i.e. something better than the common "x + y + z" approach that people often take. It's not intended to be 'optimal' because there's no good definition of what 'optimal' is when it comes to hashing for all users. Note that the approach we're taking here is the one already emitted by the compiler for anonymous types. It exhibits reasonably good behavior while not adding a ton of complexity to the user's code. As time, as more and more users are able to move forward, such can can slowly disappear and be replaced with HashCode.Combine for most people.

[CyrusNajmabadi]

So i worked at it a bit and came up with the following that i think addresses all concerns:

        Dim hashCode As Long = 2118541809
        hashCode = (hashCode * -1521134295 + a.GetHashCode()).GetHashCode()
        hashCode = (hashCode * -1521134295 + b.GetHashCode()).GetHashCode()
        Return CType(hashCode, Integer)

The piece that's interesting is specifically calling .GetHashCode() on the int64 value produced by (hashCode * -1521134295 + a.GetHashCode()). Calling .GetHashCode on this 64 bit value has two good properties for our needs. First, it ensures that hashCode only ever stores a legal int32 value in it (which makes the final returning cast always safe to perform). Second, it ensures that we don't lose any valuable information in the upper 32bits of the int64 temp value we're working with.

[jnm2]

@CyrusNajmabadi Actually offering to install the package is what I was asking about. Saves me from having to do it.

[CyrusNajmabadi]

If you type HashCode, then if System.HashCode is provided in an MS nuget package, then Roslyn will offer it.

[jnm2]

I want it to generate the nonexistent GetHashCode overload and install the package in the same operation.

[CyrusNajmabadi]

I don't think that's an appropriate choice for most users. Adding dependencies is a very heavyweight operation that users should not be forced into. Users can decide the right time to make those choices, and the IDE will respect it. That's been the approach we've taken with all our features up to now, and it's been a healthy one that people seem to like.

[CyrusNajmabadi]

Note: what nuget package is this api even being included in for us to add a reference to?

[morganbr]

The implementation is in System.Private.CoreLib.dll, so it would come as part of the runtime package. The contract is System.Runtime.dll.

[CyrusNajmabadi]

Ok. If that's the case, then it sounds like a user would get this if/when they move to a more recent Target Framework. That sort of thing is not at all a step i would have the "generate equals+hashcode" do to a user's project.