内部 HashMap 工作：如何在 java 中实现 hashCode

Question

我正在努力为下面给出的 Student class 编写正确的 hashCode 函数。

1) 我认为 hashCode 应该足够好，这样两个不同对象的 hashCode 就不会相互冲突。

观察：对于此实现，当我调试并检查 'internal table object of HashMap' class 时，我发现 HashMap 中的每个条目都分配了不同的存储桶位置。

问题：在每个索引处有一个桶（list/tree）的目的是什么。

实施：

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + id;
    return result;
}

2) 如果我允许 hashCode 冲突：

观察：对于这个实现，当我调试和检查时，发现'size of internal table of hashMap'不断增加并且只使用hashCode范围内的桶。其余所有桶索引显示为空。

问题：如果超出 hashCode 范围的桶始终为空，增加内部 table 大小的目的是什么。

实施：

@Override
public int hashCode() {
    return id%20;
}

需要帮助以正确实现 hashCode，以便解决上述问题。提前感谢您的帮助。

============================代码================ ===========

public class HashMapTest {

public static void main(String a[]) {
    HashMap<Student, Integer> set = new HashMap<Student, Integer>();

    for (int i = 0; i < 5000; i++) {
        set.put(new Student(i), i);
    }

    set.put(new Student(5001), 5001);
    System.out.println(set.size());
}
}

class Student {
private int id;

public Student(int id) {
    this.id = id;
}

// Add here hashCode() provided in comments.


@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Student other = (Student) obj;
    if (id != other.id)
        return false;
    return true;
}

}

Answer 1

What is the purpose of having a bucket(list/tree) at each index.

HashMap不要求hashCode是唯一的，因为这个一般做不到（比如有2^32个hashcode，但是无限多Strings，所以不可能用不同的每个 String) 的 hashCode。相反，它只要求碰撞罕见.

因此，HashMap 的实现使其即使在发生冲突时仍能正常工作（尽管在这种情况下它可能工作得更慢）。这就是为什么 HashMap 使用可以在必要时存储多个元素的桶。

What is the purpose of increasing internal table size, if the buckets out of hashCode range are always null.

HashMap 调整 table 的大小，因为这样做会拆分桶。通常，拆分一个桶会导致一些元素进入一个桶，而一些元素进入另一个桶，从而提高性能。它没有意识到你的 hashCode 太糟糕了，以至于所有元素都将保留在同一个桶中，所以继续尝试:-)

Need Help for proper hashCode Implementation, so that Above issues can be fixed.

我会用

@Override
public int hashCode() {
    return id;
}

如果 id 是唯一的（正如它的名字所暗示的），这是一个完美的散列函数，甚至可以快速计算:-)

（请注意，hashCode 可能大于 table 大小；HashMap 将根据需要截断它来解决这个问题）

内部 HashMap 工作：如何在 java 中实现 hashCode

Internal HashMap working : How to implement hashCode in java

java

hashmap

hashcode