A basic question in a Python interview was whether the dictionary allows mutable key types. The answer is it doesn’t.
Does the same logic apply to Scala Map? I tried using Array/List as keys, and no issues were found.
Can someone explain, what is allowed as a Scala Map key?
Anything is allowed in a Map key, look at the type, is just a generic type parameter K. So no restrictions.
The reason for this is that it will simply use universal equality under the hood.
However, that can lead to surprising behaviour if you don’t know how equality works for a certain type. Which is why it is usually better to just use immutable things like Ints, Strings, Lists, Sets, and any other immutable collection, etc.
But, a mutable key makes sense if you know how to use and that is what you want.
For example:
val arr1 = Array(1, 2, 3)
val arr2 = Array(1, 3, 5)
val map = Map(arr1 -> "foo", arr2 -> "bar")
map.get(key = arr1)
// res: Option[String] = Some("foo")
map.get(key = arr2)
// res: Option[String] = Some("bar")
arr1(1) = 0
map.get(key = arr1)
// res: Option[String] = Some("foo")
map.get(key = Array(1, 2, 3))
// res: Option[String] = None
The first three work because you use the very same array (even despite mutation), but the last one fails because even if they are equivalent they are not equal to arr1.
This may surprise someone unfamiliar with Array equality but makes perfect sense to someone who understands it.
Now, whether or not this is useful depends on the context.
2 Likes
A couple more nuances:
Besides the fact that the key can be any type in principle, keep in mind that Map itself is just an interface, and there are several different implementations. So the precise behavior of a mutable key could vary depending on which Map you are using. (In particular, I’m thinking about things like SortedMap, which is likely to get pretty broken with mutable keys.)
In general, while I can come up with strawman examples where a mutable object would be a reasonable Map key, they’re few and far between. (Basically, only situations where the mutable fields don’t affect equality or sorting.)
So while it is technically legal to use a mutable value for a Map key, I would never recommend it unless you have a very specific requirement and know exactly what you’re doing.
1 Like
I agree with Justin that use cases exist. And perhaps they’re not so rare as all that.
For example, I used maps with mutable keys all the time in the simulation engine I used to work on. The “agents” in the simulation all had unique, immutable IDs that determined hash codes and sorting, but then they also had tons of mutable fields that would change as the simulation progressed. No two agents shared the same ID, so reference equality was what we wanted, we didn’t need field-by-field comparison, both for domain reasons and for performance.
And we had no qualms about using the agents as keys in mutable maps all over the place. I think any other design (for example, segregating the immutable and mutable fields into separate classes, associated via composition) would have cost us in memory usage and runtime performance.
I guess this falls under this clause:
you have a very specific requirement and know exactly what you’re doing
but it doesn’t seem especially esoteric to me, either.
Regardless, I definitely endorse knowing what you’re doing 
3 Likes
In very simple terms, it is possible to use mutable keys, but make sure that the ordering of your keys is immutable in SortedMaps and the hashCode of your keys is immutable in HashMaps. And you should always make sure that equals is consistent with the ordering and with the hashCode.
4 Likes