How to hash an int[] in c#

Question

I'm trying to think of a way to override GetHashCode() when called from a Vector2[]. This code produces non unique hashes for objects that I know to be equal: I pass the following class the same rectangle, and different hash codes are generated.

public Shape(Rectangle r)
        {
            edges = new Vector2[4];
            edges[0] = new Vector2(0, 0);
            edges[1] = new Vector2(r.Width, 0);
            edges[2] = new Vector2(r.Width, r.Height);
            edges[3] = new Vector2(0, r.Height);
            Console.Write(edges.GetHashCode() + "\n");
            Position = new Vector2(r.X, r.Y);                
        }

A Vector2 array is just bunch of ints. How can I create a unique hash for a list of ints?

This could should work. Can you post a complete example that shows two equal vectors producing different hash codes? — David Schwartz
– David Schwartz, Commented Dec 11, 2012 at 1:47
Arrays don't provide a hash code based on the content of the array.. so this code won't work. You have to roll your own, or if you're on .NET 4 use IStructuralEquatable interface. — Simon Whitehead
– Simon Whitehead, Commented Dec 11, 2012 at 1:49
@SimonWhitehead: Really? Then what does Vector2.GetHashCode return? — David Schwartz
– David Schwartz, Commented Dec 11, 2012 at 1:50
@DavidSchwartz The Hash for a Vector2 instance. But edges.GetHashCode won't produce a hash based on each Vector2 instance in the array. Note that edges is an array of Vector2's.. — Simon Whitehead
– Simon Whitehead, Commented Dec 11, 2012 at 1:53

Kirill Polishchuk · Accepted Answer · 2012-12-11 02:08:05Z

5

You can use something like this:

public static int CombineHashCodes(params int[] hashCodes)
{
    if (hashCodes == null)
    {
        throw new ArgumentNullException("hashCodes");
    }

    if (hashCodes.Length == 0)
    {
        throw new IndexOutOfRangeException();
    }

    if (hashCodes.Length == 1)
    {
        return hashCodes[0];
    }

    var result = hashCodes[0];

    for (var i = 1; i < hashCodes.Length; i++)
    {
        result = CombineHashCodes(result, hashCodes[i]);
    }

    return result;
}

private static int CombineHashCodes(int h1, int h2)
{
    return (h1 << 5) + h1 ^ h2;

    // another implementation
    //unchecked
    //{
    //    var hash = 17;

    //    hash = hash * 23 + h1;
    //    hash = hash * 23 + h2;

    //    return hash;
    //}
}

answered Dec 11, 2012 at 2:08

Kirill Polishchuk

56.4k11 gold badges125 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Max Kessler Over a year ago

So, it loops through an array two ints at a time, carrying a total which is bit shifted by five each iteration, and incremented by itself ^ the next number. Maybe I don't understand how bit shifting works, but won't this produce a massive, massive number? And I should mod out by the size of my hash table at the end? Regardless, I find this helpful.

user166390 Over a year ago

@MaxKessler No. It uses a running "barrel hash" (h1 is mixed with h2) so it never exceeds the size of an int and bits shifted off of the end are dropped. Remember that, generally, hashes are not (and cannot be) unique; they must only be stable and, hopefully, well-distributed.

Max Kessler Over a year ago

Understood! I changed my code so that a collision is not used as a means of identifying whether two objects are equal: I did a little research, and overrode the equals method on my objects. Thank you very much!

Collectives™ on Stack Overflow

How to hash an int[] in c#

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related