Are ValueTuples suitable as dictionary keys?

Question

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?

Murillo

The easier way is to use string join. int[] input = { 1, 2, 3 }; string key = string.Join("^",input.Select(x => x.ToString())); – Shankle

@Shankle that would be a terrible idea if you care about allocations – Alkalimeter

@MarcGravell : What do you mean? – Shankle

@Shankle 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. – Alkalimeter

@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. – Capability

@Groo plus the array, plus the enumerator for LINQ... – Alkalimeter

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. – Shankle

@Shankle 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. – Murillo

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() – Shankle

@Shankle I'd much rather just do (a << 16) ^ b – Murillo

That will only work if you have ushort numbers. Why do an exclusive OR? – Shankle

Collisions or not, it will still work. – Murillo

Answer 1

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.

Alkalimeter

In case I wasn't absolutely clear: (int,int) uses public struct ValueTuple<T1, T2> from that linked file, specifically as ValueTuple<int,int> – Alkalimeter

First they made Tuple immutable, but a class, then they made ValueTuple a struct, but made it mutable. – Capability

@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. – Alkalimeter

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<T>), I would have just preferred both of them immutable as you wrote. – Capability

Answer 2

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;
}

Trek

"The equivalent structure" - would implement IEquatable<MyStruct> 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<T>.Default implementation - which changes the behaviour quite a bit – Alkalimeter

Yes, I'm interested in GetHashCode(), IEquatable<> etc. if anyone knows. – Murillo

@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. – Trek

@Trek 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 – Alkalimeter

@MarcGravell, fair enough. Thanks! – Trek

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 :) – Davena