Java刷题知识点之equals和hashcode()

  1. 云栖社区>
  2. 博客>
  3. 正文

Java刷题知识点之equals和hashcode()

技术小哥哥 2016-09-25 14:30:00 浏览549
展开阅读全文

说简单点,就是,先对hashcode,然后对eauals。

 

  以下是HashMap的jdk1.6   : 

 

 

 

 

  以下是HashMap的jdk1.7  : 

 

 

 

 

 

  以下是HashMap的jdk1.8  : 

 

 

 

 

 

equal() 和hashCode()方法都是基类Object的方法

 

  其源码如下:

复制代码
public boolean equals(Object obj) {
        return (this == obj);
    }

//hashCode method
/*Returns a hash code value for the object. This method is
  supported for the benefit of hash tables such as those provided by {@link java.util.HashMap}.*/

public native int hashCode();
复制代码

  因此,equal()方法就是直接比较对象的地址,对于hashCode(),Java采用了哈希表的原理。 哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。初学者可以这样理解,hashCode方法实际上返回的就是对象存储的物理地址(实际可能并不是)。

 

 

 

 

那么问题来了? 为什么重写equal()方法的时候通常需要重写hashCode()方法呢?

  equal()方法是比较对象是否相等的,hashCode()方法是在当对象存入集合如HashSet对象,以及HashMap对象、HashTable等里面用的,这样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就一下子能定位到它应该放置的物理位置上。 如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了, 就调用它的equals方法与新元素进行比较,相同的话就覆盖,不相同就散列其它的地址。 所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了,几乎只需要一两次

  比如String方法里重写了equal()方法:

复制代码
//String重写的equal方法
  public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

//hashCode()方法 public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }
复制代码

 

 

 

  例子:

复制代码
package com.demo;

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

public class Equal {

    public static void main(String[] args) {
        Map<String,String> maps = new HashMap<String,String>();
        maps.put("1", "zhangsan");
        maps.put("1", "lisi");
        maps.put("2", "wangwu");
        maps.put("2", "zhaoliu");
        maps.put("3", "zhaoliu");

        Iterator<Map.Entry<String, String>> iterator = maps.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<String, String> entry = iterator.next();
            System.out.println(entry.getKey()+entry.getValue());
        }
    }
}
//输出结果:
// 1lisi
// 2zhaoliu
// 3zhaoliu
复制代码

 

  总之 
1、equal()是判断两个对象是否相同的 
2、hashCode()是在HashSet、HashMap等中用的 
3. 通常equal() 和hashCode()要保证对象的一致性。。。。

 

 

 

 

 

 

  以下是关于HashCode的官方文档定义:

  hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。 
在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。 
如果根据 equals(Object) 方法,两个对象是相等的,那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。 
以下情况不 是必需的:如果根据 equals(java.lang.Object) 方法,两个对象不相等,那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能。 
实际上,由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。(这一般是通过将该对象的内部地址转换成一个整数来实现的,但是 JavaTM 编程语言不需要这种实现技巧。) 
当equals方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。

 





 以上这段官方文档的定义,我们可以抽出成以下几个关键点:

  1、hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的;

  2、如果两个对象相同,就是适用于equals(java.lang.Object) 方法,那么这两个对象的hashCode一定要相同;

  3、如果对象的equals方法被重写,那么对象的hashCode也尽量重写,并且产生hashCode使用的对象,一定要和equals方法中使用的一致,否则就会违反上面提到的第2点;

  4、两个对象的hashCode相同,并不一定表示两个对象就相同,也就是不一定适用于equals(java.lang.Object) 方法,只能够说明这两个对象在散列存储结构中,如Hashtable,他们“存放在同一个篮子里”

 

 

 

 

再归纳一下

  就是hashCode是用于查找使用的,而equals是用于比较两个对象的是否相等的。

1、hashcode是用来查找的,如果你学过数据结构就应该知道,在查找和排序这一章有 
例如内存中有这样的位置 
0 1 2 3 4 5 6 7 
而我有个类,这个类有个字段叫ID,我要把这个类存放在以上8个位置之一,如果不用hashcode而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。 
我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID%8,然后把我们的类存放在取得得余数那个位置。比如我们的ID为9,9除8的余数为1,那么我们就把该类存在1这个位置,如果ID是13,求得的余数是5,那么我们就把该类放在5这个位置。这样,以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。 

2、但是如果两个类有相同的hashcode怎么办那(我们假设上面的类的ID不是唯一的),例如9除以8和17除以8的余数都是1,那么这是不是合法的,回答是:可以这样。那么如何判断呢?在这个时候就需要定义 equals了。 
也就是说,我们先通过 hashcode来判断两个类是否存放某个桶里,但这个桶里可能有很多类,那么我们就需要再通过 equals 来在这个桶里找到我们要的类。 
那么。重写了equals(),为什么还要重写hashCode()呢? 
想想,你要在一个桶里找东西,你必须先要找到这个桶啊,你不通过重写hashcode()来找到桶,光重写equals()有什么用啊。

 

 

 

 

 

 
 
从HashMap中通过key查找value时的过程?
  首先调用的是key的hashcode()方法来获取到key对应的hash值h,这样就可以确定键为key的所有值存储的首地址。
  如果h对应的key值有多个,那么程序接着会遍历所有的key,通过调用key的equals()方法来判断key的内容是否相等。只有当equals()方法的返回值为true时,对应的value才是正确的结果。
  比如:如首先向HashMap中添加<“aaa”,"bbb">,接着添加<“aaa”,"ccc">的时候由于与前面添加的数据有相同的key:"aaa",因此会用新的值"ccc"替换“bbb”。
 
 
 
 
 
 
 
对于不同的key值可能会得到相同的hash值,因此就需要对冲突进行处理
  一般而言,对于不同的key值可能会得到相同的hash值,因此就需要对冲突进行处理。一般处理冲突的方法是:开放地址法、再hash法、链地址法等。
 
 
 
 
 
 
HashMap添加元素的操作过程
  在向HashMap中添加键值对<key,value>时,需要经过以下几个步骤:
  首先,调用key的hashcode()方法生成一个hash值h1,如果这个h1在HashMap中不存在,那么直接将<key,value>添加到HashMap中,如果这个h1已经存在,那么找出HashMap中所有hash值为h1的key。
  然后,分别调用key的equals()方法判断当前添加的key值是否与已经存在的key值相同。如果equals()方法返回true,说明当前需要添加的key已经存在,那么HashMap会使用新的value值来覆盖旧的value值。如果equals()方法返回false,说明新增加的key在HashMap中不存在,因此会在HashMap中创建新的映射关系。当新增加的key的hash值已经在HashMap中存在时,就会产生冲突。
 
 
 
 
 
 
 
 

  最近去面试了几家公司,被问到hashCode的作用,虽然回答出来了,但是自己还是对hashCode和equals的作用一知半解的,所以决定把它们研究一下。

以前写程序一直没有注意hashCode的作用,一般都是覆盖了equals,却没有覆盖hashCode,现在发现这是埋下了很多潜在的Bug!今天就来说一说hashCode和equals的作用。

       先来试想一个场景,如果你想查找一个集合中是否包含某个对象,那么程序应该怎么写呢?通常的做法是逐一取出每个元素与要查找的对象一一比较,当发现两者进行equals比较结果相等时,则停止查找并返回true,否则,返回false。但是这个做法的一个缺点是当集合中的元素很多时,譬如有一万个元素,那么逐一的比较效率势必下降很快。于是有人发明了一种哈希算法来提高从该集合中查找元素的效率,这种方式将集合分成若干个存储区域(可以看成一个个桶),每个对象可以计算出一个哈希码,可以根据哈希码分组,每组分别对应某个存储区域,这样一个对象根据它的哈希码就可以分到不同的存储区域(不同的桶中)。如下图所示:

 

  实际的使用中,一个对象一般有key和value,可以根据key来计算它的hashCode。假设现在全部的对象都已经根据自己的hashCode值存储在不同的存储区域中了,那么现在查找某个对象(根据对象的key来查找),不需要遍历整个集合了,现在只需要计算要查找对象的key的hashCode,然后找到该hashCode对应的存储区域,在该存储区域中来查找就可以了,这样效率也就提升了很多。说了这么多相信你对hashCode的作用有了一定的了解。

 

 

 

 

下面就来看看hashCode和equals的区别和联系。

  在研究这个问题之前,首先说明一下JDK对equals(Object obj)和hashCode()这两个方法的定义和规范:在Java中任何一个对象都具备equals(Object obj)和hashCode()这两个方法,因为他们是在Object类中定义的。 equals(Object obj)方法用来判断两个对象是否“相同”,如果“相同”则返回true,否则返回false。 hashCode()方法返回一个int数,在Object类中的默认实现是“将该对象的内部地址转换成一个整数返回”。

 下面是我查阅了相关资料之后对以上的说明做的归纳总结:

1、若重写了equals(Object obj)方法,则有必要重写hashCode()方法。
2、若两个对象equals(Object obj)返回true,则hashCode()有必要也返回相同的int数。
3、若两个对象equals(Object obj)返回false,则hashCode()不一定返回不同的int数。
4、若两个对象hashCode()返回相同int数,则equals(Object obj)不一定返回true。
5、若两个对象hashCode()返回不同int数,则equals(Object obj)一定返回false。
6、同一对象在执行期间若已经存储在集合中,则不能修改影响hashCode值的相关信息,否则会导致内存泄露问题。

 

  想要弄清楚以上六点,先要知道什么时候需要重写equals和hashCode。一般来说涉及到对象之间的比较大小就需要重写equals方法,但是为什么第一点说重写了equals就需要重写hashCode呢?实际上这只是一条规范,如果不这样做程序也可以执行,只不过会隐藏bug。一般一个类的对象如果会存储在HashTable,HashSet,HashMap等散列存储结构中,那么重写equals后最好也重写hashCode,否则会导致存储数据的不唯一性(存储了两个equals相等的数据)。而如果确定不会存储在这些散列结构中,则可以不重写hashCode。但是个人觉得还是重写比较好一点,谁能保证后期不会存储在这些结构中呢,况且重写了hashCode也不会降低性能,因为在线性结构(如ArrayList)中是不会调用hashCode,所以重写了也不要紧,也为后期的修改打了补丁。

 

想要弄清楚以上六点,先要知道什么时候需要重写equals和hashCode。
  一般来说涉及到对象之间的比较大小就需要重写equals方法,但是为什么第一点说重写了equals就需要重写hashCode呢?实际上这只是一条规范,如果不这样做程序也可以执行,只不过会隐藏bug。一般一个类的对象如果会存储在HashTable,HashSet,HashMap等散列存储结构中,那么重写equals后最好也重写hashCode,否则会导致存储数据的不唯一性(存储了两个equals相等的数据)。而如果确定不会存储在这些散列结构中,则可以不重写hashCode。但是个人觉得还是重写比较好一点,谁能保证后期不会存储在这些结构中呢,况且重写了hashCode也不会降低性能,因为在线性结构(如ArrayList)中是不会调用hashCode,所以重写了也不要紧,也为后期的修改打了补丁。

 

 

下面来看一张对象放入散列集合的流程图:

 

  从上面的图中可以清晰地看到在存储一个对象时,先进行hashCode值的比较,然后进行equals的比较。可能现在你已经对上面的6点归纳有了一些认识。我们还可以通过JDK中得源码来认识一下具体hashCode和equals在代码中是如何调用的。

 

HashSet.java 

public boolean add(E e) {  
    return map.put(e, PRESENT)==null;  
    }

 

 

HashMap.java

复制代码
public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value);  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
    }
复制代码

 

 
 
 
 
 

最后再来看几个测试的例子吧:

  测试一:覆盖equals(Object obj)但不覆盖hashCode(),导致数据不唯一性

复制代码
public class HashCodeTest {  
    public static void main(String[] args) {  
        Collection set = new HashSet();  
        Point p1 = new Point(1, 1);  
        Point p2 = new Point(1, 1);  
  
        System.out.println(p1.equals(p2));  
        set.add(p1);   //(1)  
        set.add(p2);   //(2)  
        set.add(p1);   //(3)  
  
        Iterator iterator = set.iterator();  
        while (iterator.hasNext()) {  
            Object object = iterator.next();  
            System.out.println(object);  
        }  
    }  
}  
  
class Point {  
    private int x;  
    private int y;  
  
    public Point(int x, int y) {  
        super();  
        this.x = x;  
        this.y = y;  
    }  
  
    @Override  
    public boolean equals(Object obj) {  
        if (this == obj)  
            return true;  
        if (obj == null)  
            return false;  
        if (getClass() != obj.getClass())  
            return false;  
        Point other = (Point) obj;  
        if (x != other.x)  
            return false;  
        if (y != other.y)  
            return false;  
        return true;  
    }  
  
    @Override  
    public String toString() {  
        return "x:" + x + ",y:" + y;  
    }  
  
}  
复制代码

 

 

 

  输出结果:

true  
x:1,y:1  
x:1,y:1  

 

  原因分析:

(1)当执行set.add(p1)时(1),集合为空,直接存入集合;

(2)当执行set.add(p2)时(2),首先判断该对象(p2)的hashCode值所在的存储区域是否有相同的hashCode,因为没有覆盖hashCode方法,所以jdk使用默认Object的hashCode方法,返回内存地址转换后的整数,因为不同对象的地址值不同,所以这里不存在与p2相同hashCode值的对象,因此jdk默认不同hashCode值,equals一定返回false,所以直接存入集合。

 (3)当执行set.add(p1)时(3),时,因为p1已经存入集合,同一对象返回的hashCode值是一样的,继续判断equals是否返回true,因为是同一对象所以返回true。此时jdk认为该对象已经存在于集合中,所以舍弃。

 
 
 

  测试二:覆盖hashCode方法,但不覆盖equals方法,仍然会导致数据的不唯一性

修改Point类:

复制代码
class Point {  
    private int x;  
    private int y;  
  
    public Point(int x, int y) {  
        super();  
        this.x = x;  
        this.y = y;  
    }  
  
    @Override  
    public int hashCode() {  
        final int prime = 31;  
        int result = 1;  
        result = prime * result + x;  
        result = prime * result + y;  
        return result;  
    }  
  
    @Override  
    public String toString() {  
        return "x:" + x + ",y:" + y;  
    }  
  
}  
复制代码

 

 

输出结果:

false  
x:1,y:1  
x:1,y:1

 

原因分析:

(1)当执行set.add(p1)时(1),集合为空,直接存入集合;

(2)当执行set.add(p2)时(2),首先判断该对象(p2)的hashCode值所在的存储区域是否有相同的hashCode,这里覆盖了hashCode方法,p1和p2的hashCode相等,所以继续判断equals是否相等,因为这里没有覆盖equals,默认使用'=='来判断,所以这里equals返回false,jdk认为是不同的对象,所以将p2存入集合。

 (3)当执行set.add(p1)时(3),时,因为p1已经存入集合,同一对象返回的hashCode值是一样的,并且equals返回true。此时jdk认为该对象已经存在于集合中,所以舍弃。

 

综合上述两个测试,要想保证元素的唯一性,必须同时覆盖hashCode和equals才行。
(注意:在HashSet中插入同一个元素(hashCode和equals均相等)时,会被舍弃,而在HashMap中插入同一个Key(Value 不同)时,原来的元素会被覆盖。)
 
 
 
 
 
 
 
测试三:在内存泄露问题
复制代码
public class HashCodeTest {  
    public static void main(String[] args) {  
        Collection set = new HashSet();  
        Point p1 = new Point(1, 1);  
        Point p2 = new Point(1, 2);  
  
        set.add(p1);  
        set.add(p2);  
          
        p2.setX(10);  
        p2.setY(10);  
          
        set.remove(p2);  
  
        Iterator iterator = set.iterator();  
        while (iterator.hasNext()) {  
            Object object = iterator.next();  
            System.out.println(object);  
        }  
    }  
}  
  
class Point {  
    private int x;  
    private int y;  
  
    public Point(int x, int y) {  
        super();  
        this.x = x;  
        this.y = y;  
    }  
  
  
    public int getX() {  
        return x;  
    }  
  
  
    public void setX(int x) {  
        this.x = x;  
    }  
  
  
    public int getY() {  
        return y;  
    }  
  
  
    public void setY(int y) {  
        this.y = y;  
    }  
  
  
    @Override  
    public int hashCode() {  
        final int prime = 31;  
        int result = 1;  
        result = prime * result + x;  
        result = prime * result + y;  
        return result;  
    }  
  
  
    @Override  
    public boolean equals(Object obj) {  
        if (this == obj)  
            return true;  
        if (obj == null)  
            return false;  
        if (getClass() != obj.getClass())  
            return false;  
        Point other = (Point) obj;  
        if (x != other.x)  
            return false;  
        if (y != other.y)  
            return false;  
        return true;  
    }  
  
  
    @Override  
    public String toString() {  
        return "x:" + x + ",y:" + y;  
    }  
  
}  
复制代码

 

 
 

运行结果:

x:1,y:1  
x:10,y:10

 

 
原因分析:
    假设p1的hashCode为1,p2的hashCode为2,在存储时p1被分配在1号桶中,p2被分配在2号筒中。这时修改了p2中与计算hashCode有关的信息(x和y),当调用remove(Object obj)时,首先会查找该hashCode值得对象是否在集合中。假设修改后的hashCode值为10(仍存在2号桶中),这时查找结果空,jdk认为该对象不在集合中,所以不会进行删除操作。然而用户以为该对象已经被删除,导致该对象长时间不能被释放,造成内存泄露。解决该问题的办法是不要在执行期间修改与hashCode值有关的对象信息,如果非要修改,则必须先从集合中删除,更新信息后再加入集合中。
 
 

 

总结:
1.hashCode是为了提高在散列结构存储中查找的效率,在线性表中没有作用。
2.equals和hashCode需要同时覆盖。
3.若两个对象equals返回true,则hashCode有必要也返回相同的int数。
4.若两个对象equals返回false,则hashCode不一定返回不同的int数,但为不相等的对象生成不同hashCode值可以提高 哈希表的性能。
5.若两个对象hashCode返回相同int数,则equals不一定返回true。
6.若两个对象hashCode返回不同int数,则equals一定返回false。
7.同一对象在执行期间若已经存储在集合中,则不能修改影响hashCode值的相关信息,否则会导致内存泄露问题。

 
 
 
 
 
 
 
 扩展
  因为,自己是大数据开发,
 

 

 
复制代码
importjava.io.*;
importorg.apache.hadoop.io.*;
public class TextPair implements WritableComparable {
    private    Text first;//Text 类型的实例变量 first
    private    Text second;//Text 类型的实例变量 second
    
    public TextPair() {
        set(newText(),newText());
    }
    
    public TextPair(String first, String second) {
        set(new Text(first),new Text(second));
    }
    
    public TextPair(Text first, Text second) {
        set(first, second);
    }
    
    public void set(Text first, Text second) {
        this.first = first;
        this.second = second;
    }
    
    public Text getFirst() {
        return first;
    }
    
    public Text getSecond() {
        return second;
    }
    
    //将对象转换为字节流并写入到输出流out中
    @Override
    public void write(DataOutput out)throwsIOException {
        first.write(out);
        second.write(out);
    }
    
    //从输入流in中读取字节流反序列化为对象
    @Override
    public void readFields(DataInput in)throwsIOException {
        first.readFields(in);
        second.readFields(in);
    }
    
    @Override
    public int hashCode() {
        return first.hashCode() *163+ second.hashCode();
    }
    
    
    @Override
    public boolean equals(Object o) {
        if(o instance of TextPair) {
            TextPair tp = (TextPair) o;
            return first.equals(tp.first) && second.equals(tp.second);
        }
            return false;
    }
    
    @Override
    publicString toString() {
        return first +"\t"+ second;
    }
    
    //排序
    @Override
    public int compareTo(TextPair tp) {
        int cmp = first.compareTo(tp.first); 
        if(cmp !=0) {
            return cmp;
        }
        return second.compareTo(tp.second);
    }
}


网友评论

登录后评论
0/500
评论
技术小哥哥
+ 关注