Why's there no collision?

Question

I'm studying maps with Kotlin, and decided to run this code:

fun main() {
    data class KeyClass(val equals: String, val hash: Int) {
        override fun equals(other: Any?): Boolean {
            return this.equals == (other as KeyClass).equals
        }

        override fun hashCode(): Int {
            return hash
        }

        override fun toString(): String {
            return "($equals,$hash)"
        }
    }

    // collision, since their hashes are the same but they are not equal
    val a1 = KeyClass("a", 1)
    val a2 = KeyClass("b", 1)
    val map = HashMap<KeyClass, String>()
    map[a1] = "value1"
    println(map)
    map[a2] = "value2"
    println(map)

    val map2 = mutableMapOf<KeyClass, String>()
    map2[a1] = "value1"
    println(map2)
    map2[a2] = "value2"
    println(map2)
}

which got me:

{(a,1)=value1}
{(a,1)=value1, (b,1)=value2}
{(a,1)=value1}
{(a,1)=value1, (b,1)=value2}

I thought HashMap's collision resulted in a list. Then when I tried mutableMapOf which is Kotlin's LinkedHashMap, I didn't get any collision either.

questions:

What am I missing from this simple collision example?
What are the most common collision behaviors per Map implementation?

HashMap can story multiple key-value-paird per key hash. This means that collisions make HashMap slow but it still works, correctly. — dan1st, Jan 29 '21 at 15:25
Remember that the contract for [`hashCode()`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-any/hash-code.html) is that equal objects _must_ have equal hash codes; but unequal objects don't _need_ different hash codes — it's perfectly acceptable (though undesirable) for different objects to have the same hash code. (The [Java docs](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--) are more explicit about this.) So anything using hash codes (such as maps) must take that into account. — gidds, Jan 29 '21 at 15:50

score 4 · Accepted Answer · answered Jan 29 '21 at 15:27

That list you're talking about is an internal implementation detail. You can't tell* that this is what's happening within the internals of that map, that's the point of encapsulation.

The only way you can observe collision is timing. So, make a million strings, shove them in a map, then run .containsKey() a couple of times on an entry that is in there.

Then, repeat the exercise, but this time, make a million objects that collide (same hashcode). Then, again, run .containsKey() a couple of times on an entry that is in there.

You'll notice that the second operation returns the exact same answers, but, runs much slower, which is the only thing you're going to observe.

*) With timing observations you could surmise it, but that's as far as it goes.

score 0 · Answer 2 · answered Jan 29 '21 at 15:53

You do have a collision. Probably the result is just not what you expect. You're having a hashCode collision which just slows the map's insertion and retrieval times. I think you expect to have the map containing only 1 entry but even though hashcodes match the equals for the keys do not, so you're still putting 2 different keys in the map producing 2 entries.

Why's there no collision?

2 Answers2