java - 关于Java HashMap冲突的困惑

Question

我有一个名为Department的自定义类，其中equals和hashCode都被覆盖。请找到以下代码段:

class Department {
    private final int id;
    private final String name;
    private final int count;

    public Department(int id, String name, int count) {
        super();
        this.id = id;
        this.name = name;
        this.count = count;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (!(obj instanceof Department))
            return false;

        final Department emp = (Department) obj;

        return emp.name != null && emp.name.equals(name) && emp.count == count && emp.id == id;
    }

    @Override
    public int hashCode() {
        return count + name.length();
    }

    @Override
    public String toString() {
        return "ID: " + id + ", Name: " + name + ", Age: " + count + ", hashCode: " + hashCode();
    }
}

在main方法中，我以这样的方式初始化了两个部门，它们的均等值将返回false，但将具有相同的哈希码。然后将这两个部门添加到HashMap中。请找到主要方法调用，如下所示:

public static void main(String[] args) {
        final Department dep1 = new Department(1, "software", 35);
        final Department dep2 = new Department(2, "software", 35);
        System.out.println("\n\nIs dep1.equals(dep2)? -- " + dep1.equals(dep2));
        System.out.println("Is dep1==dep2? -- " + (dep1 == dep2));

        System.out.println("\n\nDepartment 1: " + dep1);
        System.out.println("Department 2: " + dep2);

        final HashMap<Department, String> departmentHashMap = new HashMap<>();
        departmentHashMap.put(dep1, "Software 1");
        System.out.println("\n\nDepartment 1 added to map");
        System.out.println("Is Department 2 available in map? -- " + departmentHashMap.get(dep2));
        System.out.println("Is Department 2 key available in map? -- " + departmentHashMap.containsKey(dep2));
        departmentHashMap.put(dep2, "Software 2");

        System.out.println("\n\nDepartment 1: " + departmentHashMap.get(dep1));
        System.out.println("Department 2: " + departmentHashMap.get(dep2));

        for (final Entry<Department, String> entry : departmentHashMap.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }

根据文档，当两个不同的条目具有相同的哈希码但不满足等于比较时，将在HashMap中引起冲突，并且条目将存储为链接列表。我没有观察到这种特殊行为。但是，当我遍历HashMap条目时，它们是作为单个条目而不是链表获取的。请找到以下输出:

Is dep1.equals(dep2)? -- false
Is dep1==dep2? -- false


Department 1: ID: 1, Name: software, Age: 35, hashCode: 43
Department 2: ID: 2, Name: software, Age: 35, hashCode: 43


Department 1 added to map
Is Department 2 available in map? -- null
Is Department 2 key available in map? -- false


Department 1: Software 1
Department 2: Software 2
Key: ID: 1, Name: software, Age: 35, hashCode: 43, Value: Software 1
Key: ID: 2, Name: software, Age: 35, hashCode: 43, Value: Software 2

我无法在任何地方引用示例这种特殊情况。任何有助于澄清概念的帮助将不胜感激。

Answer 1

我将尝试带您深入了解 Associative Array ADT ，它的实现是有问题的数据结构-HashMap / HashTable。

我将尽力弄清楚一些学术和理论背景，以便您更好地理解该主题。
HashMap是Associative Array抽象数据类型(ADT)的一种实现，并且该ADT最常实现为Hash Table数据结构。因此，您可以将HashMap和HashTable视为概念上相同的数据结构，尤其是在 Java 中，在该结构中，DS特性级别的实现(例如线程安全性，并发性，排序等)仅次于其他。

在Hash Table中(以及在HashMap中，我将在下文中交替使用这两个结构名称)，数据结构的最重要特征是，它使您有Ө(1)时间通过以下方式进行读取，插入和更新操作:在内部实现关联数据结构，这要归功于哈希函数H(x)的思想。
Hash Function是哈希表中的基本概念。计算它，然后在基础实现中通过Index Normalization对其进行规范化。

底层的Hash Table由其后备数组实现。该后备数组存储(类型为):

哈希表的实际条目，因此该支持数组属于HashTable的特定条目类型-Entry<K, V>[]。 (通常，哈希表的条目是一种特殊的类型/类，包含该键和该值的组成-即代表一个条目，并且其实例保存在支持数组中； 或

哈希表条目的存储桶。现在，在这里请密切注意，因为我将在很深的层次上对此进行解释。在这种情况下，数组的类型将为桶，每个桶将依次成为辅助数据结构的实例，该数据结构通常是 LinkedList 。因此，长话短说，在这种情况下，您可以想象支持数组将类似于LinkedList<K, V>[]。 <-此数组的每个元素将是LinkedList实例，在该实例中，您可能有许多对象。

现在，我们准备介绍碰撞。

碰撞
Hash Function H(x)的重要属性之一是，它必须是确定性的和统一的。良好的均匀H(x)可以减少碰撞的可能性-这意味着H(x)不太可能将两个不同的输入散列到同一输出，但是，可能会发生! ，对于两个不同的输入，您可能会获得相同的输出，该输出将被标准化为相同的数字，并有效地指向支持数组的相同插槽。

因此，这就是碰撞-当两个输入哈希到同一索引时。

问:如何处理？
答:有两种解决该问题的技术策略。

单独链接

打开寻址

由于您的问题针对的是存储列表实现的后备数组，因此这是一种单独链接策略，在此我不多说几句(如果您发现我的答案有用，我以后可能还会添加关于线性探测的说明)。

单独链接

单独链接 –通过维护辅助数据结构(通常是链表，但也可以使用其他数据结构)来处理所有冲突，这些冲突是所有散列到相同特定哈希值的不同键。
(持有冲突键的辅助数据结构有时称为存储桶，代表许多元素的集合)

如上所述，在此策略/技术中，后备数组的每个元素都是(哈希表条目的)Linked List数据结构，每当两个或多个元素(键)发生冲突(哈希到相同的哈希值)时，它们条目只是添加到相应的“链接列表”中(放置在冲突的哈希值的位置)，但是只有在这些条目的原始(哈希之前)键不同的情况下才添加。如果两个条目的键在散列后发生冲突，并且这些条目的原始键也相等，则现有条目将替换为我们要添加的条目。
例如，如果哈希表包含{3, "Subhrat"}条目，而我们要再添加一个条目{5，“David”}，但由于哈希功能不佳，则将3和5哈希成相同的值x，则后面的元素将被添加到相应的链表(在后备数组的索引x处)；但是，如果两个键散列为相同的值，并且它们的原始状态也相同(散列之前)，则现有条目将被后者替换。

现在是您没有观察到的部分。

问:在单独链接的情况下如何完成查找？
一个:

我们将密钥提供给哈希表；

键被散列，结果值表示后备数组的索引；

数组中第二步的相应插槽中有一个存储桶(在我们的示例中为“链表”)，在该存储桶中原始键(第一步骤)被查找/搜索。

我希望这可以为Hash Map和Hash Table的工作原理提供一些启示，现在您了解了更多为什么不能真正看到LinkedList被取出的原因。