java - 为什么没有碰撞？

Question

我正在用 Kotlin 研究 map ，并决定运行这段代码:

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

这让我:

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

我认为 HashMap 的 collision resulted in a list .然后，当我尝试 mutableMapOf(Kotlin 的 LinkedHashMap)时，我也没有遇到任何冲突。

问题:

1. 我从这个简单的碰撞示例中遗漏了什么？
2. 每个 Map 实现最常见的碰撞行为是什么？

Answer 1

您所说的列表是内部实现细节。您不能说*这是该 map 内部发生的事情，这就是封装的要点。

观察碰撞的唯一方法是计时。因此，创建一百万个字符串，将它们放入映射中，然后对其中的条目运行 .containsKey() 几次。

然后，重复练习，但这一次，制作一百万个碰撞的对象(相同的哈希码)。然后，再次对其中的条目运行 .containsKey() 几次。

您会注意到第二个操作返回完全相同的答案，但运行速度要慢得多，这是您唯一会观察到的事情。

*) 通过时间观察，您可以推测它，但仅此而已。