How does native implementation of ValueType.GetHashCode work?

by

It is a lot more complicated than meets the eye. For starters, give the key2 value a completely different string. Notice how the hash code is still the same:

    var k1 = new TheKey(17, "abc");
    var k2 = new TheKey(17, "def");
    System.Diagnostics.Debug.Assert(k1.GetHashCode() == k2.GetHashCode());

Which is quite valid, the only requirement for a hash code is that the same value produces the same hash code. Different values don’t have to produce different hash codes. That’s not physically possible since a .NET hash code can only represent 4 billion distinct values.

Calculating the hash code for a struct is tricky business. The first thing the CLR does is check if the structure contains any reference type references or has gaps between the fields. A reference requires special treatment because the reference value is random. It is a pointer whose value changes when the garbage collector compacts the heap. Gaps in the structure layout are created because of alignment. A struct with a byte and an int has a 3 byte gap between the two fields.

If neither is the case then all the bits in the structure value are significant. The CLR quickly calculates the hash by xor-ing the bits, 32 at a time. This is a ‘good’ hash, all the fields in the struct participate in the hash code.

If the struct has fields of a reference type or has gaps then another approach is needed. The CLR iterates the fields of the struct and goes looking for one that is usable to generate a hash. A usable one is a field of a value type or an object reference that isn’t null. As soon as it finds one, it takes the hash of that field, xors it with the method table pointer and quits.

In other words, only one field in the structure participates in the hash code calculation. Which is your case, only the id field is used. Which is why the string member value doesn’t matter.

This is an obscure factoid that’s obviously important to be aware of if you ever leave it up to the CLR to generate hash codes for a struct. By far the best thing to do is to just never do this. If you have to, then be sure to order the fields in the struct so that the first field gives you the best hash code. In your case, just swap the id and Name fields.

Another interesting tidbit, the ‘good’ hash calculation code has a bug. It will use the fast algorithm when the structure contains a System.Decimal. Problem is, the bits of a Decimal are not representative for its numeric value. Try this:

struct Test { public decimal value; }

static void Main() {
    var t1 = new Test() { value = 1.0m };
    var t2 = new Test() { value = 1.00m };
    if (t1.GetHashCode() != t2.GetHashCode())
        Console.WriteLine("gack!");
}

More Related Contents:

  1. Why are mutable structs “evil”?
  2. When should I use a struct rather than a class in C#?
  3. Calculate MD5 checksum for a file
  4. How to hash a password
  5. Structs versus classes
  6. Changing the value of an element in a list of structs
  7. Non-unique enum values
  8. Generic constraints, where T : struct and where T : class
  9. Which cryptographic hash function should I choose?
  10. How is GetHashCode() of C# string implemented?
  11. Modify Struct variable in a Dictionary
  12. MD5 hash with salt for keeping password in DB in C#
  13. Are Structs always stack allocated or sometimes heap allocated?
  14. Can structs contain fields of reference types
  15. Is it safe for structs to implement interfaces?
  16. Compute a hash from a stream of unknown length in C#
  17. Non-read only alternative to anonymous types
  18. Can I depend on the values of GetHashCode() to be consistent?
  19. Marshal C++ struct array into C#
  20. Obtain SHA-256 string of a string
  21. C# Structs: Unassigned local variable?
  22. Does using public readonly fields for immutable structs work?
  23. What is the best way to implement this composite GetHashCode()
  24. Why are public fields faster than properties?
  25. Hashing with SHA1 Algorithm in C#
  26. A fast hash function for string in C#
  27. C# – Value Type Equals method – why does the compiler use reflection?
  28. SHA1 hashing in SQLite: how?
  29. Are C# structs thread safe?
  30. Problem with struct and property in c#

Leave a Comment