首页 > > 程序设计 > Java技术 >

关于重写equals()和hashCode()的思考__从HashMap…

2019-08-16 09:58:16来源：博客园阅读 ()

关于重写equals()和hashCode()的思考__从HashMap源码分析

最近这几天一直对equals()和hashCode()的事搞不清楚，云里雾里的。

为什么重写equals()，我知道。

但是为什么要两个都要重写呢，我就有点迷糊了，所以趁现在思考清楚后记录一下。

通过本文，你可以了解到

1.为什么要重写equals(从普通角度而言)

2.为什么要重写equals(从java数据结构角度而言)

3.为什么要重写hashCode

4.哈希值与哈希表索引的关系

5.哈希冲突

6.拉链法

7.HashSet和HashMap是怎么添加元素的

本来我打算将源码单独写一篇博文的，但想想还是在这里写算了。

起因

无非就是一道面试题：“你重写过 equals 和 hashcode 吗，为什么重写equals时必须重写hashCode方法？”

1.为什么要重写equals()

也不用多说大道理了，我们都知道Object类的equals()其实用的也是“==”。

我们也知道“==”比较的是内存地址。

所以当对象一样时，它的内存地址也是一样的，所以此时不管是“==”也好，equals()也好，都是返回true。

例子

public static void main(String[] args) {
        String s = "大木大木大木大木";
        String sb = s;

        System.out.println(s.equals(sb));

        System.out.println(s == sb);
    }

输出结果

true
true

但是，我们有时候判断两个对象是否相等不一定是要判断它的内存地址是否相等，我只想根据对象的内容判断。

在我们人为的规定下，我看到对象的内容相等，我就认为这两个对象是相等的，怎么做呢？

很显然，用“==”是做不到的，所以我们需要用到equals()方法，

我们需要重写它，让它达到我们上面的目的，也就是根据对象内容判断是否相等，而不是根据对象的内存地址。

例子：没有重写equls()

public class MyClass {

    public static void main(String[] args) {
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("jojo", 18);

        System.out.println(s1.equals(s2));
    }

    private static class Student {
        String name;
        int age;

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

输出结果

false

结果分析

两个长得一样的对象比较，为什么equals()会返回false。

因为我们的Student类没有重写equals()方法，所以它调用的其实是Object类的equals()，其实现就是“==”。

所以虽然两个对象长一样，但它们的内存地址不一样，两个对象也就不相等，所以就返回了false。

所以我们为了达到我们先前的规定，需要重写一下equals()方法，至于重写此方法，有几点原则，我就不多说了，都是些废话。

例子：重写了equals()方法

 private static class Student {
        String name;
        int age;

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

　　　　 /**
　　　　　* 重写后的equals()是根据内容来判定相等的
　　　　　*/

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return age == student.age &&
                    name.equals(student.name);
        }
    }

此时再次执行以下代码

public static void main(String[] args) {
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("jojo", 18);

        System.out.println(s1.equals(s2));
    }

输出结果

true

结果分析

显然我们此时已经达到了目的，根据内容能够判定对象相等。

总结

1.Object类的equals()方法实现就是使用了"=="，所以如果没有重写此方法，调用的依然是Object类的equals()

2.重写equals()是为了让对象根据内容判断是否相等，而不是内存地址。

2.哈希值

关于hashCode()，百度百科是这么描述的。

hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值 
详细了解请 参考 public int hashCode()返回该对象的哈希值。
支持此方法是为了提高哈希表（例如 java.util.Hashtable 提供的哈希表）的性能。

因为hashCode()的返回值就是一个哈希值。

所以下文没有特别说明的话，文中的哈希值是指hashCode()，hashCode()同样也可以指哈希值。

哈希表的内容我这里也不多提，但我们需要明白的是

哈希值相当于一个元素在哈希表中的索引位置。

注意这里是相当，而不是说确确切切就是 哈希值 = 索引。

在java中，hashCode()返回的是int类型的一个哈希值。
int类型的范围在不同编译器有所不同，但也差不了什么。
我们以32位编译器为例，它的范围是-2^31 到 2^31-1。
所以大概大概也都是四十多亿个数了。
如果一个哈希值就是一个索引的话，那么哈希表的长度就是四十多亿，这明显不可能。
一个哈希值使用一个索引，是行不通的，那就多个有相同特征的哈希值使用一个索引。
所以为了解决这个问题，可以用什么 除留取余法 之类的，让这些哈希值限定在一个索引范围内。
这样一来，哈希值的使用姑且解决了，但又出现一个致命的问题，那就是哈希冲突。
因为你这么多哈希值都挤在一个范围，肯定会有出现一个索引多个哈希值的问题，这里先抛开不讲。

我们回到最初的讨论，从上面的话来看，哈希值才相当于索引，而不是确确切切等于索引。

因为真要讲的话，不可能一台机器上真就使用了那么多内存，所以哈希冲突的概率很小。

哈希冲突少了，哈希值一人使用一个索引还是绰绰有余的，

其中还要知道，

元素的哈希值相同，内容不一定相同

元素的内容相同，哈希值一定相同。

为什么第一句会这么说呢，因为其就是接下来所说的哈希冲突。

3.哈希冲突

哈希冲突就是哈希值重复了，撞车了。

最直观的看法是，两个不同的元素，却因为哈希算法不够强，算出来的哈希值是一样的。

所以解决哈希冲突的方法就是哈希算法尽可能的强。

例子：弱的哈希算法

public class MyClass {
    public static void main(String[] args) {
        //Student对象
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("JOJO", 18);//用equals()比较，并附带hashCode()
        System.out.println("哈希值：s1-->" + s1.hashCode() + "  s2-->" + s2.hashCode());
    }

    private static class Student {
        String name;
        int age;

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

        /**
         * 此方法只是简单的运算了name和age。
         * @return
         */
        @Override
        public int hashCode() {
            int nameHash = name.toUpperCase().hashCode();
            return nameHash ^ age;
        }
    }
}

输出结果

哈希值：s1-->2282840  s2-->2282840

结果分析

我们可以看到这个两个不同的对象却因为简单的哈希算法不够健壮，导致了哈希值的重复。

这显然不是我们所希望的，所以可以用更强的哈希算法。

例子：强的哈希算法

public class MyClass {
    public static void main(String[] args) {
        //Student对象
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("JOJO", 18);

        //用equals()比较，并附带hashCode()
        System.out.println("哈希值：s1-->" + s1.hashCode() + "  s2-->" + s2.hashCode());
    }

    private static class Student {
        String name;
        int age;

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

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

输出结果

哈希值：s1-->101306313  s2-->70768585

结果分析

上面用的哈希算法是IDEA自动生成的，它是使用了java.util.Objects的hash()方法，

总而言之，好的哈希算法能够尽可能的减少哈希冲突。

总结

哈希冲突可以减少，但无法避免，解决方法就是哈希算法尽可能的强。

所以结合上面而言，我们可以认为，哈希值越唯一越好，这样在哈希表中插入对象时就不容易在同一个位置插入了。

但是，我们希望哈希值唯一，现实却不会如我们希望，在哈希表中，哈希码值的计算总会有撞车，有重复的，

关于哈希值的介绍仅此这么点，更多详情可以继续学习，这里就不多提及了。

另：拉链法

我们上面说到因为多个哈希值使用同一个索引而引发哈希冲突，但哈希冲突不可避免，那就想办法解决。

除了在哈希值方面下手，也可以从存储方面下手，比如待会要提的拉链法，因为在jdk1.8的HashMap就使用了这个。

（ps：经过评论的指出，我的表述有错误，抱歉，现已更改。感谢评论者@我的粪斗）

存储方面怎么实现呢，那就是拉链法，拉链法一直都被HashMap使用着。

但在jdk1.8之后，HashMap由数组+链表变成了数组+链表+红黑树。关于红黑树就不提及了，主要就是拉链长了就转换。

其中对于插入方法1.8与1.7及之前的有区别，1.8使用的是尾插法。1.7及以前使用的是头插法，原因是解决多线程环境下get方法死循环的问题。

拉链法我也不讲那么多官方话，直接看图就懂。

拉链法就是这样，索引相同的元素就用链表串起来。

4.极其重要的一点

不是所有重写equals()的都要重写hashCode()，如果不涉及到哈希表的话，就不用了，比如Student对象插入到List中。

涉及到哈希表，比如HashSet, Hashtable, HashMap这些数据结构，Student对象插入就必须考虑哈希值了。

5.重写

以下的讨论是设定在jdk1.8的HashSet，因为HashSet本质是哈希表的数据结构，是Set集合，是不允许有重复元素的。

它底层使用的是HashMap，所以也可说是讨论HashMap，无差无差。

在这种情况下才需要重写equals()和重写hashCode()。

我们分四种情况来说明。

1.两个方法都不重写

例子

public class MyClass {

    public static void main(String[] args) {
        //Student对象
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("jojo", 18);

        //HashSet对象
        HashSet set = new HashSet();
        set.add(s1);
        set.add(s2);

        //输出两个对象
        System.out.println(s1);
        System.out.println(s2);

        //输出equals
        System.out.println("s1.equals(s2)的结果为：" + s1.equals(s2));

        //输出哈希值
        System.out.println("哈希值为：s1->" + s1.hashCode() + "  s2->" + s2.hashCode());

        //输出set
        System.out.println(set);
    }

    private static class Student {
        String name;
        int age;

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

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }
}

输出结果

Student{name='jojo', age=18}
Student{name='jojo', age=18}
s1.equals(s2)的结果为：false
哈希值为：s1->2051450519 s2->99747242
[Student{name='jojo', age=18}, Student{name='jojo', age=18}]

结果分析

equals() 返回 false

哈希值不一致

两个都没有重写，HashSet将s1和s2都存进去了，明明算是重复元素，为什么呢？

到底HashSet怎么才算把两个元素视为重复呢？

我们看源码：

HashSet的add()调用了它底层的HashMap的put()。

而在HashMap的put()中又调用了putVal()。

当s1添加进来时，部分源码为

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 第一次添加元素，tab数组为空，初始化数组
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // i为索引，根据hash算出索引
        // tab[i]此时为null，所以s1就被插进到tab[i]
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

源码中的hash已经是被HashMap根据元素的hashCode()重新算出来的。

hash的题外话

我们知道HashTable直接使用对象的hashCode()，而HashMap是重新计算哈希值。

但HashMap重新计算哈希值也是用到了元素的hashCode()，才算出结果的。

所以总的来说hashCode()是唯一的变量，它跟hash是一一对应的。

再看s2添加进来时，部分源码为

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // tab数组已经初始过，跳过执行
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 此时因为没有重写hashCode()，所以s1和s2的哈希值是系统随机算的，不一致不相同
        // 所以根据哈希值算出来的hash也是新的
        // 此时的i也是一个新的，s2插入tab[i]
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

所以第一种情况的存储情况如下图，当然，这是一种示意图，并不是真的索引，因为i也是算出来的。

存储示意图：

它们因为哈希值不同而直接被分配到两个不同的位置里了。

2.只重写equals()

例子

public class MyClass {

    public static void main(String[] args) {
        //Student对象
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("jojo", 18);

        //HashSet对象
        HashSet set = new HashSet();
        set.add(s1);
        set.add(s2);

        //输出两个对象
        System.out.println(s1);
        System.out.println(s2);

        //输出equals
        System.out.println("s1.equals(s2)的结果为：" + s1.equals(s2));

        //输出哈希值
        System.out.println("哈希值为：s1->" + s1.hashCode() + "  s2->" + s2.hashCode());

        //输出set
        System.out.println(set);
    }

    private static class Student {
        String name;
        int age;

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

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return age == student.age &&
                    Objects.equals(name, student.name);
        }
    }
}

输出结果

Student{name='jojo', age=18}
Student{name='jojo', age=18}
s1.equals(s2)的结果为：true
哈希值为：s1->2051450519  s2->99747242
[Student{name='jojo', age=18}, Student{name='jojo', age=18}]

结果分析

equals() 返回 true

哈希值不一致

重写了equals()之后，HashSet依然将s1和s2都存进去了。

哈希值不一致，很明显，从源码看的话，依然跟情况1一模一样，

我们看源码：

不看了，跟情况一的一样，忘了的往上翻翻。

存储示意图：

也是可怜的小猪猪，哈希值不同，就天各一方。

3.只重写hashCode()

例子

public class MyClass {

    public static void main(String[] args) {
        //Student对象
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("jojo", 18);

        //HashSet对象
        HashSet set = new HashSet();
        set.add(s1);
        set.add(s2);

        //输出两个对象
        System.out.println(s1);
        System.out.println(s2);

        //输出equals
        System.out.println("s1.equals(s2)的结果为：" + s1.equals(s2));

        //输出哈希值
        System.out.println("哈希值为：s1->" + s1.hashCode() + "  s2->" + s2.hashCode());

        //输出set
        System.out.println(set);
    }

    private static class Student {
        String name;
        int age;

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

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }

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

输出结果

Student{name='jojo', age=18}
Student{name='jojo', age=18}
s1.equals(s2)的结果为：false
哈希值为：s1->101306313  s2->101306313
[Student{name='jojo', age=18}, Student{name='jojo', age=18}]

结果分析

equals() 返回 false

哈希值一致

这次我们只重写hashCode()，没有重写equals()。

此时哈希值一致了，但是依然存储了两个元素，让我们康康怎么回事。

我们看源码：

当s1添加进来时，也是跟情况一所说的一样，tab数组初始化，放入tab[i]。

重点是s2的添加，s2的添加部分源码为

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // tab数组不为空 跳过
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 此时重写了hashCode()，得到的哈希值跟元素内容相关，所以s1和s2的哈希值一致
        // 再根据哈希值算出来的hash也一致，所以i也一致
        // 按理说应该插入tab[i]，但之前s1已经存在tab[i]了，所以就哈希冲突了，跳过执行
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 哈希冲突走这里
            Node<K,V> e; K k;
            // 再次判断元素的hash和equals()以便确认是同一元素
            // 但因为equals()没有重写，所以认为s1和s2是两个元素
            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) {
                    // 获取到tab[i]上的链表结尾
                    if ((e = p.next) == null) {
                        // 链表尾指向新节点，也就是指向s2
                        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) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

所以此时s2也被添加进去了。

存储示意图：

我们可以看到HashMap用了拉链法存储s1和s2。

从这我们可以得知putVal()不仅涉及了元素的哈希值，即hashCode()，还涉及到了equals()。

所以为什么上面只重写hashCode()之后HashSet还能添加s1和s2，就是因为equals()没有重写。

导致了虽然哈希值相同，但equals()不同，所以认为s1和s2是索引相同，内容不同的元素。

就将它们都插入了，并且插入的位置是同一个索引，也就是“拉链法”。

所以综上所述，我们可以知道，对于这些哈希结构的东西，

它们判断元素重复是先判断哈希值然后再判断equals()的。

也就是说

先判断哈希值，如果哈希值相等，内容不一定等，此时继续判断equals()。

如果哈希值不等，那么此时内容一定不等，就不用再判断equals()了，直接操作。

4.两个都重写

例子

public class MyClass {

    public static void main(String[] args) {
        //Student对象
        Student s1 = new Student("jojo", 18);
        Student s2 = new Student("jojo", 18);

        //HashSet对象
        HashSet set = new HashSet();
        set.add(s1);
        set.add(s2);

        //输出两个对象
        System.out.println(s1);
        System.out.println(s2);

        //输出equals
        System.out.println("s1.equals(s2)的结果为：" + s1.equals(s2));

        //输出哈希值
        System.out.println("哈希值为：s1->" + s1.hashCode() + "  s2->" + s2.hashCode());

        //输出set
        System.out.println(set);
    }

    private static class Student {
        String name;
        int age;

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

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return age == student.age &&
                    Objects.equals(name, student.name);
        }

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

输出结果

Student{name='jojo', age=18}
Student{name='jojo', age=18}
s1.equals(s2)的结果为：true
哈希值为：s1->101306313  s2->101306313
[Student{name='jojo', age=18}]

结果分析

equals() 返回 true

哈希值一致

重写了两个方法后，equals()返回了true，哈希值也因为内容一样而一样，

更重要的是，HashSet只插入了一个元素。

我们看源码：

s1添加依然不用看了，都是一样的，重点依然是s2的添加。

s2的添加前面跟第三种情况的一样，都是因为hash导致索引i相同，

然后需要用equals()加以判断元素是否相同。

此时部分源码为

        // 因为重写有hashCode()，所以hash相同导致i相同
        // 需要处理哈希冲突
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 通过hash和equals()判断元素相同
            // 而因为equals()重写过了，所以通过
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 通过了 把p赋给e
                e = p;
           /******省略********/
            }
            // 此时e不为null，它等于p，p的key就是s1，
            // 在Hashset中，因为只有key，所以可将 <key,value> 看成 <key>
            // 所以此时可以认为e是s1
            if (e != null) { 
                // 记录旧值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // 记录新值
                    e.value = value;
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }

从上面分析可以看出，当通过hash和equals()判断出s1和s2是同一个元素时，

直接就把p（也就是s1）赋给了e，然后替换了一下value部分，完全不管key部分的s2了。

存储示意图：

所以可以得知，元素相同时，

在HashMap中，会记录旧value，更新value后返回旧value。

但是在HashSet中，因为只有key部分没有value部分，所以返回的是一个空对象，

为什么是空对象呢。有代码为证。

// 这是HashSet的add，调用了HashMap的put()
// put(K key,V value)是插入键值对
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

// HashSet传了一个key为我们add的元素，而value部分用的是它自己的东西

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

//官方解释说这个PRESENT就是一个虚拟值，说白了就是应付value用的