从对集合数据去重到Distinct源码分析【金沙官网线

今天在写代码的时候要对数据进行去重,正打算使用Distinct方法的时候,发现这个用了这么久的东西,竟然不知道它是怎么实现的,于是就有了这篇文章.
使用的.net core2.0

本文为原创文章,如需转载请注明出处,谢谢!

1.需求

假如我们有这样一个类

    public class Model
    {
        public int Code { get; set; }
        public int No { get; set; }
        public override string ToString()
        {
            return "No:" + No + ",Code:" + Code;
        }
    }

还有这样一组数据

        public static IEnumerable<Model> GetList()
        {
            return new List<Model>()
            {
                new Model(){No = 1,Code = 1},
                new Model(){No = 1,Code = 2},
                new Model(){No = 7,Code = 1},
                new Model(){No = 11,Code = 1},
                new Model(){No = 55,Code = 1},
                new Model(){No = 11,Code = 1},//重复
                new Model(){No = 6,Code = 7},
                new Model(){No = 1,Code = 1},
                new Model(){No = 6,Code = 7},//重复
            };
        }

我们要把集合中重复的数据去掉,对的就这么简单个需求,工作中可不会有这么简单的需求.

概述

本文将围绕以下五点进行说明

1.equals() 和 == 的作用以及应用
2.hashCode() 的作用及应用
3.hashCode() 和 equals() 的联系
4.HashSet 和 HashMap 的特性
5.Hash 冲突是什么以及如何解决

2.在刚学编程的时候我们可能这样写的

在很久以前一直使用这种简单粗暴的方法解决重复问题

        /// <summary>
        /// 双重循环去重
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        public static IEnumerable<Model> MyDistinct(IEnumerable<Model> list)
        {
            var result = new List<Model>();
            foreach (var item in list)
            {
                //标记
                var flag = true;
                foreach (var item2 in result)
                {
                    //已经存在的标记为false
                    if (item2.Code == item.Code && item2.No == item.No)
                    {
                        flag = false;
                    }
                }

                if (flag)
                {
                    result.Add(item);
                }
            }

            return result;
        }

一、equals() 和 == 的区别

废话不多说,先举个栗子!

String str1 = new String("abc");
String str2 = new String("abc");
System.out.println(str1.equals(str2));
System.out.println(str1 == str2);

许多 Java 基础笔试题中都会出现类似的题目,其实就是在考察是否理解 equals() 和 == 的本质区别。我们先把结论说一下:

1. equals() 方法比较的是两个对象是否相等。

2. == 分为两种情况

  • 比较对象,比较的是对象在内存中的空间地址是否相等
  • 比较基本类型,比较的是值是否相等

解释完原理后,相信上面的题解答就易如反掌了,str1,str2 均为 String 对象。equals() 比较对象,== 比较内存地址,那么问题来了,String 的 equals()方法是怎么比较对象是否相等的呢?那我们就来看看源码吧

public boolean equals(Object anObject) {
        if (this == anObject) { //对象的空间地址相同,说白了就是一个对象!
            return true;
        }
        if (anObject instanceof String) { //地址不同,而且对象是 String
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) { 
            //这里首先看两个 String 长度是否相同,如果不同就不等
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) { //然后逐一比对字符
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }// 所有字符都相等,OK ,String对象就相等了
                return true;
            }
        }
        return false;
    }

经过源码(真理)的一番解释,我们明白了 String 的 equals()的比较逻辑,所以第一个打印为 true。第二个打印比较的是 str1 和 str2 两个引用指向 new 的对象的地址,明显不同,所以为 false。

补充:上面我们分析了 String 的 equals() 方法,那么平时我们使用自定义对象时,equals 又有什么作用呢?我们都知道 Java 中所有的类都继承自 Object,所以我们需要看一下 Object 的 equals() 做了什么。

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

可以看到 equals() 实际上就是用 == 来比较两个对象是否相等。所以我们可以得出如下结论:

  • 如果不重写 equals() ,则 equals() 和 == 效果相同,比较的都是对象内存地址是否相同
  • 重写 equals() ,则根据 equals 内的逻辑判断两个对象是否相同

3.后来认识了Distinct

后来知道了Distinct去重,我们写法变成了这样

   /// <summary>
    /// 比较器
    /// </summary>
    public class ModelEquality : IEqualityComparer<Model>
    {
        public bool Equals(Model x, Model y)
        {
            return x.No == y.No && x.Code == y.Code;
        }

        public int GetHashCode(Model obj)
        {
            return obj.No.GetHashCode() + obj.Code.GetHashCode();
        }
    }
//这样就可以得到去重后的集合
GetList().Distinct(new ModelEquality());

二、equals() 和 hashCode() 的关系

可能一说到 hashCode() 方法,就能开始背课文了:
1、如果两个对象相等(equals() 返回 true),那么它们的 hashCode()一定要相同;
2、如果两个对象hashCode()相等,它们并不一定相等(equals() 不一定返回 true)。

这课文的结论肯定没错,但他们的应用场景究竟是什么呢?我们什么时候会同时用到 equals()和 hashCode() 呢?

在回答这两个问题前,我们先要认清 hashCode()方法的作用是什么,来看下面的解释。

hashCode(),返回对象的哈希码,作用是根据哈希码确定对象在散列表中的位置(单独创建对象或创建数组类型对象时 hashCode() 无作用)。

上面的解释已经很清晰了,那么问题来了,散列表又是啥?再来看看散列表的解释。

散列表本质是数组存储,通过 key-value 的形式存储数据,所以当取 value 的时候,实际上取数组某个位置的元素,并且以 key 的 hashCode 作为 value 在数组中的位置。

我们平时用的 HashSet、HashMap 都是散列表结构,接着我们就以这两个集合为例,详细分析一下 hashCode 在其中的作用。

我们先在此小节简单的说一下 HashSet。面试题常会问,List 和 Set 的区别是什么,又可以背课文了:

1.List 是按 add 顺序存储,且元素可以重复,元素有索引,可以根据元素位置进行 get。
2.Set 存储元素无序,元素不可重复,没有 get 方法,只能通过迭代器获取元素。

我们来逐一解释一下 Set 的特性:

  • 元素无序:上文已经说散列表其实是数组结构,元素的位置是hashCode 决定的,所以元素的顺序我们无法确定。

  • 元素不可重复:这个特性其实由 HashMap 决定,what?你没看错,就是 HashMap,我们看一下 HashSet 的 add 方法就明白了。

    private transient HashMap<E,Object> map;
    
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    

    我们看到其实 Set 中的元素就是 HashMap 中的 KeySet 中的元素,而每个 Key 对应的 Value 都是一个新的 Object 对象,我们又知道 HashMap 中不允许 key 值重复,所以 Set 中的元素也不会重复,至于原理我们在后面一节单讲 HashMap 的时候再说。

  • 没有 get:元素位置本身是由元素的 hashCode 决定,而我们无法事先获取 hashCode 然后再去获取元素,这是一个不可逆的过程。

说了这么多好像有些偏离本节题目了!不好意思,哈哈,马上回到正轨!那么本节开始时背的课文到底说的是什么情况呢,看看我发现的几个好栗子吧!

以下内容均出自 http://www.cnblogs.com/skywang12345/p/3324958.html

 1 import java.util.*;
 2 import java.lang.Comparable;
 3 
 4 /**
 5  * @desc 比较equals() 返回true 以及 返回false时, hashCode()的值。
 6  *
 7  * @author skywang
 8  * @emai kuiwu-wang@163.com
 9  */
10 public class ConflictHashCodeTest1{
11 
12     public static void main(String[] args) {
13         // 新建Person对象,
14         Person p1 = new Person("eee", 100);
15         Person p2 = new Person("eee", 100);
16         Person p3 = new Person("aaa", 200);
17 
18         // 新建HashSet对象 
19         HashSet set = new HashSet();
20         set.add(p1);
21         set.add(p2);
22         set.add(p3);
23 
24         // 比较p1 和 p2, 并打印它们的hashCode()
25         System.out.printf("p1.equals(p2) : %s; p1(%d) p2(%d)n", p1.equals(p2), p1.hashCode(), p2.hashCode());
26         // 打印set
27         System.out.printf("set:%sn", set);
28     }
29 
30     /**
31      * @desc Person类。
32      */
33     private static class Person {
34         int age;
35         String name;
36 
37         public Person(String name, int age) {
38             this.name = name;
39             this.age = age;
40         }
41 
42         public String toString() {
43             return "("+name + ", " +age+")";
44         }
45 
46         /** 
47          * @desc 覆盖equals方法 
48          */  
49         @Override
50         public boolean equals(Object obj){  
51             if(obj == null){  
52                 return false;  
53             }  
54               
55             //如果是同一个对象返回true,反之返回false  
56             if(this == obj){  
57                 return true;  
58             }  
59               
60             //判断是否类型相同  
61             if(this.getClass() != obj.getClass()){  
62                 return false;  
63             }  
64               
65             Person person = (Person)obj;  
66             return name.equals(person.name) && age==person.age;  
67         } 
68     }
69 }

运行结果

p1.equals(p2) : true; p1(1169863946) p2(1690552137)
set:[(eee, 100), (eee, 100), (aaa, 200)]

我们重写了Person的equals()。但是,很奇怪的发现:HashSet中仍然有重复元素:p1 和 p2。为什么会出现这种情况呢?这是因为虽然p1 和 p2的内容相等,但是它们的hashCode()不等;所以,HashSet在添加p1和p2的时候,认为它们不相等。

接下来我们同时重写 equals 和 hashCode。

 1 import java.util.*;
 2 import java.lang.Comparable;
 3 
 4 /**
 5  * @desc 比较equals() 返回true 以及 返回false时, hashCode()的值。
 6  *
 7  * @author skywang
 8  * @emai kuiwu-wang@163.com
 9  */
10 public class ConflictHashCodeTest2{
11 
12     public static void main(String[] args) {
13         // 新建Person对象,
14         Person p1 = new Person("eee", 100);
15         Person p2 = new Person("eee", 100);
16         Person p3 = new Person("aaa", 200);
17         Person p4 = new Person("EEE", 100);
18 
19         // 新建HashSet对象 
20         HashSet set = new HashSet();
21         set.add(p1);
22         set.add(p2);
23         set.add(p3);
24 
25         // 比较p1 和 p2, 并打印它们的hashCode()
26         System.out.printf("p1.equals(p2) : %s; p1(%d) p2(%d)n", p1.equals(p2), p1.hashCode(), p2.hashCode());
27         // 比较p1 和 p4, 并打印它们的hashCode()
28         System.out.printf("p1.equals(p4) : %s; p1(%d) p4(%d)n", p1.equals(p4), p1.hashCode(), p4.hashCode());
29         // 打印set
30         System.out.printf("set:%sn", set);
31     }
32 
33     /**
34      * @desc Person类。
35      */
36     private static class Person {
37         int age;
38         String name;
39 
40         public Person(String name, int age) {
41             this.name = name;
42             this.age = age;
43         }
44 
45         public String toString() {
46             return name + " - " +age;
47         }
48 
49         /** 
50          * @desc重写hashCode 
51          */  
52         @Override
53         public int hashCode(){  
54             int nameHash =  name.toUpperCase().hashCode();
55             return nameHash ^ age;
56         }
57 
58         /** 
59          * @desc 覆盖equals方法 
60          */  
61         @Override
62         public boolean equals(Object obj){  
63             if(obj == null){  
64                 return false;  
65             }  
66               
67             //如果是同一个对象返回true,反之返回false  
68             if(this == obj){  
69                 return true;  
70             }  
71               
72             //判断是否类型相同  
73             if(this.getClass() != obj.getClass()){  
74                 return false;  
75             }  
76               
77             Person person = (Person)obj;  
78             return name.equals(person.name) && age==person.age;  
79         } 
80     }
81 }

运行结果

p1.equals(p2) : true; p1(68545) p2(68545)
p1.equals(p4) : false; p1(68545) p4(68545)
set:[aaa - 200, eee - 100]

这下,equals() 生效了,HashSet中没有重复元素。比较p1和p2,我们发现:它们的 hashCode() 相等,通过equals()比较它们也返回true。所以,p1和p2被视为相等。比较p1和p4,我们发现:虽然它们的hashCode()相等;但是,通过 equals() 比较它们返回false。所以,p1和p4被视为不相等。

小结

  1. 在单独使用对象的时候,hashCode() 对于对象判等没有作用。
  2. 在散列表中使用对象,一定要同时重写 hashCode() 和 equals(),并且要保证 hashCode() 的算法能尽量保证对象的唯一。
  3. HashSet 会先去判断对象的 hashCode 相不相等,如果不相等对象一定不等,如果相等再去通过 equals() 判断对象是否相等。
  4. 本节开始背的课文其实就是针对使用散列表存储对象的时候,我们应该如何设计对象的 equals() 和 hashCode()。

本文由金沙官网线上发布于编程,转载请注明出处:从对集合数据去重到Distinct源码分析【金沙官网线

您可能还会对下面的文章感兴趣: