bucket 是单个内存位置还是类似于内存位置数组？

Question

当我们说，对于具有相同哈希码的2个不相等的对象，对象存储在同一个桶中，这实际上意味着什么？

Answer 1

当多个对象落入同一个桶时，它们将作为单链表存储在该桶中。

散列的优点table 是您可以在 O(1) 时间内计算出密钥进入哪个存储桶。这意味着如果每个桶只有一个元素，那么无论 table 中有多少元素，您的查找时间都将保持不变。当您在一个存储桶中有多个密钥时，如果不检查每个密钥，您将无法判断要查找的是哪一个。当你有一个糟糕的散列函数将许多元素放入同一个桶时，你就失去了散列的优势table，它开始表现得更像一个链表。

Answer 2

2 unequal objects having same hash code, the objects are stored in same bucket, what does it imply practically ?

我将用下面的 Product class 示例向您解释这个概念：

产品class:

public class Product {

     private int id;

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

     //add getters and settes for id

     public boolean equals(Object obj) {
         Product product = (Product)obj;
         if(id == product.getId()) {
             return true;
         }
         return false;
     }

     public int hashcode() {
         return 1;
     }
}

测试class:

public class Test {

    public static void main(String[] args) {
        Set<Product> set = new HashSet<>();
        Product p1 = new Product(1);
        Product p2 = new Product(2);
        set.add(p1);
        set.add(p2);
    }
}

假设您已经为 Product class 创建了两个对象 p1 和 p2 并添加到 HashSet，如上所示。

根据 Product class 的合同，p1 和 p2 对象不相等，因为它们的产品 ID 不同。在 HashSet 中，这些 p1 和 p2 对象根据 Product 对象返回的 hashcode 存储在不同的桶中（简单地说是放置不同的内存位置） . 因为你的 p1 和 p2 对象都返回相同的哈希码（来自 Product class 的 hashcode() 方法），它们都将被保存到同一个桶（内存位置）。同样，所有 product 对象（即使 product 对象不相等）都将被推送到同一个桶，因为它们的哈希码相同。

因此，当您尝试使用 set.contains() 从 HashSet 中搜索 product 对象时，必须扫描并从整个产品中找到该对象（假设您已存储 10000 个对象）。

但是当你正确实现你的hashcode()时，即为不相等的Product对象返回不同的哈希码，那么product对象将分布在不同的桶 和 检索变得更快 （无需扫描所有对象）即，它显着提高了性能。

相同的概念适用于所有Hash*相关集合API（HashMap、HashSet等。） Java中的方法].

Is bucket a single memory location or similar to an array of memory locations ?

一个 Bucket 存储多个对象引用，每个 Hash 桶内部使用 LinkedList 或 TreeMap 等数据结构来定位存储的对象。

您可以在此处查看有关同一主题的更多详细信息。

bucket 是单个内存位置还是类似于内存位置数组？

Is bucket a single memory location or similar to an array of memory locations?

java

hashtable

equals

hashcode