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

Question

我正在努力为下面给出的学生类编写合适的hashCode函数。

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

观察：对于这个实现，当我调试并检查“HashMap的内部表对象”类时，我发现HashMap中的每个条目都分配了不同的bucket位置。

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

实施：

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

2)如果我允许hashCode冲突:

观察：对于这个实现，当我调试和检查时，发现“hashMap内部表的大小”不断增加，并且只使用hashCode范围内的存储桶。其余所有存储桶索引显示为空。

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

实施：

@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

在每个索引处有一个桶(列表/树)的目的是什么。

HashMap不要求哈希代码是唯一的，因为这通常无法实现（例如，有2 ^ 32个哈希码，但无限多的字符串，因此不可能为每个字符串使用不同的哈希代码）。相反，它只要求碰撞是罕见的。

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

如果超出hashCode范围的桶总是空的，那么增加内部表大小的目的是什么？

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

需要帮助才能正确实现哈希码，以便可以修复上述问题。

我会使用

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

如果id是唯一的（它的名字似乎暗示了这一点），这是一个完美的哈希函数，它甚至可以快速计算：-）

（请注意，hashCode可能大于表大小；HashMap将通过必要时截断它来解决这个问题）