C# Immutability and Equality

Question

I'm trying to create and use only immutable classes where all fields are readonly immutable types, though there may be additional fields which are mutable and not considered to be part of the object's state (mainly a cached hashcode).

When implementing IEquatable I do the same as I would for non immutable objects

Ie,

public bool Equals(MyImmutableType o) => 
  object.Equals(this.x, o.x) && object.Equals(this.y, o.y);

Now being immutable this seems inefficient, the object will never change, if I could calculate and store some unique fingerprint of it I could simply compare fingerprints instead of whole fields (which may call their own Equals etc).

I am wondering what can be a good solution for this ? will BinaryFormatter + MD5 be worth exploring ?

Answer 1

Since you've already overridden Equals, you are required to also overload GetHashCode. Remember, the fundamental rule of GetHashCode is equal objects have equal hashes.

Therefore, you have overridden GetHashCode.

Since equal objects are required to have equal hash codes, you can implement Equals as:

public static bool Equals(M a, M b)
{
  if (object.ReferenceEquals(a, b)) return true;
  // If both of them are null, we're done, but maybe one is.
  if (object.ReferenceEquals(null, a)) return false;
  if (object.ReferenceEquals(null, b)) return false;
  // Both are not null.
  if (a.GetHashCode() != b.GetHashCode()) return false;
  if (!object.Equals(a.x, b.x)) return false;
  if (!object.Equals(a.y, b.y)) return false;
  return true;
}

And now you can implement as many instance versions of Equals as you like by calling the static helper. Also overload == and != while you're at it.

That implementation takes as many early outs as possible. Of course, the worst-performing case is the case where we have value equality but not reference equality, but that's also the rarest case! In practice, most objects are unequal to each other, and most objects that are equal to each other are reference equal. In those 99% cases we get the right answer in four or fewer highly efficient comparisons.

If you are in a scenario where it is extremely common for there to be objects that are value equal but not reference equal, then solve the problem in the factory; memoize the factory!