How do you implement GetHashCode for structure with two string, when both strings are interchangeable

Question

I have a structure in C#:

public struct UserInfo
{
   public string str1
   {
     get;
     set;
   }

   public string str2
   {
     get;
     set;
   }   
}

The only rule is that UserInfo(str1="AA", str2="BB").Equals(UserInfo(str1="BB", str2="AA"))

How to override the GetHashCode function for this structure?

Euripus

possible duplicate of Fast String Hashing Algorithm with low collision rates with 32 bit integer – Ftc

@nawfal, shouldn't it be the other way round? My question was posted on Sept 16/08, but the one you proposed was posted on Sept 22/08. – Euripus

In the latest .Net(core) there is HashCode.Combine method -see #23469171 – Nootka

Does this answer your question? What is the best algorithm for overriding GetHashCode? – Nootka

@Euripus "Possible duplicate" is a way to clean-up - to close similar questions and keep one with the best answers. The date is not essential. See meta.stackexchange.com/questions/147643/… If you agree that it requires clarification please vote on meta.stackexchange.com/questions/281980/… – Nootka

Answer 1

MSDN:

A hash function must have the following properties:

• If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two object do not have to return different values.
• The GetHashCode method for an object must consistently return the same hash code as long as there is no modification to the object state that determines the return value of the object's Equals method. Note that this is true only for the current execution of an application, and that a different hash code can be returned if the application is run again.
• For the best performance, a hash function must generate a random distribution for all input.

Taking it into account correct way is:

return str1.GetHashCode() ^ str2.GetHashCode() 

^ can be substituted with other commutative operation

Eureetloir

Shouldn't that be return str1.GetHashCode() ^ str2.GetHashCode(); – Eartha

Also, doesn't consider null values. – Crocodile

Omer van Kloeten, is should be obvious to any .net developer. quick sample intended to show general idea, not complete solution – Eureetloir

If you expect having str1,str2 and str2,str1 in your hash to be a very frequent occurance , lookup speed might be a bit slower than it should be. Lookup speed can also be increased by caching the hashcode. Obviously these may be premature optimizations. – Walliw

+1 for pointing out the importance of using a commutative operation – Gamal

what we can say for this string s1 = "hello"; string s2 = "hello"; (s1 == s2).Dump(); (s1.GetHashCode() == s2.GetHashCode()).Dump(); – Forsook

Why does it need to be commutative? Then if you had two objects like: o1.str1 == o2.str2 && o1.str2 == o1.str1 they would have the same hash code but may not be considered equal, or am I missing something? – Rectum

Unfortunately, "If two string objects are equal, the GetHashCode method returns identical values. However, there is not a unique hash code value for each unique string value. Different strings can return the same hash code." per msdn.microsoft.com/en-us/library/system.string.gethashcode.aspx, so there's a chance that this would fail spectacularly. – Sciurine

I stand corrected, Hashes can be the same for different objects. I'm guessing that all of the LINQ methods that use getHash, for example, would also use Equals in the case that two objects return the same hash. – Sciurine

Answer 2

See Jon Skeet's answer - binary operations like ^ are not good, they will often generate colliding hash!

Coeternal

but jon says it's bad because it'll do exactly what OP wants. F(a,b) == F(b,a) ... – Precedency

Answer 3

public override int GetHashCode()
{
    unchecked
    {
        return (str1 ?? String.Empty).GetHashCode() +
            (str2 ?? String.Empty).GetHashCode();
    }
}

Using the '+' operator might be better than using '^', because although you explicitly want ('AA', 'BB') and ('BB', 'AA') to explicitly be the same, you may not want ('AA', 'AA') and ('BB', 'BB') to be the same (or all equal pairs for that matter).

The 'as fast as possible' rule is not entirely adhered to in this solution because in the case of nulls this performs a 'GetHashCode()' on the empty string rather than immediately return a known constant, but even without explicitly measuring I am willing to hazard a guess that the difference wouldn't be big enough to worry about unless you expect a lot of nulls.

Hyperpituitarism

Answer 4

1. As a general rule, a simple way to generate a hashcode for a class is to XOR all the data fields that can participate in generating the hash code (being careful to check for null as pointed out by others). This also meets the (artificial?) requirement that the hashcodes for UserInfo("AA", "BB") and UserInfo("BB", "AA") are the same.

2. If you can make assumptions about the use of your class, you can perhaps improve your hash function. For example, if it is common for str1 and str2 to be the same, XOR may not be a good choice. But if str1 and str2 represent, say, first and last name, XOR is probably a good choice.

Although this is clearly not meant to be a real-world example, it may be worth pointing out that: - This is probably a poor example of use of a struct: A struct should normally have value semantics, which doesn't seem to be the case here. - Using properties with setters to generate a hash code is also asking for trouble.

Bouncer

Hmm, why do you think his struct doesn't have value semantics? And could you expand on your last sentence? – Waynant

Answer 5

Going along the lines ReSharper is suggesting:

public int GetHashCode()
{
    unchecked
    {
        int hashCode;

        // String properties
        hashCode = (hashCode * 397) ^ (str1!= null ? str1.GetHashCode() : 0);
        hashCode = (hashCode * 397) ^ (str2!= null ? str1.GetHashCode() : 0);

        // int properties
        hashCode = (hashCode * 397) ^ intProperty;
        return hashCode;
    }
}

397 is a prime of sufficient size to cause the result variable to overflow and mix the bits of the hash somewhat, providing a better distribution of hash codes. Otherwise there's nothing special in 397 that distinguishes it from other primes of the same magnitude.

Euraeurasia

This hash code does not satisfy OP's requirement: the only rule is that UserInfo(str1="AA", str2="BB").Equals(UserInfo(str1="BB", str2="AA")) – Globoid

Answer 6

A simple general way is to do this:

return string.Format("{0}/{1}", str1, str2).GetHashCode();

Unless you have strict performance requirements, this is the easiest I can think of and I frequently use this method when I need a composite key. It handles the null cases just fine and won't cause (m)any hash collisions (in general). If you expect '/' in your strings, just choose another separator that you don't expect.

Cambridgeshire

Very simple indeed. This can be simplified in C# 6.0 to just return $"{str1}/{str2}".GetHashCode();. See String Interpolation – Wrestling

Not safe, what if str1 = "a/b" and str2 = ""? This would have the same hash as str1 = "a" and str2 = "b/". – Imitate

@ErwinMayer use a separator character you know isn't in your strings. Besides, GetHashCode is not required to always return unique values. It is used as an optimization to avoid calling Equals too often (exact comparison is often more expensive). – Mallee

How does this ensure that it results in the same hash code for str1="a", str2="b" and for str1="b" str2="a"? Is there some magic so that "a/b" and "b/a" result in the same hash? – Globoid

@KaspervandenBerg No those two must have different hash since they are aren't the same, right? – Mallee

@DanielLidström they should be the same, since OP required UserInfo(str1: "AA", str2: "BB").Equals(UserInfo(str1: "BB", str2: "AA")) – Globoid

@KaspervandenBerg Then the Equals function needs to be overridden and provide that functionality. That has not so much to do with GetHashCode. – Mallee

@DanielLidström, it does have much to do with GetHashCode, since GetHashCode is required to result in the same hashcode when two objects are Equal. – Globoid

@KaspervandenBerg Nice catch, forgot about that. Guess you'll have to account for that then. – Mallee

Answer 7

public override int GetHashCode()   
{       
    unchecked      
    {           
        return(str1 != null ? str1.GetHashCode() : 0) ^ (str2 != null ? str2.GetHashCode() : 0);       
    }   
}

Mozzarella

Why unchecked? xor can't overflow. – Hirst

Answer 8

Ah yes, as Gary Shutler pointed out:

return str1.GetHashCode() + str2.GetHashCode();

Can overflow. You could try casting to long as Artem suggested, or you could surround the statement in the unchecked keyword:

return unchecked(str1.GetHashCode() + str2.GetHashCode());

Tameratamerlane

Answer 9

Try out this one:

(((long)str1.GetHashCode()) + ((long)str2.GetHashCode())).GetHashCode()

Springfield

Answer 10

Since C# 7, we can take advantage of ValueTuple for that:

return (str1, str2).GetHashCode();

Quinidine

But are you sure (str1,str2).GetHashCode() is the same with (str2,str1).GetHashCode() ? – Euripus

this isn't a requirement, also using other algorithms, sometimes you do some manipulation to one of the fields (such as str1<<2) before XORing, so if the order were a problem, it would be a problem also using the other suggested methods. I think that as long as you are consistent with the order in the internal implementation it shouldn't be a problem – Quinidine

Answer 11

Many possibilities. E.g.

return str1.GetHashCode() ^ str1.GetHashCode()

Hollington

Answer 12

Perhaps something like str1.GetHashCode() + str2.GetHashCode()? or (str1.GetHashCode() + str2.GetHashCode()) / 2? This way it would be the same regardless of whether str1 and str2 are swapped....

Falgout

Answer 13

Sort them, then concatenate them:

return ((str1.CompareTo(str2) < 1) ? str1 + str2 : str2 + str1)
    .GetHashCode();

Camarillo

This will cause your GetHashCode method to do quite a lot of work. Hash codes are intended to be quick. From MSDN: "A hash function is used to quickly generate a number (hash code) that corresponds to the value of an object". Allocating a new string seems like a bad idea inside a hash function. – Magritte

Answer 14

GetHashCode's result is supposed to be:

1. As fast as possible.
2. As unique as possible.

Bearing those in mind, I would go with something like this:

if (str1 == null)
    if (str2 == null)
        return 0;
    else
       return str2.GetHashCode();
else
    if (str2 == null)
        return str1.GetHashCode();
    else
       return ((ulong)str1.GetHashCode() | ((ulong)str2.GetHashCode() << 32)).GetHashCode();

Edit: Forgot the nulls. Code fixed.

Crocodile

The only rule is that UserInfo(str1="AA", str2="BB").Equals(UserInfo(str1="BB", str2="AA")) – Chopstick

Answer 15

Too complicated, and forgets nulls, etc. This is used for things like bucketing, so you can get away with something like

if (null != str1) {
    return str1.GetHashCode();
}
if (null != str2) {
    return str2.GetHashCode();
}
//Not sure what you would put here, some constant value will do
return 0;

This is biased by assuming that str1 is not likely to be common in an unusually large proportion of instances.

Vaudois

This does not satisfy the condition that the order of str1 and str2 does not matter. ("A", "B") and ("B", "A") produce different hashcodes. – Familial

6.5 years later? And what condition are you referring to? This is the discussion of the generation of a hashcode for a struct containing 2 strings, not for what happens when comparing 2 strings. – Vaudois

The structs ("A", "B") and ("B", "A") should be considered equal. Therefore, their hash codes must be equal. But ("A", "B") produces the hash code of "A", and ("B", "A") produces the hash code of "B" - which is not equal. – Familial

Given that this question has been edited within the last 6 months at least, I'm not sure that was actually in this question originally. – Vaudois