How to reduce complexity of GetHashCode

Question

I want to decrease my code execution time. Looking at some testing results, I found out that GetHashCode() took 21,62% of my execution time.

I also got a warning:

Warning 1 DA0010: .*.GetHashCode() = 7,63; GetHashCode functions should be cheap and not allocate any memory. Reduce complexity of hash code function if possible.

Code Snippets:

My GetHashCode() in Field Class:

    public override int GetHashCode()
    {
        int hash = 7;
        hash = (hash * 13) + this.Coordinate.GetHashCode();
        return hash;
    }

My GetHashCode() in Coordinate Class:

    public override int GetHashCode()
    {
        int hash = 17;

        hash = (hash * 23) + this.Row.GetHashCode();
        hash = (hash * 23) + this.Column.GetHashCode();

        return hash;
    }

Edit: Row and Column are just byte variables. I just call their property which returns a byte in the get accessor

My GetHashCode() in Sudoku Class:

    public override int GetHashCode()
    {
        int hash = 7;

        hash = (hash * 5) + this.Grid.GetHashCode();

        return hash;
    }

Edit: Grid is just a multidimensional array of type: Field[,], I just call it's Property here which returns a Field[,] grid through it's get accessor.

Questions: How can I greatly decrease the complexity of my GetHashCode() and increase it's performance? Why is the performance of GetHashCode() method so low?

Answer 1

I suspect you'll find that GetHashCode isn't your problem. If you're spending > 20% of your time in GetHashCode, you must be doing a whole lot of dictionary lookups. Or you're using the hash code for something you probably shouldn't be using it for.

GetHashCode might be the manifestation of the performance problem, but it's almost certainly not the cause.

Answer 2

Your calculation is just adding a conts to your hashcode. Only the combination of your hashcodes needs to have a better hashcode then just adding the two values:

//Field 
public override int GetHashCode()
{
    return this.Coordinate.GetHashCode();
}

//Coordinate 
public override int GetHashCode()
{
    return  this.Column.GetHashCode() * 17 + this.Row.GetHashCode();
}    

//Sudoku, I doubt if this is ever called...
public override int GetHashCode()
{
    return this.Grid.GetHashCode();
}

For performance it realy depends on how often you call GetHashCode (if you do any calculation). Or if you store them in some kind of dictionay, the problem can be multiple values with the same hash, which will decrese your access time to the objects in the dictionary/hashtable. So your hashfunction has to be a good distrubution for the set you are storing.

Answer 3

If your classes don't have too many mutators, you can cache the hash code and just return the cached value from GetHashCode(). (Even if you have a lot of mutators you can do this, but it is likely to be much less effective if objects are frequently mutated.)

You should lazily evaluate it. You will need to know when it is dirty and needs to be recalculated. You can do this easily by adding a bool isHashCodeDirty field, which is initialised to true when the class is constructed and also by every mutator method.

Then in your implementation of GetHashCode() if isHashCodeDirty is true, set it to false and recalculate and return the hash code. If it's false, just return the cached value.

You have to be careful with multithreading here, of course. I think that adding a lock to GetHashCode() would impact performance quite a lot though!

The ideal of course is to have immutable classes; then you just calculate the hash code once in the constructor and it'll never change thereafter.

Answer 4

Looks like the problem is not in integer addition, but in accessing properties like this.Coordinate, this.Grid, e.t.c.

Take a look at their get accessors, they may be doing some extra work.