根据我的理解,我认为:

两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode

我说的对吗?

如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?

有人能解释一下HashMap内部是如何使用对象的hashcode的吗?


当前回答

每个Entry对象表示键值对。如果一个桶有多于1个Entry,则字段next指向其他Entry对象。

有时候,两个不同对象的hashcode可能是相同的。在这种情况下,2个对象将保存在一个桶中,并将显示为LinkedList。入口点是最近添加的对象。该对象引用具有next字段的其他对象,等等。最后一项为空。 当您使用默认构造函数创建HashMap时

数组的大小为16,默认负载平衡为0.75。

(源)

其他回答

这将是一个很长的答案,拿着饮料继续阅读…

哈希就是在内存中存储一个键-值对,可以更快地读写。它将键存储在数组中,值存储在LinkedList中。

假设我想存储4个键值对

{
“girl” => “ahhan” , 
“misused” => “Manmohan Singh” , 
“horsemints” => “guess what”, 
“no” => “way”
}

为了存储键,我们需要一个4元素的数组。现在我如何将这4个键中的一个映射到4个数组索引(0,1,2,3)呢?

因此java找到单个键的hashCode并将它们映射到特定的数组索引。 哈希码公式是-

1) reverse the string.

2) keep on multiplying ascii of each character with increasing power of 31 . then add the components .

3) So hashCode() of girl would be –(ascii values of  l,r,i,g are 108, 114, 105 and 103) . 

e.g. girl =  108 * 31^0  + 114 * 31^1  + 105 * 31^2 + 103 * 31^3  = 3173020

哈希和女孩!!我知道你在想什么。你对狂野二重唱的迷恋可能会让你错过一件重要的事情。

为什么java要把它乘以31 ?

因为,31是奇数质数形式为2^5 - 1。奇素数降低了哈希碰撞的概率

这个哈希码是如何映射到数组下标的呢?

答案是,哈希码%(数组长度-1)。在我们的例子中,“girl”被映射为(3173020 % 3)= 1。它是数组的第二个元素。

值“ahhan”存储在与数组索引1相关的LinkedList中。

HashCollision -如果您尝试使用上面描述的公式查找密钥“误用”和“horsemints”的hasHCode,您将看到两者都给出相同的1069518484。Whooaa ! !〇教训

2个相等的对象必须具有相同的hashCode,但如果没有保证 hashCode匹配,则对象相等。所以它应该存储 这两个值都对应于1号桶的“误用”和“horsemints” (1069518484% 3)。

现在哈希图看起来是-

Array Index 0 –
Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”)
Array Index 2 – LinkedList (“way”)
Array Index 3 – 

现在,如果有人试图找到键“horsemints”的值,java很快就会找到它的hashCode,对它进行模块化,并开始在LinkedList对应的索引1中搜索它的值。因此,这样我们就不需要搜索所有的4个数组索引,从而使数据访问更快。

但是,等一下。有3个值在那个linkedList对应的数组索引1,它如何找出哪一个是值为关键“horsemints”?

其实我撒谎了,我说HashMap只是在LinkedList中存储值。

它将两个键值对存储为映射条目。实际上Map是这样的。

Array Index 0 –
Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>)
Array Index 2 – LinkedList (<”no” => “way”>)
Array Index 3 – 

现在你可以看到,当遍历对应于ArrayIndex1的linkedList时,它实际上会将linkedList的每个条目的key与horsemints进行比较,当它找到一个时,它会返回它的值。

希望你读得开心:)

你的第三个断言是不正确的。

两个不相等的对象拥有相同的哈希码是完全合法的。它被HashMap用作“第一遍过滤器”,以便映射可以快速找到具有指定键的可能条目。然后测试具有相同哈希码的键是否与指定的键相等。

您不会希望要求两个不相等的对象不能具有相同的哈希码,否则将限制为232个可能的对象。(这也意味着不同类型甚至不能使用对象的字段来生成哈希码,因为其他类可以生成相同的哈希码。)

import java.util.HashMap;

public class Students  {
    String name;
    int age;

    Students(String name, int age ){
        this.name = name;
        this.age=age;
    }

    @Override
    public int hashCode() {
        System.out.println("__hash__");
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println("__eq__");
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Students other = (Students) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    public static void main(String[] args) {

        Students S1 = new Students("taj",22);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Output:

__ hash __

116232

__ hash __

116201

__ hash __

__ hash __

2

因此,在这里我们可以看到,如果对象S1和S2都有不同的内容,那么我们可以非常确定,我们覆盖的Hashcode方法将为两个对象生成不同的Hashcode(116232,11601)。因为有不同的哈希码,所以它甚至不需要调用EQUALS方法。因为不同的Hashcode保证对象中不同的内容。

    public static void main(String[] args) {

        Students S1 = new Students("taj",21);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Now lets change out main method a little bit. Output after this change is 

__ hash __

116201

__ hash __

116201

__ hash __

__ hash __

__ eq __

1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally  calls Equal method to verify this. 


Conclusion 
If hashcode is different , equal method will not get called. 
if hashcode is same, equal method will get called.

Thanks , hope it helps. 

你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html上找到很好的信息

总结:

HashMap的工作原理是哈希

put(key, value): HashMap将key和value对象都存储为Map.Entry。Hashmap应用hashcode(key)来获取桶。如果有碰撞,HashMap使用LinkedList存储对象。

get(key): HashMap使用key Object的hashcode来查找桶的位置,然后调用keys.equals()方法来识别LinkedList中的正确节点,并在Java HashMap中返回该键的相关值对象。

记住这里对hashmap结构的解释,也许有人可以解释Baeldung上的以下段落:-

Java有接口Map的几个实现,每个实现都有自己的特殊性。

但是,现有的Java核心Map实现都不允许Map处理单个键的多个值。

正如我们所看到的,如果我们试图为同一个键插入两个值,第二个值将被存储,而第一个值将被删除。

它还将返回(由put(K键,V值)方法的每个正确实现):

Map<String, String> map = new HashMap<>();
assertThat(map.put("key1", "value1")).isEqualTo(null);
assertThat(map.put("key1", "value2")).isEqualTo("value1");
assertThat(map.get("key1")).isEqualTo("value2");