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

Question

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.

There is no problem at all if hashcodes collide. It's preferable to not get collisions, but it's not necessary (and mathematically it's also not possible). — Jon, Oct 28 '11 at 03:46
http://msdn.microsoft.com/en-us/library/system.object.gethashcode%28v=vs.71%29.aspx -- "Derived classes must override GetHashCode with an implementation that returns a unique hash code." — Matt Fenwick, Oct 28 '11 at 03:50
@MattFenwick Because of the pigeonhole principle, there is no such thing as a unique hash code for most types.* That article is a bit inaccurate. They removed that line in succeeding versions. *- `int.GetHashCode()` is probably unique for each number though. — Ilian, Oct 28 '11 at 04:07
@IlianPinzon -- good, I'm glad that was wrong because it was confusing me. Thanks for clearing that up! — Matt Fenwick, Oct 28 '11 at 04:11

score 15 · Accepted Answer · edited May 06 '14 at 16:24

15

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/

edited May 06 '14 at 16:24

Eric Lippert

647,829
179
1,238
2,067

answered Oct 28 '11 at 04:08

lontivero

5,235
5
25
42

This looks really good, thanks. I tried to multiply each component by 100000, 10000, 1000 and 1 before to get this, but this is more clean and extensible. – A-Type Oct 28 '11 at 04:26
Well, it still doesn't build... I will keep this hashcode and do some unit testing to see if I'm doing something else wrong. – A-Type Oct 28 '11 at 04:28
I should have said "it still gets stuck", not "doesn't build". There are no compiler errors. The game just gets stuck in a loop which uses the hash codes. – A-Type Oct 28 '11 at 05:07
Turns out I was using exceptions when I should have been smarter with the code and used booleans to tell me if something worked or not. The exceptions were slowing the initialization of the program to a crawl. The fact that this slowdown had not previously appeared actually proves that things were wrong before and I hadn't realized. Thanks for your help; my roommate reminded me that a struct is better than fiddling with hashcodes in order to compare by value. But your method would work too, and I did learn something! – A-Type Oct 28 '11 at 05:30
This answer is very inefficient if you need to write scalable code, because first you need to convert each int to a string, and then the hash calculation for string incurs further costs. For hashing multiple int fields efficiently, please check out my answer here: https://stackoverflow.com/a/34006336/1911540 – Special Sauce May 05 '18 at 21:05

score 3 · Answer 2 · answered Oct 28 '11 at 04:20

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.

Jeffrey Hill · Answer 3 · 2019-11-15T03:23:05.530

0

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

edited Nov 15 '19 at 03:23

answered Nov 14 '19 at 09:09

Jeffrey Hill

167
1
9

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

3 Answers3