CODEWITHSUNDEEP
c#hash
A-Type
A-Type

Reputation: 1148

How can I make a hashcode for a custom data structure?

I've made a custom "Coordinate" data structure which defines the position of an object according to a certain system.

A coordinate is defined as follows:

public class Coordinate
{
    public int X;
    public int Y;
    private int face;
    public int Face
    {
        get { return face; }
        set
        {
            if (value >= 6 | value < 0)
                throw new Exception("Invalid face number");
            else
                face = value;
        }
    }
    private int shell;
    public int Shell
    {
        get { return shell; }
        set
        {
            if (value < 0)
                throw new Exception("No negative shell value allowed");
            else
                shell = value;
        }
    }

    public Coordinate(int face, int x, int y, int shell)
    {
        this.X = x;
        this.Y = y;
        this.face = face;
        this.shell = shell;
    }

    public static Coordinate operator +(Coordinate a, Coordinate b)
    {
        return new Coordinate(a.Face + b.Face, a.X + b.X, a.Y + b.Y, a.Shell + b.Shell);
    }

    public override bool Equals(object obj)
    {
        Coordinate other = (obj as Coordinate);
        if (other == null)
            return false;
        else
            return (Face == other.Face && Shell == other.Shell && X == other.X && Y == other.Y);
    }
}

Or, to summarize, it contains an int Face (0 to 5), an int X, int Y, and int Shell. X, Y, and Shell are all bound below at 0 (inclusive).

I have no experience at all in hash codes. I need to compare them to see if they are equal. I tried this:

private const int MULTIPLIER = 89;

[...]

int hashCode = 1;
hashCode = MULTIPLIER * hashCode + obj.X.GetHashCode();
hashCode = MULTIPLIER * hashCode + obj.Y.GetHashCode();
hashCode = MULTIPLIER * hashCode + obj.Face.GetHashCode();
hashCode = MULTIPLIER * hashCode + obj.Shell.GetHashCode();
return hashCode;

Going off something I found while Googling. But when I try to compile the code with this method, I'm pretty sure it runs into collisions, as it never finishes building. Probably getting into all sorts of messy loops thinking a bunch of the coordinates are the same or somesuch.

I'm sorry this question is rather elementary, but for some reason I'm stumped. I'm just looking for advice on how to write this hash code so that it doesn't collide.

Upvotes: 7

Views: 12247

Answers (3)

Jeffrey Hill
Jeffrey Hill

Reputation: 305

If you use dotnetcore 2.1+, you can use HashCode struct's Combine method, it's very easily to use and efficiency.

Upvotes: 2

lontivero
lontivero

Reputation: 5275

If well this is not the best way, it can be a good enough approach:

public override int GetHashCode()
{
   return string.Format("{0}-{1}-{2}-{3}", X, Y, Face, Shell).GetHashCode();
}

Update: Take a look at this article: http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/

Upvotes: 15

Matt Fenwick
Matt Fenwick

Reputation: 49095

Basically, when writing hashcode functions, you need to make sure that:

  • you don't have stale hashcodes (i.e. the state of the object shouldn't change after a hashcode has been generated, such that the hashcode would change if regenerated)
  • objects with equal values return the same hashcodes
  • the same object always returns the same hashcode (if it's not modified) -- deterministic

Also, it's great, but not necessary, if:

  • your hashcodes are uniformly dispersed over the possible values (source: Wikipedia)

You don't need to ensure that different objects return different hashcodes. It's only frowned upon because it can decrease performance of things like Hashtables (if you have lots of collisions).

However, if you still want your hashcode function to return unique values, then you want to know about perfect hashing.

Upvotes: 3

Related Questions