27

I'm thinking this could be a convenient dictionary:

var myDict = new Dictionary<(int, int), bool>();

What would the hashes look like?
What would the equivalent key type (struct) look like?

Steinbitglis
  • 2,482
  • 2
  • 27
  • 40
  • The easier way is to use string join. int[] input = { 1, 2, 3 }; string key = string.Join("^",input.Select(x => x.ToString())); – jdweng Dec 18 '18 at 10:40
  • 3
    @jdweng that would be a terrible idea if you care about allocations – Marc Gravell Dec 18 '18 at 10:42
  • @MarcGravell : What do you mean? – jdweng Dec 18 '18 at 10:44
  • 1
    @jdweng I mean: you're now allocating a string every time you want to store or retrieve a value - that's a *huge* problem in many systems. Compared to using the value-tuple as a key, which is essentially free in terms of allocations. – Marc Gravell Dec 18 '18 at 10:44
  • 2
    @jdweng: there is no reason to do this: you are allocating lots of data unnecessarily (string concatenation), you are spending time creating string representations of individual objects using the current culture, then you're spending much more time evaluating their equality (valuetype.equals is trivial), and finally joining string representations using a separator is generally a bad idea because you need to make sure you don't accidentally create key collisions. `ValueTuple` is a struct, on the other hand, no allocations, no GC, simple equality check. – vgru Dec 18 '18 at 10:45
  • @Groo plus the array, plus the enumerator for LINQ... – Marc Gravell Dec 18 '18 at 10:50
  • What happens if you have an array of 100 integers that you are combining into a key? My method does create unique keys. Collision only occur due to the GetHash() method and not due to the key itself. The amount of memory depends on size of integer. Number 1-9 with my method take one character (two bytes) rather than 4 bytes. – jdweng Dec 18 '18 at 10:57
  • @jdweng thanks for the suggestion. In this case though, I would prefer to avoid having too many allocations. I only have two ints in the key, and I could implement a custom struct if the default `ValueTuple` doesn't fit properly. – Steinbitglis Dec 18 '18 at 11:04
  • The question is how do you create the unique hash and do you have case where you have only one integer instead of two. I would use a ulong : (a<< 32 | b).GetHashCode(); I think it is same as : a.ToString() + "^" + b.ToString() – jdweng Dec 18 '18 at 11:09
  • @jdweng I'd much rather just do (a << 16) ^ b – Steinbitglis Dec 18 '18 at 11:16
  • That will only work if you have ushort numbers. Why do an exclusive OR? – jdweng Dec 18 '18 at 11:24
  • Collisions or not, it will still work. – Steinbitglis Dec 18 '18 at 11:32

2 Answers2

42

Yes, that's fine. The ValueTuple<...> family is a well-defined set of regular structs with the correct equality and hash-code behaviour to work as dictionary keys. There is a slight caveat in that they are mutable rather than immutable, but that doesn't really impact them in this context thanks to copy semantics (which means: you can't change the key after it has been added, as you're only changing a different copy of the key; this is very different to the problem with mutable classes as keys). You can see the code here.

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
  • 1
    In case I wasn't absolutely clear: `(int,int)` uses `public struct ValueTuple` from that linked file, specifically as `ValueTuple` – Marc Gravell Dec 18 '18 at 10:46
  • 2
    First they made `Tuple` immutable, but a class, then they made `ValueTuple` a struct, but made it mutable. – vgru Dec 18 '18 at 10:50
  • 3
    @Groo indeed, and I think that's a valid and pragmatic way of doing it; a mutable class `Tuple<...>` family would have been incredibly dangerous; a mutable struct `ValueTuple<...>` family is much much safer, and enables a few scenarios without causing any key equality problems. I might have *preferred* it as immutable (I love me some `readonly struct`), but... meh, in this case it makes sense. – Marc Gravell Dec 18 '18 at 10:52
  • I don't have problems with `Tuple` being mutable, but to me it didn't make sense that it was a class in the first place. I really like the way .NET is going with reducing allocations (e.g. `Span`), I would have just preferred *both* of them immutable as you wrote. – vgru Dec 18 '18 at 11:02
4

Being a value type, the hash for ValueTuple follows the default implementation, which is based on the values of the members:

If value types do not override GetHashCode, the ValueType.GetHashCode method of the base class uses reflection to compute the hash code based on the values of the type's fields. In other words, value types whose fields have equal values have equal hash codes.

Tuples are mutable, but because they are copied by value, you can use them safely as dictionary keys. A problem might be if you use a variable of a tuple type, use this variable in Dictionary.Add, then modify this variable and try to access the associated value from the dictionary using the same variable as a key. In this case you will not find it in the dictionary.

The equivalent structure would be like:

MyStruct : struct
{
    public int A;
    public int B;
}
Nick
  • 4,787
  • 2
  • 18
  • 24
  • 4
    "The equivalent structure" - would implement `IEquatable` and have custom `GetHashCode()`/`Equals(object)`/`Equals(MyStruct)` implementations - yes it'll *work* without them, but it'll cause boxing in all the "constrained call" checks and the `EqualityComparer.Default` implementation - which changes the behaviour quite a bit – Marc Gravell Dec 18 '18 at 10:54
  • Yes, I'm interested in `GetHashCode()`, `IEquatable<>` etc. if anyone knows. – Steinbitglis Dec 18 '18 at 11:00
  • @MarcGravell, would you please elaborate more on this? I am afraid I fail to perceive how boxing will get into the way, except causing extra allocations and unboxing operations. – Nick Dec 18 '18 at 11:10
  • 1
    @Nick it won't "get in the way" in terms of changing *the end result*, but it can have a significant impact on *how it gets there*, so: it'll have very different performance characteristics despite behaving *functionally equivalent*. I'm one of those people who considers "very different performance characteristics" to be an important part of the behaviour – Marc Gravell Dec 18 '18 at 11:18
  • @MarcGravell, fair enough. Thanks! – Nick Dec 18 '18 at 11:23
  • Just to make it perfectly clear in case anyone else is confused, it does NOT follow the default implementation as stated, which is good as it would cause problems as pointed out by Mark. Just keep in mind that any more than 7 elements will be nested in a struct, for all of you who were tempted to use a 7+ ValueTuple as a key :) – MichaelRRMoore Oct 15 '21 at 08:45