Java - HashMap混淆了冲突处理和get()方法

jqjz2hbq  于 2023-02-18  发布在  Java
关注(0)|答案(6)|浏览(170)

我使用的是HashMap,我还不能直接回答get()方法在冲突情况下是如何工作的。
假设n > 1对象被放置在同一个key中。它们是否存储在LinkedList中?它们是否被覆盖,以便只有放置在该key中的最后一个对象存在于那里?它们是否使用了其他碰撞方法?
如果它们放在LinkedList中,是否有办法检索整个列表?如果没有,是否有其他内置的JavaMap,我可以在其中执行此操作?
就我的目的而言,独立链接是理想的,因为如果有冲突,我需要能够浏览列表并获得其中所有对象的信息。在Java中,实现这一点的最佳方法是什么?
谢谢你的帮助!

00jrzges

00jrzges1#

它们是否被覆盖,以便只有最后放置在该键中的对象才存在?
是的,假设您将多个值放入同一个键(根据Object.equals,而不是Object.hashCode),这在Map.put javadoc中指定:
如果Map以前包含键的Map,则旧值将替换为指定值。
如果您想将一个键Map到多个值,最好使用Guava的ListMultimap,具体来说就是ArrayListMultimap,它将键Map到值列表。如果您不能容忍第三方库,那么实际上您必须有一个Map<Key, List<Value>>,尽管这可能有点笨拙。

gt0wga4j

gt0wga4j2#

Hashmap.put()的文档明确指出,“将指定的值与此Map中的指定键关联。如果Map以前包含键的Map,则替换旧值
如果您希望拥有一个与键关联的对象列表,则将列表存储为值。
请注意,“冲突”通常指HashMap的内部工作,其中两个键具有相同的哈希值,而不是对两个不同的值使用相同的键。

lsmepo6l

lsmepo6l3#

假设有n〉1个对象被放置在同一个键中,它们是否被存储在一个链表中?它们是否被覆盖,使得只有最后放置在该键中的对象才存在?它们是否使用了其他的碰撞方法?
同一个键可能有一个示例,因此最后一个会覆盖前一个

Map<String, Integer> map = new HashMap<String, Integer>();
map.put("a", 1);
map.put("a", 2);// it overrides 1 and puts 2 there

链接出现在为不同的键转换相同的散列的地方

参见

brqmpdu1

brqmpdu14#

所以我最后会提供答案:每当HashMap实现遇到冲突时(当两个或多个key对象返回相同的hash()值时),它会将这些键-值对(节点)链接起来,从而通过其结构产生一个LinkedList。因此,每当您使用以前导致与其他对象冲突的key调用“get(key)”时,它将:
1.找一个桶;
1.遍历该bucket所引用的链表以找到确切的key对象;
1.它将在迭代过程中使用LinkedList中Key对象的方法“equals()”,以最终获得所需的Key,并作为结果-您正在寻找的Value。
注意:* 要解决冲突,您应该为Key对象类提供“equals()”和“hashcode()”实现。*
参与HashMap组合的所有类型都应该为它们提供显式实现(equals和hashcode)。
为此,请遵循下一个约定:

-------等于--------

主要条件:[任何内容!= null]
·自反性:x.等于(x)=真。
·对称:x等于(y)== y等于(x)。
·传递性:x.等于(y)== y.等于(z)== x.等于(z)。
·持续:x.equals(y)的多次调用一致地仅返回真或仅返回假(equals中使用的数据不应改变)。
·不可为空:x.等于(空)=假。

-------散列代码----------

·内部一致性:仅当Equals()中的属性更改时,HashCode()才会更改。
·等于一致性:对象x.equals(y)= true必须返回相同的哈希代码。
·碰撞:不相等的对象可以具有相同的HashCode。

rqcrx0a6

rqcrx0a65#

引用:“假设n〉1个对象被放置在同一个键中。它们被存储在一个链表中吗?它们被覆盖了吗?这样只有最后一个被放置在那个键中的对象存在了吗?它们使用了其他的碰撞方法吗?”
是的,如果散列表在这个键下包含了一些东西,它将覆盖它。
您可以实现自己的类来处理这个问题,或者更简单地使用一个HashMap〉,其中K是您的Key对象,V是对象值。请记住,当您执行Map时,使用上一个解决方案,get(K)将检索您选择的List或实现(即:ArrayList),所以这个实现的所有方法都是可用的,也许能满足你的要求。例如,如果你使用Arraylist,你有size,trimToSize,removeRange等。

0md85ypi

0md85ypi6#

在java中,哈希的冲突解决不是基于链接的。据我所知,JDK使用双哈希,这是开放寻址的最佳方式之一。所以没有列表会与哈希槽相关联。
您可以将哈希函数解析为相同键的对象放入列表中,并且可以在表/Map中更新此列表。

package hashing;

import java.util.HashMap;
import java.util.Map;

public class MainAnimal {

    /**
     * @param args
     */
    public static void main(String[] args) {

        Animal a1 = new Animal(1);
        Animal a2 = new Animal(2);

        Map<Animal, String> animalsMap = new HashMap<Animal, String>();

        animalsMap.put(a1,"1");
        animalsMap.put(a2,"2");

        System.out.println(animalsMap.get(a1));

        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("a", 1);
        map.put("a", 2);// it overrides 1 and puts 2 there

        System.out.println(map.get("a"));       

    }

}

class Animal {

    private int index = 0;

    Animal(int index){
        this.index = index;
    }

    public boolean equals(Object obj){
        if(obj instanceof Animal) {
            Animal animal = (Animal) obj;
            if(animal.getIndex()==this.getIndex())
                return true;
            else
                return false;
        }
        return false;
    }

    public int hashCode() {
        return 0;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

}

在上面的代码中,我展示了两个不同的东西.
情况1 -两个不同的示例解析为相同的散列键情况2 -两个相同的示例充当两个不同条目的键。
动物示例,a1和a2解析到相同的键。但是它们不能被覆盖。哈希机制通过哈希槽进行探测,并将条目放置在不同的槽中。
在第二种情况下,键解析为相同的散列键,并且equals方法也满足。2因此重写发生。
如果在动物类中我用这种方法重写equals方法-

public boolean equals(Object obj){
//      if(obj instanceof Animal) {
//          Animal animal = (Animal) obj;
//          if(animal.getIndex()==this.getIndex())
//              return true;
//          else
//              return false;
//      }
//      return false;
        return true;
    }

覆盖发生了。行为就像使用相同的示例。因为a1和a2在同一个桶中,并且等于也返回true。

相关问题