equals()和hashcode()方法详解

starlin 663 2018-09-21

今天来重新梳理下equals方法和hashcode方法,好了开始

什么是hashcode

hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值,也就是哈希码,哈希码并不是完全唯一的,它是一种算法,让同一个类的对象按照自己不同的特征尽量的有不同的哈希码,但不表示不同的对象哈希码完全不同。

示例伪代码如下:

    String str1 = “aa”,
    str1.hashCode= 3104
    String str2 = “bb”, 
    str2.hashCode= 3106
    String str3 = “aa”, 
    str3.hashCode= 3104
    //根据HashCode由此可得出
    str1!=str2,
    str1==str3

不同的对象有不同的哈希码算法:
1.Object类的hashCode返回对象的内存地址经过处理后的结构,由于每个对象的内存地址都不一样,所以哈希码也不一样。
2.String类的hashCode根据String类包含的字符串的内容,根据一种特殊算法返回哈希码,只要字符串所在的堆空间相同,返回的哈希码也相同
3.Integer类,返回的哈希码就是Integer对象里所包含的那个整数的数值,如:

    Integer in1 = new Integer(10);
    System.out.println(in1.hashCode());//hashcode为10
    Integer in2 = new Integer(10);
    System.out.println(in2.hashCode());//hashcode为10

由此可以看出Java中的hashCode方法就是根据一定的规则将与对象相关的信息(比如对象的存储地址,对象的 字段等)映射成一个数值,这个数值称作为散列值。

hashcode在java中的使用

在Java中Object类的 hashcode方法定义如下:

public native int hashCode();

有此可以看出object类并未对其具体实现,该方法的返回值是int,是本地方法。
对于hash码来说本身是一种提高效率的算法,因此在绝大多数容器中都有用到hash算法,我们来看看之前分析过的HashMap中put方法的源码:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

从以上put方法中可以看出,先比较hash值,然后在查看是否存在该hashCode值,如果存在则调用equals方法重新确定是否存在该元素,如果存在,则更新value值,否则将新的元素添加到HashMap中。同时hashCode方法的存在是为了减少equals方法的调用次数,从而提高程序效率。

Hash算法和Hash冲突

Hash算法:就是根据设定的Hash函数H(key)和处理冲突方法,将一组关键字映射到一个有限的地址区间上的算法。所以Hash算法也被称为散列算法、杂凑算法。

Hash表:通过Hash算法后得到的有限地址区间上的集合。数据存放的位置和key之前存在一定的关系(H(key)=stored_value_hash(数据存放位置)),可以实现快速查询。与之相对的,如果数据存放位置和key之间不存在任何关联关系的集合,称之为非Hash表。

Hash冲突:由于用于计算的数据是无限的H(key),key属于(-∞,+∞),而映射到区间是有限的,所以肯定会存在两个key:key1,key2,H(key1)=H(key2),这就是hash冲突。一般的解决Hash冲突方法有:开放定址法、再哈希法、链地址法(拉链法)、建立公共溢出区。

为了解决哈希冲突,可以采用”开放地址法”或者”链地址法”等来解决问题。HashMap中采用的是链地址法

开放地址法
开放定址法也称为再散列法,基本思想就是,如果p=H(key)出现冲突时,则以p为基础,再次hash,p1=H(p),如果p1再次出现冲突,则以p1为基础,以此类推,直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素,而且因为存在再次hash,所以只能在删除的节点上做标记,而不能真正删除节点。

缺点:容易产生堆积问题;不适合大规模的数据存储;插入时会发生多次冲突的情况;删除时要考虑与要删除元素互相冲突的另一个元素,比较复杂。

再哈希法(双重散列,多重散列)
提供多个不同的hash函数,当R1=H1(key1)发生冲突时,再计算R2=H2(key1),直到没有冲突为止。 这样做虽然不易产生堆集,但增加了计算的时间。

链地址法(拉链法)
链地址法:将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中,查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。HashMap采用的就是链地址法来解决hash冲突。(链表长度大于等于8时转为红黑树)

equals方法

Object类中的定义如下:

    public boolean equals(Object obj) {
        return (this == obj);
    }

在Object这个类中使用== ,对于基本数据类型来说,是用于比较 “值”是否相等的;而对于引用类型来说,是用于比较引用地址是否相同的。

在Object这个类里面提供的equals()方法默认的实现是比较当前对象的引用和你要比较的那个引用它们指向的是否是同一个对象
而在String类中对其进行了重写(比较两个字符串的值是否相等),源码如下:

    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;
    }

从上面的代码中可以看出String类中变成对值得比较,比较两者value是否相等

在重写equals方法的时候,需要按照以下几个原则:
1、自反性:对任意引用值X,x.equals(x)的返回值一定为true.
2、对称性:对于任何引用值x,y,当且仅当y.equals(x)返回值为true时,x.equals(y)的返回值一定为true;
3、传递性:如果x.equals(y)=true, y.equals(z)=true,则x.equals(z)=true
4、一致性:如果参与比较的对象没任何改变,则对象比较的结果也8不应该有任何改变
5、非空性:任何非空的引用值X,x.equals(null)的返回值一定为false

两者相似与比较

对于equals()与hashcode(),比较通用的规则:
①两个obj,如果equals()相等,hashCode()一定相等
②两个obj,如果hashCode()相等,equals()不一定相等

用一个示例代码来说明下:
首先定义一个Person类,重写了equals和hashCode方法

class Person{
    private String name;
    private int age;
    public Person(String name,int age){
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "姓名:" + this.name + ",年龄:" + this.age;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj == null){
            return false;
        }
        if(this == obj){
            return true;
        }
        if(!(obj instanceof Person)){
            return false;
        }
        Person per = (Person) obj;
        if(per.name.equals(this.name) && (per.age == this.age)){
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

测试类如下:

public class Test11 {
    public static void main(String[] args) {
        Person p1 = new Person("aa",10);
        Person p2 = new Person("aa",10);
        HashSet<Person> hashSet = new HashSet();
        hashSet.add(p1);
        hashSet.add(p2);
        System.out.println(hashSet);
    }
}

运行结果:

[姓名:aa,年龄:10]

如果不重写equals和hashCode方法,运行结果:

[姓名:aa,年龄:10, 姓名:aa,年龄:10]

Person类继承自Object类,Object类的hashCode()方法返回的值是地址的一种表现,因为P1和P2的地址是不相同的,所以hashcode值也是不相同的,因此都被加到了set集合里面

还有一点需要注意的是:如果要在HashMap的“键”部分存放自定义的对象,一定要在这个对象重写的equals和hashCode方法
测试类如下:

class User {
    private Integer id;

    public Integer getId() {
        return id;
    }

    public User(Integer id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || !(o instanceof User)) {
            return false;
        } else {
            return this.getId().equals(((User) o).getId());
        }
    }

    @Override
    public int hashCode() {
        return id.hashCode();
    }
}

public class HashMapDemoWithHashCode {
    public static void main(String[] args) {
        User user1 = new User(1);
        User user2 = new User(1);
        HashMap<User, String> map = new HashMap<User,String>();
        map.put(user1, "1");
        System.out.println(map.get(user2));
    }
}

大家可以想下输出结果为多少
当注释掉重写的equals方法和hashCode方法后,输出结果又是多少了

equals一个大坑

关于equals其实还有一个大坑,equals比较的对象除了所谓的相等外,还有一个非常重要的因素,就是该对象的类加载器也必须是同一个,不然equals返回的肯定是false;
之前遇到过一个坑:重启后,两个对象相等,结果是true,但是修改了某些东西后,热加载(不用重启即可生效)后,再次执行equals,返回就是false,因为热加载使用的类加载器和程序正常启动的类加载器不同。
关于类加载器部分,JDK 9 之前的 Java 应用都是由「启动类加载器」、「扩展类加载器」、「应用程序类加载器」这三种类加载器互相配合来完成加载的,如果有需要还可以加入自定义的类加载器来进行拓展;
JDK 9 为了模块化的支持,对双亲委派模式做了一些改动:
扩展类加载器被平台类加载器(Platform ClassLoader)取代。
平台类加载器和应用程序类加载器都不再继承自 java.net.URLClassLoader,而是继承于 jdk.internal.loader.BuiltinClassLoader。具体细节可以自行搜索。

什么情况下需要重写

1.自定义类 需要判断对象在业务逻辑上是否相等
2.如果要在HashMap的“键”部分存放自定义的对象,一定要在这个对象重写的equals和hashCode方法

总结

通过hashcode和equals方法保证了元素的唯一性,当重写equals方法时,必须重写hashCode方法,因为如果不重写这两个方法,就会默认使用Object的方法,一般是不相同的,所以就会导致存储了重复值,与hashset、hashmap等性质冲突。

End,感谢阅读!


# Java基础