Overriding GetHashCode in a mutable struct - What NOT to do?

Question

I am using the XNA Framework to make a learning project. It has a Point struct which exposes an X and Y value; for the purpose of optimization, it breaks the rules for proper struct design, since its a mutable struct.

As Marc Gravell, John Skeet, and Eric Lippert point out in their respective posts about GetHashCode() (which Point overrides), this is a rather bad thing, since if an object's values change while its contained in a hashmap (ie, LINQ queries), it can become "lost".

However, I am making my own Point3D struct, following the design of Point as a guideline. Thus, it too is a mutable struct which overrides GetHashCode(). The only difference is that mine exposes and int for X, Y, and Z values, but is fundamentally the same. The signatures are below:

public struct Point3D : IEquatable<Point3D>
{
    public int X;
    public int Y;
    public int Z;

    public static bool operator !=(Point3D a, Point3D b) { }
    public static bool operator ==(Point3D a, Point3D b) { }

    public Point3D Zero { get; }

    public override int GetHashCode() { }
    public override bool Equals(object obj) { }
    public bool Equals(Point3D other) { }
    public override string ToString() { }
}

I have tried to break my struct in the way they describe, namely by storing it in a List<Point3D>, as well as changing the value via a method using ref, but I did not encounter they behavior they warn about (maybe a pointer might allow me to break it?).

Am I being too cautious in my approach, or should I be okay to use it as is?

Answer 1

Let's break it down.

Is a mutable struct with public fields a good idea?

No. You already know that it is not, but you're choosing to play with fire while walking on thin ice anyways. I would advise against using Point as a model. Value types should logically be values, and values don't change, variables change.

That said, there can be good performance reasons for doing what you're doing; I would only do so if I had clear empirical evidence that there was no other way to meet my performance goals.

If I put a mutable struct into a dictionary and then mutate it, can the struct be "lost" in the hash code?

The question is not answerable because it presumes a falsehood. You can't put a mutable struct into a dictionary and then mutate it. Asking "what happens when I do something impossible?" doesn't afford answers upon which you can make engineering decisions.

What happens when I try to mutate a mutable struct that I've put into a dictionary?

Value types are copied by value; that's why they're called "value types". When you fetch the value from the dictionary, you make a copy. If you then mutate it, you mutate the copy. If you try to mutate it directly by changing a field, the compiler will tell you that you are mutating a copy and that the mutation will be lost.

So what's the real danger of putting a mutable struct into a dictionary?

The danger of putting a mutable value type in a dictionary is that mutations are lost, not that the object gets lost in the dictionary. That is, when you say:

struct Counter 
{ 
  public int x; 
  public void Increment() { x = x + 1; } 
  ...
}

...

var c = new Counter();
var d = new Dictionary<string, Counter>();
d["hello"] = c;
c.Increment();
Console.WriteLine(c.x);
Console.WriteLine(d["hello"].x);
d["hello"].Increment();
Console.WriteLine(c.x);
Console.WriteLine(d["hello"].x);

then the increment to c is preserved but not copied to the dictionary, and the increment of the dictionary's copy is lost because it is made to a copy, not to the dictionary.

This is very confusing for people, which is why you should avoid it.

Answer 2

I see no particular problem in writing a struct like this, once you fully understand the trade-offs. The problem is (presumably) that you want to be to able to store it in a Dict (or similar collection) and you need a HashCode.

One thing you didn't mention is: do your points have identity? That is, if you have two points with the same value, are they the same point? [As two Integers both with the value 7 are the same integer. There is only one Integer with the value 7.]

Mutability implies identity. If a Point3D has identity then its HashCode is derived from its identity. You could use a this pointer or something like a GUID.

If the Point3D has no identity then its HashCode is best derived from its value. If you change the value (say by reusing values from a pool), you better make sure it's not in a Dict-like collection at the time or it will be lost.

---

Obviously if you don't use hash-based collections then the point is moot.

---

If you do, consider this code.

public struct ValuePoint {
  public int x;
  public int y;
  public override int GetHashCode() { return (x * 1000 + y) % 97; }
  public ValuePoint(int _x, int _y) { x = _x; y = _y; }
}
public struct IdentityPoint {
  static int nextkey = 0;
  int key;
  public int x;
  public int y;
  public override int GetHashCode() { return key; }
  public IdentityPoint(int _x, int _y) { key = ++nextkey; x = _x; y = _y; }
}
class Program {
  Dictionary<ValuePoint, int> dictv = new Dictionary<ValuePoint,int>();
  Dictionary<IdentityPoint, int> dicti = new Dictionary<IdentityPoint,int>();
  HashSet<ValuePoint> setv = new HashSet<ValuePoint>();
  HashSet<IdentityPoint> seti = new HashSet<IdentityPoint>();

  void exec() {
    ValuePoint vp = new ValuePoint(3, 4);
    dictv[vp] = 777;
    vp.x++;
    dictv[vp] = 888;
    IdentityPoint ip = new IdentityPoint(3, 4);
    dicti[ip] = 777;
    ip.x++;
    dicti[ip] = 888;
  }

ValuePoint uses its value as its hashkey. If you change the value (x++) then the original value is 'lost', and the assigned value '888' adds a new key instead of updating the existing one.

IdentityPoint uses a unique key. If you change the value (x++) then the original entry is still found and overwritten with the assigned value '888'.

This is a contrived example, but illustrates the point about value versus identity. [The code is bad but good enough for the purpose.]

@EricLippert is a highly regarded writer whom I remember from the early days of COM and the design of .NET and his advice is sound. I think he misses the point by using a dictionary in which the key is a string. The issue of GetHashCode() only arises when the mutable object itself is the key.