Let me give an example.
Suppose I have a
Map[(Int,Int),Boolean] such and at some point I add
((2,4) -> true) to it. Later on I create another tuple which happens to have the same components
(2,4). If I ask whether
(2,4) is in the map, the answer is yes. But its not the same
(2,4) object, it’s just one which happens to contain 2 and 4. How can I ask the map to give me the original
(2,4) object? I could of course iterate over all the keys, but that would be a linear complexity operation, rather than an amortised constant complexity operation.
A use case. Suppose I have a sequence of 100,000 tuples. I could normalise the 100,000 tuples, but building a Map, and then mapping over the sequence to build a new sequence where each tuple is replaced with the hash key which it is
== to. This would decrease the memory allocation by 100,000 * (2 * 64), i.e., replacing 3 64 bit pointers by 1 such pointer, but repeated 100,000 times, thus saving 16Meg of memory.