11

I come from a python world where only hashable objects may be used as keys to a dictionary. Is there a similar restriction in C#? Can you use custom types as dictionary keys?

static_rtti
  • 53,760
  • 47
  • 136
  • 192
  • 7
    Theoretically you can use any type as a key. In practice it should be an immutable type, otherwise you'll be in a world of pain when keys start mutating... – Patryk Ćwiek Sep 06 '13 at 08:22
  • 1
    @PatrykĆwiek Note [this comment](https://stackoverflow.com/questions/3917298/are-the-keys-in-a-dictionarytkey-tvalue-immutable#comment16656400_3917393) -- "Only the GetHashCode value and the equivalence class defined by Equals need to be immutable. A suitable equivalence class is defined for all class types--reference equality--that is generally the only equivalence class which should be used for mutable objects. There is nothing whatsoever wrong with having a mutable class type as a dictionary key if the purpose of the dictionary is to associate instances of that type with something else. " – ChrisW Jun 16 '21 at 06:50

3 Answers3

18

The requirement for a dictionary key is that it is comparable and hashable. That's turtles all the way down in .NET, every type (other than pointer types) derives from System.Object and it is always comparable thanks to its Equals() method. And hashable thanks to its GetHashCode() method. So any .NET type automatically can be used as a key.

If you want to use your own type as the key then you only need to do something special if you want to re-define object identity. In other words, if you need the ability for two distinct objects to be equal. You'd then override the Equals() method, typically comparing fields of the object. And then you must also override GetHashCode(), equal objects must generate the same hash code.

If the type cannot be changed or you want to customize the behavior especially for the Dictionary then you can pass a custom IEqualityComparer<> to the constructor. Keep in mind that the quality of the hash code you generate with your own GetHashCode() determines the dictionary efficiency.

Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
3

Yes, the important thing with keys is that they implement (or have a good default implementation of) GetHashCode and Equals. The Dictionary<T, K> implementation can take advantage of generic IEqualityComparer<T>.

All custom types will come with a default implementation of GetHashCode and Equals because these are members of object, however, that default might not always be relevant to your type.

The dictionary first attempts to get the hash code to determine the bucket the value will land in. If there is a hash collision, it falls back onto equality (I think).

Do note that the type of key you use (class, struct, primitive type, etc) can yield different performance characteristics. In our code base we found that the default implementation of GetHashCode in struct wasn't as fast as overriding it ourselves. We also found that nested dictionaries perform better in terms of access time than a single dictionary with a compound key.

Adam Houldsworth
  • 63,413
  • 11
  • 150
  • 187
  • I suppose if you use the obvious definition of equality (ie. objects are equal if all fields are equal), the default Equals and GetHashCode are good enough? (except maybe for performance reasons, but I'm not there yet) – static_rtti Sep 06 '13 at 08:26
  • 3
    @static_rtti The default implementation of equality for a `class` is not field-equal, it's reference equal I think. For a `struct` I believe it's value equal over the first x-byte block or something arcane like that. Personally I'm a fan of making sure the implementation is well defined for custom types as keys, but at the same time we have few instances where custom types are keys. – Adam Houldsworth Sep 06 '13 at 08:27
  • 1
    @static_rtti Not necessarily, all reference types use reference equality by default. – Patryk Ćwiek Sep 06 '13 at 08:28
  • 2
    You're right about performance, Value types GetHashCode default implementation uses reflection to get the values of the type's fields (http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx). It's very slow. On the other side that gives you a pretty good default behavior. – Charles Barthélemy Sep 06 '13 at 08:31
  • @CharlesBarthélemy Yes the default is actually as you would expect, by its value, which is fortunate. I never realised it used reflection. – Adam Houldsworth Sep 06 '13 at 08:32
2

Yes you can, just implement interface IEqualityComparer, override GetHashCode and Equals.

Suhan
  • 1,434
  • 2
  • 13
  • 28
  • So you have to do it all by yourself? Is there something to help you implement the hashing function? – static_rtti Sep 06 '13 at 08:22
  • 2
    `GetHasCode` is a funny name for a method. Default implementation is `return false;` :) – Tim Schmelter Sep 06 '13 at 08:25
  • @static_rtti: `System.Object` has a default implementation of GetHashCode() that's probably simply based on the object's address (or maybe some kind of ID in case of garbage collection). Some other objects, like `System.String`, override it to return something related to their contents. And for all other cases, you can use an implementation of `IEqualityComparer` to customize the hashing. Look at the `StringComparer` class for example: Each of its members has a different implementation of `IEqualityComparer` to match the string comparison, so you can have, say, case-insensitive hashing. – Medinoc Sep 06 '13 at 08:33
  • @Suhan You don't actually need to implement that interface, but it is arguably a Good Thing to do. – Adam Houldsworth Sep 06 '13 at 08:37
  • When I've had to implement `IEqualtyComparer`, I usually just have to delegate the `GetHashCode` call to something else, like an identifier or string. Rarely have I had to generate a hash-code myself. Obviously this depends on the object being stored. – Moo-Juice Sep 06 '13 at 08:38
  • @Adam Houldsworth You also don't need to implement IEnumerable for using iterators, but it is more obvious – Suhan Sep 06 '13 at 08:38
  • @Suhan I know, but your answer as it stands implies that it is *required*. – Adam Houldsworth Sep 06 '13 at 08:40