提问者:小点点

为什么在发生哈希冲突并且Hashmap不允许重复元素时需要linkedlist?


为什么在发生哈希冲突并且HashMap不允许重复元素时需要Linkedlist?我试图理解HashMap中的以下几点:

>

  • HashMap没有给出元素的顺序。但是在我获得插入顺序的元素之后,LinkedHashMapHashMap不同。

    Map<String, Integer>  ht2=new HashMap<String, Integer>();
    ht2.put("A", 20);
    ht2.put("B", 10);
    ht2.put("C", 30);
    ht2.put("D", 50);
    ht2.put("E", 40);
    ht2.put("F", 60);
    ht2.put("G", 70);
    
    for(Entry e:ht2.entrySet())
    {
        System.out.println(e.getKey() +"<<<key  HashMap value>>>"+e.getValue());
    }
    

    HashMap不允许重复的键,是的,我可以得到预期的输出。当我们将对象存储为键时,我们必须根据属性覆盖相等的方法,所以相同的对象或相同的对象信息不会重复。所以如果相同的前一个条目将被覆盖,每个桶将只有一个条目。我不明白当冲突发生时,多个条目是如何在同一个桶中出现的,它正在覆盖前一个值。当这里不允许重复时,为什么这里需要链表。请查看下面的示例。

    HashMap<Employee, Integer> hashMap = new HashMap<Employee, Integer>(4);        
    for (int i = 0; i < 100; i++) {
        Employee myKey = new Employee(i,"XYZ",new Date());
        hashMap.put(myKey, i);
    }
    System.out.println("myKey Size ::"+hashMap.size());
    

    在这里,我创建了100个员工对象,因此创建了100个桶。我可以看到hashcode值何时打印了不同的值。那么链表是如何来到这里的,以及多个条目是如何进入同一个桶的。


  • 共2个答案

    匿名用户

    HashMap中的存储桶数量和条目数不同。

    HashMap的两个键可能具有相同的hashCode,即使它们彼此不相等,这意味着它们都将存储在同一个存储桶中。因此需要链表(或其他一些可以容纳多个条目的结构)。

    即使两个具有不同hashCode的键也可能存储在同一个存储桶中,因为存储桶的数量远小于可能的hashCode值的数量。例如,如果HashMap有16个存储桶,则hashCode0和16的键将映射到同一个存储桶。因此,存储桶必须能够容纳多个条目。

    你的问题的第一部分不清楚。如果你想问为什么你在HashMapLinkedHashMap中看到不同的迭代顺序,原因是HashMap不维护插入顺序,而LinkedHashMap确实维护插入顺序。如果对于某些输入,你看到与HashMap中的插入顺序匹配的迭代顺序,那只是巧合(取决于插入的键碰巧映射到的桶)。

    匿名用户

    当发生HashMap冲突时,就像您在问题中所说的那样,涉及. equals。链表是这样使用的:

    1. 如果发生冲突并且. equals返回true,则旧引用(当然,如果引用不相同)被新引用替换
    2. 如果. equals()对现有值返回false,并且当前存储桶中只有一个对象,HashMap会将其插入索引为0的链表中。请注意,在java的标准HashMap实现中,这个链表中的条目完全是内部的,也就是说,在正常情况下您甚至无法访问该列表
    3. 如果当前桶中有多个条目,它会继续沿着列表向下,直到找到. equals()在列表中的现有对象上返回true并替换的情况,或者它到达列表/桶的末尾,在这种情况下发生第2步

    因此,从技术上讲,您不必担心列表,只需确保您的. hashcode将冲突量降至最低即可