Using a class versus struct as a dictionary key

Question

Suppose I had the following class and structure definition, and used them each as a key in a dictionary object:

public class MyClass { }
public struct MyStruct { }

public Dictionary<MyClass, string> ClassDictionary;
public Dictionary<MyStruct, string> StructDictionary;

ClassDictionary = new Dictionary<MyClass, string>();
StructDictionary = new Dictionary<MyStruct, string>();

Why is it that this works:

MyClass classA = new MyClass();
MyClass classB = new MyClass();
this.ClassDictionary.Add(classA, "Test");
this.ClassDictionary.Add(classB, "Test");

But this crashes on runtime:

MyStruct structA = new MyStruct();
MyStruct structB = new MyStruct();
this.StructDictionary.Add(structA, "Test");
this.StructDictionary.Add(structB, "Test");

It says the key already exists, as expected, but only for the struct. The class treats it as two separate entries. I think it has something to do with the data being held as a reference versus value, but I would like a more detailed explanation as to why.

Solution 1

1. new object() == new object() is false, because reference types have reference equality and the two instances are not the same reference

2. new int() == new int() is true, because value types have value equality and the value of two default integers are the same value. Note, that if you have reference types or default values that are incremental in your struct, the defaults may not compare equal for structs either.

You can override the Equals and GetHashCode methods and the equality operators of both structs and classes if you don't like the default equality behavior.

Also, If you want a safe way to set the dictionary value, regardless, you can do dictionary[key] = value; which will add new values or update old ones with the same key.

Update

@280Z28 posted a comment that pointed out how this answer could be misleading, which I recognize and want to address. It's important to know that:

1. By default, reference types' Equals(object obj) method and == operator call object.ReferenceEquals(this, obj) under the hood.

2. The operators and instance methods need to be overridden eventually to propagate the behavior. (e.g. changing the Equals implementation will not affect the == implementation, unless a nested call is added explicitly).

3. All the default .NET generic collections use an IEqualityComparer<T> implementation to determine equality (not an instance method). The IEqualityComparer<T> may (and often does) call the instance method in its implementation, but this is not something you can count on. There are two possible sources for the IEqualityComparer<T> implementation that is used:

   1. You can provide it explicitly in the constructor.

   2. It will be retrieved automatically from EqualityComparer<T>.Default (by default). If you want to configure the default IEqualityComparer<T> globally that is accessed by EqualityComparer<T>.Default, you can use Undefault (on GitHub).

Solution 2

Dictionary<TKey, TValue> uses an IEqualityComparer<TKey> for comparing the keys. If you do not explicitly specify the comparer when you construct the dictionary, it will use EqualityComparer<TKey>.Default.

Since neither MyClass nor MyStruct implement IEquatable<T>, the default equality comparer will call Object.Equals and Object.GetHashCode for comparing instances. MyClass is derived from Object, so the implementation will use reference equality for comparison. MyStruct on the other hand is derived from System.ValueType (the base class of all structs), so it will use ValueType.Equals for comparing the instances. The documentation for this method states the following:

The ValueType.Equals(Object) method overrides Object.Equals(Object) and provides the default implementation of value equality for all value types in the .NET Framework.

If none of the fields of the current instance and obj are reference types, the Equals method performs a byte-by-byte comparison of the two objects in memory. Otherwise, it uses reflection to compare the corresponding fields of obj and this instance.

The exception occurs because IDictionary<TKey, TValue>.Add throws an ArgumentException if "An element with the same key already exists in the [dictionary]." When using structs, the byte-by-byte comparison done by ValueType.Equals results in both calls attempting to add the same key.

Solution 3

There are generally three good types of dictionary keys: the identities of mutable class objects, the values of immutable class objects, or the values of structures. Note that structures with exposed public fields are just as suitable for use as dictionary keys as those which do not, since the only way the copy of the structure stored within the dictionary will change will be if the structure is read out, modified, and written back. By contrast, classes with exposed mutable properties generally make lousy dictionary keys except in the case where one wishes to key upon the identity of the object, rather than its contents.

In order for a type to be used as a dictionary key, either its Equals and GetHashCode methods must have the desired semantics, or else the constructor of the Dictionary must be given an IEqualityComparer<T> which implements the desired semantics. The default Equals and GetHashCode method for classes will key on object identity (useful if one wishes to key upon the identities of mutable objects; not so useful otherwise). The default Equals and GetHashCode methods for value types will generally key upon the Equals and GetHashCode methods of their members, but with a couple of wrinkles:

• Code using the default methods on structures will often run much slower (sometimes an order of magnitude) than code which uses custom-written methods.

• Structures which contain only primitive types will perform floating-point comparisons differently from those which include other types as well. For example, the values posZero=(1.0/(1.0/0.0)) and negZero=(-1.0/(1.0/0.0)) will both compare equal, but if stored in a struct that contains only primitives they will compare unequal. Note that even thought he values compare equal, they are semantically not the same, since computing 1.0/posZero will yield positive infinity, and 1.0/negZero will yield negative infinity.

If performance is nowhere near critical, one may define a simple struct [simply declare the appropriate public fields] and throw it into a Dictionary and have it behave as a value-based key. It won't be terribly efficient, but it will work. Dictionaries will generally handle immutable class objects somewhat more efficiently, but defining and using immutable class objects can sometimes be more work than defining and using "plain old data structures".

Solution 4

Beause a struct is not refered like a class.

A struct creates a copy of itself instead og parsing a reference like a class do.

Therefor if you try this:

var a =  new MyStruct(){Prop = "Test"};
var b =  new MyStruct(){Prop = "Test"};

Console.WriteLine(a.Equals(b));

//will print true

If you do the same with a class:

var a =  new MyClass(){Prop = "Test"};
var b =  new MyClass(){Prop = "Test"};

Console.WriteLine(a.Equals(b));

// will print false! (assuming you have not implemented some compare function) beacuse the reference is not the same

Solution 5

The reference type key (class) points to a distinct reference; the value type key (struct) points to identical values. I would think that's why you get the exception.

View more solutions

Comments

[Sam Harwell]

Your answer is misleading because Dictionary<TKey, TValue> uses EqualityComparer<T>.Default for comparisons, and that comparer does not use operator == for comparisons. Operator == is completely irrelevant to this question.

[Jim D'Angelo]

+1 for EqualityComparer<TKey>.Default. This is the right answer.

[smartcaveman]

@280Z28, that's a good point - I updated my answer to address this.

[Sam Harwell]

The question asked why Dictionary<TKey, TValue> treats classes and structs differently when used as keys. Your reply discusses the == operator and mentions overriding Equals and GetHashCode to change the equality behavior. The first part of that is irrelevant, the second part is only correct some of the time, and neither gives any explanation for the situation described in the original question. The update seems to address my comment as though I said you were incorrect, when in reality I was simply saying you were off-topic.

[smartcaveman]

@280Z28 The OP asked for a detailed explanation of the behavior he was getting. I interpreted the question as an indication that the OP had a misunderstanding about .NET equality in general and that the issue with dictionary keys is just a particular manifestation of that misunderstanding. So, I tried to answer the question in the way that I believe is most helpful. I guess you could consider the broader generalization as partially "off-topic", but that's my rationale for my answer.