Shared vocabulary and hash code generation for multipart key

Question

I have an object with a private key, and I'm struggling to find a suitable way to override GetHashCode. An example of what the class looks like:

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;} } 

Please note that in each instance of the class no more than 2 or 3 of the key parts will have a value greater than 0.

Any ideas on how best to create a unique hash code in this situation?

I also played with creating a key that is not unique, but evenly distributes objects between buckets of dictionaries, and then stores the objects with matched hashes in List <> or LinkedList <> or SortedList <>. > Any thoughts on this?

Answer 1

The easiest way is to use XOR. A slightly better method recommended by Josh Bloch in Effective Java. See here .

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

Answer 2

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 suggested that single is a reference type. Pay attention to the unchecked block to prevent overflow exceptions.

Answer 3

The hash code does not have to be unique. Since the hash code is only 32 bits, it is not even possible to get a unique code if the data has more than 32 bits.

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

 public int GetHashCode() { return 1; } 

This does not work well, as the distribution is terrible, but it still works.

You can start with a very simple implementation for the hash code, for example:

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

For something more complex, 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 4

You could do something really simple:

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

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

Answer 5

As keltex said, but with one important addition: if you override GetHasCode, you must 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 6

When switching to the premature optimization route, you can try

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

Interesting aside: I do not have an IDE suitable for testing right now, but if I remember correctly that the hash code int just returns int itself. This means that if true, you can eliminate all of these GetHashCode calls.