Generic Dictionary and generating a hashcode for multi-part key

Question

I have an object that has a multi-part key and I am struggling to find a suitable way override GetHashCode. An example of what the class looks like is.

public class wibble{
   public int keypart1 {get; set;}
   public int keypart2 {get; set;}
   public int keypart3 {get; set;}
   public int keypart4 {get; set;}
   public int keypart5 {get; set;}
   public int keypart6 {get; set;}
   public int keypart7 {get; set;}
   public single value {get; set;}
}

Note in just about every instance of the class no more than 2 or 3 of the keyparts would have a value greater than 0.

Any ideas on how best to generate a unique hashcode in this situation?

I have also been playing around with creating a key that is not unique, but spreads the objects evenly between the dictionaries buckets and then storing objects with matched hashes in a List<> or LinkedList<> or SortedList<>.
Any thoughts on this?

Answer 1

You could do something real simple like this:

public override int GetHashCode()
{
    return (keypart1.ToString() + ":"
      keypart2.ToString() + ":" + ... etc).GetHashCode();
}

There are numerical methods that are probably quicker, but this would do the job without premature optimization.

Answer 2

The simplest method is to use XOR. A slightly better method is the one recommended by Josh Bloch in Effective Java. See here.

Regarding your use of the hash code: it is expected that there will sometimes be collisions and this should not cause problems (having too many collisions will make your code slow, but it should still work). If you can have multiple values for the same key you should consider using something like a Dictionary<Foo, List<Bar>> or a Lookup. If the hashes of the keys happen to collide but the keys are different then you don't need to do anything special. Dictionary handles this situation for you automatically, as long as your implementation of Equals is correct.

Answer 3

As keltex said but with one important addition: if you override GetHasCode you should also override equals! From here: http://msdn.microsoft.com/en-us/library/ms173147(VS.80).aspx

public override bool Equals(System.Object obj)
{
    // If parameter is null return false.
    if (obj == null)
    {
        return false;
    }

    // If parameter cannot be cast to wibblereturn false.
    wibble p = obj as wibble;
    if ((System.Object)p == null)
    {
        return false;
    }

    // Return true if the fields match:
    return (Your comparison);
}

Answer 4

Going the premature optimisation route, you could try

public override int GetHashCode()
{
    return 
       keypart1.GetHashCode() ^
       keypart2.GetHashCode() ^
       keypart3.GetHashCode() ^
       keypart4.GetHashCode() ^
       keypart5.GetHashCode() ^
       keypart6.GetHashCode() ^
       keypart7.GetHashCode();
}

Interesting aside: I don't have an IDE handy to test right now, but if I remember correctly getting the hashcode of an int simply returns the int itself. Which means, if that is true, that you can eliminate all of those GetHashCode calls.

Answer 5

The hash code doesn't have to be unique. As the hash code is just 32 bits it's not even possible to get a unique code if the data is more than 32 bits.

The only requirement is that the hash code is always the same for any specific set of relevant data in the class. That means that even a constant hash code works:

public int GetHashCode() {
   return 1;
}

It doesn't perform well, as the distribution is horrible, but it still works.

You can start with some very simple implementation for the hash code, like:

public int GetHashCode() {
   return
     keypart1 ^ keypart2 ^ keypart3 ^ keypart4 ^
     keypart5 ^ keypart6 ^ keypart7 ^ value.GetHashCode();
}

For something a bit more sophisticated you can multiply by a prime number:

public int GetHashCode() {
   return
     ((((((keypart1 * 13 + keypart2) * 13 + keypart3) * 13 + keypart4) * 13 +
     keypart5) * 13 + keypart6) * 13 + keypart7) * 13 + value.GetHashCode();
}

Answer 6

Resharper gives you the following:

    public override int GetHashCode()
    {
        unchecked
        {
            int result = keypart1;
            result = (result * 397) ^ keypart2;
            result = (result * 397) ^ keypart3;
            result = (result * 397) ^ keypart4;
            result = (result * 397) ^ keypart5;
            result = (result * 397) ^ keypart6;
            result = (result * 397) ^ keypart7;
            result = (result * 397) ^ (value != null ? value.GetHashCode() : 0);
            return result;
        }
    }

I've assumed that single is a reference type. Notice the unchecked block to prevent overflow exceptions.