3
\$\begingroup\$

Have I over-ridden GetHashCode properly in the below code?

public class ODPair
{
    #region Constructors and Destructors

    public ODPair(string origin, string destination)
    {
        if (string.IsNullOrEmpty(origin))
        {
            throw new ArgumentNullException(origin, "Origin of an ODPair should be non-null");
        }

        if (string.IsNullOrEmpty(destination))
        {
            throw new ArgumentNullException(destination, "Destination of an ODPair should be non-null");
        }

        this.Origin = origin;
        this.Destination = destination;
    }

    #endregion

    #region Public Properties

    public string Destination { get; private set; }

    public string Origin { get; private set; }

    #endregion

    #region Public Methods and Operators

    public override bool Equals(object obj)
    {
        if (obj == null)
        {
            return false;
        }

        var pair = obj as ODPair;
        if (pair == null)
        {
            return false;
        }

        return this.Origin == pair.Origin && this.Destination == pair.Destination;
    }

    public bool Equals(ODPair pair)
    {
        if (pair == null)
        {
            return false;
        }

        return this.Origin == pair.Origin && this.Destination == pair.Destination;
    }

    public override int GetHashCode()
    {
        return this.Origin.GetHashCode() ^ this.Destination.GetHashCode();
    }

    #endregion
}
\$\endgroup\$
  • \$\begingroup\$ Are Origin and Destination ever/frequently the same? \$\endgroup\$ – RobH Jul 3 '15 at 9:51
  • \$\begingroup\$ No, they are never the same. WIll update the ctor check. \$\endgroup\$ – Narayana Jul 3 '15 at 9:56
  • \$\begingroup\$ But you may often have one pair (X, Y) and another pair (Y, X). Trivial change is to shift the second hash code by one bit position. \$\endgroup\$ – gnasher729 Jul 3 '15 at 11:12
7
\$\begingroup\$

Equals

You have a bit of repetition between your Equals methods. Since no instance is equal to null, you can replace your entire overridden Object.Equals method with:

return Equals(obj as ODPair);

If the obj is not an ODPair, this will just pass in a null which will then return false.


At a pinch, XOR is a passable way of combining hash-codes. But it has collision issues:

  • All instances where the origin and destination are the same will have the hash code of 0 (you mentioned this will never be the case for this class, but it's worth keeping in mind in general)
  • Two instances where the origin and destination are swapped will have the same hash code.
  • As Simon mentions in his answer, if the hashcodes being XORed occupy a small subset of the integers, there will be frequent collisions. This too is not likely to be much of a problem for you because the codes getting combined are from strings, so are likely to span the integers pretty well.

So of those it's likely to be the second, if any, which is of concern in this particular case.

My preference is to avoid the complexity of trying to implement my own hashing algorithm and let .NET do it for me:

return Tuple.Create(Origin, Destination).GetHashCode();

or:

return new {Origin, Destination}.GetHashCode();

Only if this presents a noticeable performance issue should you worry about trying to implement your own- premature optimization is still premature optimization even inside a GetHashCode method!

\$\endgroup\$
  • 1
    \$\begingroup\$ Neat trick using a Tuple to create the hash code. Tucking that in my pocket for later. ++ \$\endgroup\$ – RubberDuck Jul 3 '15 at 12:24
  • \$\begingroup\$ @RubberDuck My recollection, having tried this a while ago, is that the anonymous object version is marginally faster. Worth testing it yourself though. \$\endgroup\$ – Ben Aaronson Jul 3 '15 at 12:29
  • \$\begingroup\$ @BenAaronson - The anonymous object version will have a compiler generated GetHashCode method similar to the approach using primes given in the other answers. Tuple does a fair amount of additional stuff. \$\endgroup\$ – RobH Jul 3 '15 at 14:23
4
\$\begingroup\$

There is a better way to get the hash code. Currently, you will get many duplicates because of the XOR operator.

public override int GetHashCode()
{
    return this.Origin.GetHashCode() ^ this.Destination.GetHashCode();
}

Consider the following:

4 ^ 2 == 6 ^ 0 == 7 ^ 1 == ...

This means that the hashcode is not as effective as it can be. Effective Java, item 9 (which I believe applies to C# as well) recommends to multiply each part of the hashcode with a prime number, and add together, such as:

int result = 17;
result = 43 * result + this.Origin.GetHashCode();
result = 43 * result + this.Destination.GetHashCode();
return result;

This will lead to significantly less duplicate hashcodes.

\$\endgroup\$
  • 1
    \$\begingroup\$ So, if I add an ODPair instance as a dictionary key, that is one place where GetHashCode would get called right? Because I'm doing that a lot. \$\endgroup\$ – Narayana Jul 3 '15 at 10:00
  • 2
    \$\begingroup\$ @Narayana Yes, that's right. Frequent collisions will mean the dictionary has to search multiple items and call Equals to check. It's a perf issue not a correctness issue as long as Equals behaves. \$\endgroup\$ – RobH Jul 3 '15 at 10:12
4
\$\begingroup\$

Basically it looks ok, but can surely be improved.

By adding some larger primes for calculating the hash code you can reduce the possible collisions.

See: what-is-the-best-algorithm-for-an-overridden-system-object-gethashcode


  • Regions

    Regions are in my opinion an anti pattern whcih should not be used.

    Please read are-regions-an-antipattern-or-code-smell

    Is there a good use for regions?

    No. There was a legacy use: generated code. Still, code generation tools just have to use partial classes instead. If C# has regions support, it's mostly because this legacy use, and because now that too many people used regions in their code, it would be impossible to remove them without breaking existent codebases.

    Think about it as about goto. The fact that the language or the IDE supports a feature doesn't mean that it should be used daily. StyleCop SA1124 rule is clear: you should not use regions. Never.

  • Validation

    The messages of the ArgumentNullExceptions in the constructor should be changed to reflect the true reason. You are checking IsNullOrEmpty() but stating "...should be non-null" but string.empty != null so either validate for null and throw an ArgumentException in addition checking if the string is empty and throw an ArgumentException or change the message.


I like the private setters of the properties and your code looks readable with one exception. Unfortunatetly this one exception is the name of the class. ODPair is a very poor name using abreviation of origin and destination so a better name would be in order. Otherwise you will either add an explaining comment in the calling code (which is as bad) or Sam the maintainer will come and get you which isn't better either.

\$\endgroup\$
  • 2
    \$\begingroup\$ The regions are automatically created by Resharper when I run a CleanCode command. I knew regions inside methods were bad, but that link was very good. I guess its time to update my Resharper rules. Agree with the input checks, it was not done correctly. As for the name, the term "ODPair" is taken as is from the domain (airlines industry), and comes all over the place in the spec. Thanks! :) \$\endgroup\$ – Narayana Jul 3 '15 at 10:51
2
\$\begingroup\$

XOR may be bad since all equal hash codes will end in 0. An alternative is something like this:

   public override int GetHashCode()
    {
        int result = 17;
        result = 31 * result +  Origin.GetHashCode(); 
        result = 31 * result +  Destination.GetHashCode(); 
        return result;
    }

source Effective Java: Equals and HashCode by Joshua Bloch

\$\endgroup\$
  • 1
    \$\begingroup\$ But String hash codes are not supposed to be equal. \$\endgroup\$ – gnasher729 Jul 3 '15 at 11:14
  • \$\begingroup\$ There are less possible integers than possible strings so it can happen. And of course when the 2 strings are equal. But for this case the most probable collision would be the one mention by @Ben Aaronson great answer. \$\endgroup\$ – MAG Jul 3 '15 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.