为什么没有碰撞？

Question

我正在学习使用 Kotlin 制作地图，并决定运行以下代码：

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 的 冲突 会导致一个列表。但是当我尝试使用 Kotlin 中的 mutableMapOf（它是 LinkedHashMap）时，我也没有遇到任何冲突。

问题:

1. 这个简单的冲突示例中，我错过了什么？
2. 每种 Map 实现的最常见冲突行为是什么？

- rado

---

HashMap可以在每个键哈希中存储多个键值对。这意味着冲突会使HashMap变慢，但它仍然能够正确地工作。 - dan1st

请记住，hashCode() 方法的约定是相等的对象 必须 具有相同的哈希码；但是不相等的对象不 需要 具有不同的哈希码 —— 尽管这并不理想，但不同的对象具有相同的哈希码也是可以接受的。因此，任何使用哈希码的内容（如映射）都必须考虑到这一点。（Java文档中更明确地说明了这一点。） - gidds

Answer 1

你提到的那个列表是一个内部实现细节。你无法确定这是在映射表的内部发生了什么，这就是封装的意义所在。

观察"碰撞(collision)"的唯一方法是计时。因此，创建一百万个字符串，把它们放入映射表中，然后在里面运行.containsKey()几次。

接下来，再重复这个过程，但这次创建一百万个碰撞的对象(即它们的哈希码相同)。然后，再次运行.containsKey()几次，对已存在的条目进行操作。

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

*)通过计时观察，你可能会推断出一些信息，但仅限于此。

- rzwitserloot

Answer 2

你遇到了碰撞问题。可能结果不是你所期望的。你遇到了哈希码碰撞，这会减慢映射的插入和检索时间。我想你期望映射只包含一个条目，但即使哈希码匹配，键的相等性也不匹配，所以你仍然将两个不同的键放入映射中，产生了两个条目。

- P Sh