根据我的理解,我认为:

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

我说的对吗?

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

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


当前回答

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

哈希就是在内存中存储一个键-值对,可以更快地读写。它将键存储在数组中,值存储在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是如何工作的,但是会给出一个例子,这样我们就可以通过将HashMap与现实联系起来来记住它是如何工作的。

我们有Key, Value,HashCode和bucket。

在一段时间内,我们将把它们与以下内容联系起来:

一个社会 HashCode ->社会地址(总是唯一的) 社会中的房子 Key ->房屋地址。

使用Map.get(key):

Stevie想去他的朋友(Josse)的房子,他住在一个VIP社会的别墅里,让它成为javalavers社会。 Josse的地址是他的SSN(每个人都不一样)。 有一个索引,我们可以根据社会安全号找到协会的名字。 这个索引可以被认为是一个找出HashCode的算法。

SSN协会名称 92313(Josse’s) -爪哇 13214—AngularJSLovers 98080—javalover 53808 -生物爱好者


这个SSN(密钥)首先给我们一个HashCode(来自索引表),它只是社会的名字。 现在,多个房子可以在同一个社会中,所以HashCode可以是公共的。 假设,社会对两个房子都是公用的,我们如何识别我们要去哪个房子,是的,通过使用(SSN)密钥,它只是房子的地址

使用Map.put(关键字,值)

这将通过查找HashCode为该值找到一个合适的社会,然后存储该值。

我希望这能有所帮助,而且这是可以修改的。

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

哈希就是在内存中存储一个键-值对,可以更快地读写。它将键存储在数组中,值存储在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是这样工作的(这有点简化,但它说明了基本机制):

它有许多“桶”,用来存储键值对。每个桶都有一个唯一的编号——用来标识该桶。当您将一个键值对放入映射时,hashmap将查看键的哈希码,并将该对存储在标识符为键的哈希码的bucket中。例如:密钥的哈希码为235 ->,存储在桶号为235的桶中。(注意,一个桶可以存储多个键-值对)。

当您在hashmap中查找一个值时,通过给它一个键,它将首先查看您给出的键的哈希代码。然后,hashmap将查看相应的存储桶,然后它将通过equals()比较您给出的键与存储桶中所有对的键。

现在,您可以看到这对于在map中查找键-值对是多么高效:通过键的哈希代码,哈希映射立即知道要在哪个bucket中查找,因此它只需要测试该bucket中的内容。

看看上面的机制,你也可以看到对键的hashCode()和equals()方法有什么必要的要求:

If two keys are the same (equals() returns true when you compare them), their hashCode() method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it's going to look in the same bucket). If two keys are different, then it doesn't matter if their hash codes are the same or not. They will be stored in the same bucket if their hash codes are the same, and in this case, the hashmap will use equals() to tell them apart.

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. 

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

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

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