一次List对象去重失败，引发对Java8中distinct()的思考

prtyaa
prtyaa 2023-12-31 22:31:12 62285
分类专栏： 资讯

list的转map的另一种猜想

Java8使用lambda表达式进行函数式编程可以对集合进行非常方便的操作。一个比较常见的操作是将list转换成map，一般使用Collectors的toMap()方法进行转换。一个比较常见的问题是当list中含有相同元素的时候，如果不指定取哪一个，则会抛出异常。因此，这个指定是必须的。

当然，使用toMap()的另一个重载方法，可以直接指定。这里，我们想讨论的是另一种方法：在进行转map的操作之前，能不能使用distinct()先把list的重复元素过滤掉，然后转map的时候就不用考虑重复元素的问题了。

使用distinct()给list去重

直接使用distinct()，失败

package example.mystream;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class ListToMap {

    @AllArgsConstructor
    @NoArgsConstructor
    @ToString
    private static class VideoInfo {
        @Getter
        String id;
        int width;
        int height;
    }

    public static void main(String [] args) {
        List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
                new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));

        // preferred: handle duplicated data when toMap()
        Map<String, VideoInfo> id2VideoInfo = list.stream().collect(
                Collectors.toMap(VideoInfo::getId, x -> x,
                        (oldValue, newValue) -> newValue)
        );

        System.out.println("No Duplicated1: ");
        id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));

        // handle duplicated data using distinct(), before toMap()
        Map<String, VideoInfo> id2VideoInfo2 = list.stream().distinct().collect(
                Collectors.toMap(VideoInfo::getId, x -> x)
        );

        System.out.println("No Duplicated2: ");
        id2VideoInfo2.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
    }
}

list里总共有三个元素，其中有两个我们认为是重复的。第一种转换是使用toMap()直接指定了对重复key的处理情况，因此可以正常转换成map。而第二种转换是想先对list进行去重，然后再转换成map，结果还是失败了，抛出了IllegalStateException，所以distinct()应该是失败了。

No Duplicated1: 
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
Exception in thread "main" java.lang.IllegalStateException: Duplicate key ListToMap.VideoInfo(id=123, width=1, height=2)
    at java.util.stream.Collectors.lambda$throwingMerger$0(Collectors.java:133)
    at java.util.HashMap.merge(HashMap.java:1253)
    at java.util.stream.Collectors.lambda$toMap$58(Collectors.java:1320)
    at java.util.stream.ReduceOps$3ReducingSink.accept(ReduceOps.java:169)
    at java.util.stream.DistinctOps$1$2.accept(DistinctOps.java:175)
    at java.util.Spliterators$ArraySpliterator.forEachRemaining(Spliterators.java:948)
    at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481)
    at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
    at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708)
    at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
    at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499)
    at example.mystream.ListToMap.main(ListToMap.java:79)

原因：distinct()依赖于equals()

查看distinct()的API，可以看到如下介绍：

Returns a stream consisting of the distinct elements (according to {@link Object#equals(Object)}) of this stream.

显然，distinct()对对象进行去重时，是根据对象的equals()方法去处理的。如果我们的VideoInfo类不overrride超类Object的equals()方法，就会使用Object的。

但是Object的equals()方法只有在两个对象完全相同时才返回true。而我们想要的效果是只要VideoInfo的id/width/height均相同，就认为两个videoInfo对象是同一个。所以我们比如重写属于videoInfo的equals()方法。相关文章：一次性搞清楚equals和hashCode

重写equals()的注意事项

我们设计VideoInfo的equals()如下：

@Override
public boolean equals(Object obj) {
    if (!(obj instanceof VideoInfo)) {
        return false;
    }
    VideoInfo vi = (VideoInfo) obj;
    return this.id.equals(vi.id)
          && this.width == vi.width
          && this.height == vi.height;
}

这样一来，只要两个videoInfo对象的三个属性都相同，这两个对象就相同了。欢天喜地去运行程序，依旧失败！why？

《Effective Java》是本好书，连Java之父James Gosling都说，这是一本连他都需要的Java教程。在这本书中，作者指出，如果重写了一个类的equals()方法，那么就必须一起重写它的hashCode()方法！必须！没有商量的余地！

必须使得重写后的equals()满足如下条件：

  • 根据equals()进行比较，相等的两个对象，hashCode()的值也必须相同；
  • 根据equals()进行比较，不相等的两个对象，hashCode()的值可以相同，也可以不同；

因为这是Java的规定，违背这些规定将导致Java程序运行不再正常。

具体更多的细节，建议大家读读原书，必定获益匪浅。强烈推荐！

最终，我按照神书的指导设计VideoInfo的hashCode()方法如下：

@Override
public int hashCode() {
   int n = 31;
   n = n * 31 + this.id.hashCode();
   n = n * 31 + this.height;
   n = n * 31 + this.width;
   return n;
}

终于，distinct()成功过滤了list中的重复元素，此时使用两种toMap()将list转换成map都是没问题的：

No Duplicated1: 
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
No Duplicated2: 
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>

引申

既然说distinct()是调用equals()进行比较的，那按照我的理解，list的3个元素至少需要比较3次吧。那是不是就调用了3次equals()呢？

在equals()中加入一句打印，这样就可以知道了。加后的equals()如下：

@Override 
public boolean equals(Object obj) {
    if (! (obj instanceof VideoInfo)) {
        return false;
    }
    VideoInfo vi = (VideoInfo) obj;

    System.out.println("<===> Invoke equals() ==> " + this.toString() + " vs. " + vi.toString());

    return this.id.equals(vi.id) && this.width == vi.width && this.height == vi.height;
}

结果：

No Duplicated1: 
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
<===> Invoke equals() ==> ListToMap.VideoInfo(id=123, width=1, height=2) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
No Duplicated2: 
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>

结果发现才调用了一次equals()。为什么不是3次呢？仔细想想，根据hashCode()进行比较，hashCode()相同的情况就一次，就是list的第一个元素和第三个元素（都是VideoInfo(id=123, width=1, height=2)）会出现hashCode()相同的情况。

所以我们是不是可以这么猜想：只有当hashCode()返回的hashCode相同的时候，才会调用equals()进行更进一步的判断。如果连hashCode()返回的hashCode都不同，那么可以认为这两个对象一定就是不同的了！

验证猜想：

更改hashCode()如下：

@Override
public int hashCode() {
   return 1;
}

这样一来，所有的对象的hashCode()返回值都是相同的。当然，这样搞是符合Java规范的，因为Java只规定equals()相同的对象的hashCode必须相同，但是不同的对象的hashCode未必会不同。

结果：

No Duplicated1: 
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
<===> Invoke equals() ==> ListToMap.VideoInfo(id=456, width=4, height=5) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
<===> Invoke equals() ==> ListToMap.VideoInfo(id=456, width=4, height=5) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
<===> Invoke equals() ==> ListToMap.VideoInfo(id=123, width=1, height=2) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
No Duplicated2: 
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>

果然，equals()调用了三次！看来的确只有hashCode相同的时候才会调用equal()进一步判断两个对象究竟是否相同；如果hashCode不相同，两个对象显然不相同。猜想是正确的。

结论

  1. list转map推荐使用toMap()，并且无论是否会出现重复的问题，都要指定重复后的取舍规则，不费功夫但受益无穷；
  2. 对一个自定义的class使用distinct()，切记覆写equals()方法；
  3. 覆写equals()，一定要覆写hashCode()；
  4. 虽然设计出一个hashCode()可以简单地让其return 1，这样并不会违反Java规定，但是这样做会导致很多恶果。比如将这样的对象存入hashMap的时候，所有的对象的hashCode都相同，最终所有对象都存储在hashMap的同一个桶中，直接将hashMap恶化成了一个链表。从而O(1)的复杂度被整成了O(n)的，性能自然大大下降。
  5. 好书是程序猿进步的阶梯。——高尔基。比如《Effecctive Java》。

最终参考程序：

package example.mystream;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class ListToMap {

    @AllArgsConstructor
    @NoArgsConstructor
    @ToString
    private static class VideoInfo {
        @Getter
        String id;
        int width;
        int height;

        public static void main(String [] args) {
            System.out.println(new VideoInfo("123", 1, 2).equals(new VideoInfo("123", 1, 2)));
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof VideoInfo)) {
                return false;
            }
            VideoInfo vi = (VideoInfo) obj;
            return this.id.equals(vi.id)
                    && this.width == vi.width
                    && this.height == vi.height;
        }

        /**
         * If equals() is override, hashCode() must be override, too.
         * 1. if a equals b, they must have the same hashCode;
         * 2. if a doesn't equals b, they may have the same hashCode;
         * 3. hashCode written in this way can be affected by sequence of the fields;
         * 3. 2^5 - 1 = 31. So 31 will be faster when do the multiplication,
         *      because it can be replaced by bit-shifting: 31 * i = (i << 5) - i.
         * @return
         */
        @Override
        public int hashCode() {
            int n = 31;
            n = n * 31 + this.id.hashCode();
            n = n * 31 + this.height;
            n = n * 31 + this.width;
            return n;
        }
    }

    public static void main(String [] args) {
        List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
                new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));

        // preferred: handle duplicated data when toMap()
        Map<String, VideoInfo> id2VideoInfo = list.stream().collect(
                Collectors.toMap(VideoInfo::getId, x -> x,
                        (oldValue, newValue) -> newValue)
        );

        System.out.println("No Duplicated1: ");
        id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));

        // handle duplicated data using distinct(), before toMap()
        // Note that distinct() relies on equals() in the object
        // if you override equals(), hashCode() must be override together
        Map<String, VideoInfo> id2VideoInfo2 = list.stream().distinct().collect(
                Collectors.toMap(VideoInfo::getId, x -> x)
        );

        System.out.println("No Duplicated2: ");
        id2VideoInfo2.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
    }
}

再拓展

假设类是别人的，不能修改

以上，VideoInfo使我们自己写的类，我们可以往里添加equals()和hashCode()方法。如果VideoInfo是我们引用的依赖中的一个类，我们无权对其进行修改，那么是不是就没办法使用distinct()按照某些元素是否相同，对对象进行自定义的过滤了呢？

使用wrapper

在stackoverflow的一个回答上，我们可以找到一个可行的方法：使用wrapper。

假设在一个依赖中（我们无权修改该类），VideoInfo定义如下：

@AllArgsConstructor
@NoArgsConstructor
@ToString
public class VideoInfo {
    @Getter
    String id;
    int width;
    int height;
}

使用刚刚的wrapper思路，写程序如下（当然，为了程序的可运行性，还是把VideoInfo放进来了，假设它就是不能修改的，不能为其添加任何方法）：

package example.mystream;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class DistinctByWrapper {

    private static class VideoInfoWrapper {

        private final VideoInfo videoInfo;

        public VideoInfoWrapper(VideoInfo videoInfo) {
            this.videoInfo = videoInfo;
        }

        public VideoInfo unwrap() {
            return videoInfo;
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof VideoInfo)) {
                return false;
            }
            VideoInfo vi = (VideoInfo) obj;
            return videoInfo.id.equals(vi.id)
                    && videoInfo.width == vi.width
                    && videoInfo.height == vi.height;
        }

        @Override
        public int hashCode() {
            int n = 31;
            n = n * 31 + videoInfo.id.hashCode();
            n = n * 31 + videoInfo.height;
            n = n * 31 + videoInfo.width;
            return n;
        }
    }

    public static void main(String [] args) {
        List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
                new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));

        // VideoInfo --map()--> VideoInfoWrapper ----> distinct(): VideoInfoWrapper --map()--> VideoInfo
        Map<String, VideoInfo> id2VideoInfo = list.stream()
                .map(VideoInfoWrapper::new).distinct().map(VideoInfoWrapper::unwrap)
                .collect(
                Collectors.toMap(VideoInfo::getId, x -> x,
                        (oldValue, newValue) -> newValue)
        );

        id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
    }

}

/**
 * Assume that VideoInfo is a class that we can't modify
 */
@AllArgsConstructor
@NoArgsConstructor
@ToString
class VideoInfo {
    @Getter
    String id;
    int width;
    int height;
}

整个wrapper的思路无非就是构造另一个类VideoInfoWrapper，把hashCode()和equals()添加到wrapper中，这样便可以按照自定义规则对wrapper对象进行自定义的过滤。

我们没法自定义过滤VideoInfo，但是我们可以自定义过滤VideoInfoWrapper啊！

之后要做的，就是将VideoInfo全部转化为VideoInfoWrapper，然后过滤掉某些VideoInfoWrapper，再将剩下的VideoInfoWrapper转回VideoInfo，以此达到过滤VideoInfo的目的。很巧妙！

使用“filter() + 自定义函数”取代distinct()

另一种更精妙的实现方式是自定义一个函数：

    private static <T> Predicate<T> distinctByKey(Function<? super T, Object> keyExtractor) {
        Map<Object, Boolean> map = new ConcurrentHashMap<>();
        return t -> map.putIfAbsent(keyExtractor.apply(t), Boolean.TRUE) == null;
    }

（输入元素的类型是T及其父类，keyExtracctor是映射函数，返回Object，整个传入的函数的功能应该是提取key的。distinctByKey函数返回的是Predicate函数，类型为T。）

这个函数传入一个函数（lambda），对传入的对象提取key，然后尝试将key放入concurrentHashMap，如果能放进去，说明此key之前没出现过，函数返回false；如果不能放进去，说明这个key和之前的某个key重复了，函数返回true。

这个函数最终作为filter()函数的入参。根据Java API可知filter(func)过滤的规则为：如果func为true，则过滤，否则不过滤。因此，通过“filter() + 自定义的函数”，凡是重复的key都返回true，并被filter()过滤掉，最终留下的都是不重复的。

最终实现的程序如下

package example.mystream;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;


public class DistinctByFilterAndLambda {

    public static void main(String[] args) {
        List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
                new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));

        // Get distinct only
        Map<String, VideoInfo> id2VideoInfo = list.stream().filter(distinctByKey(vi -> vi.getId())).collect(
                Collectors.toMap(VideoInfo::getId, x -> x,
                        (oldValue, newValue) -> newValue)
        );

        id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
    }

    /**
     * If a key could not be put into ConcurrentHashMap, that means the key is duplicated
     * @param keyExtractor a mapping function to produce keys
     * @param <T> the type of the input elements
     * @return true if key is duplicated; else return false
     */
    private static <T> Predicate<T> distinctByKey(Function<? super T, Object> keyExtractor) {
        Map<Object, Boolean> map = new ConcurrentHashMap<>();
        return t -> map.putIfAbsent(keyExtractor.apply(t), Boolean.TRUE) == null;
    }
}

/**
 * Assume that VideoInfo is a class that we can't modify
 */
@AllArgsConstructor
@NoArgsConstructor
@ToString
class VideoInfo {
    @Getter
    String id;
    int width;
    int height;
}

网站声明：如果转载，请联系本站管理员。否则一切后果自行承担。

本文链接：https://www.xckfsq.com/news/show.html?id=33399
赞同 0
评论 0 条

相关文章

  • 如何将文档中插入的对象置于底层？ 2022-09-29 60735 浏览

    使用WPS Office打开文档，选中需要操作的对象。依次点击“页面布局”--->“下移一层”--->“置于底层”即可。

  • [网页编程]-12 JavaScript BOM和DOM对象 2023-12-27 64130 浏览

    简单的来说,整个浏览器的结构就是BOM这包括着浏览器的全部而Dom就是中间我们浏览内容的那一块Bom包含Dom●什么是BOM●BOM是Browser0bjectModel的简写，即浏览器对象模型。●BOM由一系列对象组成，是访问、控制、修改浏览器的属性的方法●BOM没有统一的标准(每种客户端都可以自定标准)。●BOM的顶层是window对象●什么是DOM●DOM;是DocumentObjectMo

  • [网页编程]-08 JavaScript 内置对象 2023-12-27 63891 浏览

    JavaScript中内置里几个对象,我们就挑常用的来学习就好JavaScript教程导读_w3cschool​www.w3cschool.cn/javascript/js-tutorial.html

  • 如何快速删除表格对象？ 2022-09-29 65134 浏览

    使用WPS Office打开表格，选择需要处理的单元格区域。依次点击“特色功能”--->“智能工具箱”--->“单元格处理”。选择“删除其他”--->“删除对象”，在弹出框勾选需要删

  • [MyBatis]-17 多表关联查询_集合对象_关联方式实现 2023-12-27 66892 浏览

    思路整理一下之前一直做的都是多对一的查询多:学生一:班级通过查到学生后在去查询班级现在倒过来,做1对多的查询,一个班级多个学生那怎么处理这个多呢,实际上就是吧所有的学生封装进一个集合里表现出来,最直观的就是在class的实体类中添加一个学生类型的集合思路:在pojo里的Class类的属性中加入Student的集合,将查到的Student信息封装进Class类里面pojo层Clazz.classpu

  • 如何不打印文档中的图形对象？ 2022-09-29 66939 浏览

    使用WPS Office打开文档，点击左上角“打印”或使用快捷键“Ctrl+P”打开打印功能。在“打印”的弹出框中点击“选项”，取消勾选“图形对象”后确认，再重新操作即可。

  • Java：new一个对象的过程中发生了什么？ 2024-01-01 65442 浏览

    java在new一个对象的时候，会先查看对象所属的类有没有被加载到内存，如果没有的话，就会先通过类的全限定名来加载。加载并初始化类完成后，再进行对象的创建工作。我们先假设是第一次使用该类，这样的话new一个对象就可以分为两个过程：加载并初始化类和创建对象。一、类加载过程（第一次使用该类）java是使用双亲委派模型来进行类的加载的，所以在描述类加载过程前，我们先看一下它的工作过程：双亲委托模型的工作

  • 如何隐藏/显示文档中的对象？ 2022-09-29 66203 浏览

    使用WPS Office打开文档，依次点击“开始”--->“选择”--->“选择窗格”。在页面右侧栏中可查看文档中的对象是否有插入的图、形状等。点击对象后方眼睛图标可将其隐藏或显示。（注意

  • 如何在幻灯片中插入对象文件？ 2022-09-29 64426 浏览

    使用WPS Office打开幻灯片，依次点击“插入”--->“对象”。根据需要选择插入的文件后，点击“确定”即可。

  • 如何查看PPT中的对象？ 2022-09-29 63592 浏览

    使用WPS Office打开PPT,依次点击“绘图工具”--->“选择窗格”。即可在右侧栏显示文档中的对象,点击对象后的眼睛图标可隐藏或显示对象。

prtyaa
prtyaaL0
粉丝 1 发表 2554 + 关注 私信
上周热门
银河麒麟添加网络打印机时，出现“client-error-not-possible”错误提示  1327
银河麒麟打印带有图像的文档时出错  1239
银河麒麟添加打印机时，出现“server-error-internal-error”  1026
统信桌面专业版【如何查询系统安装时间】  954
统信操作系统各版本介绍  947
统信桌面专业版【全盘安装UOS系统】介绍  906
麒麟系统也能完整体验微信啦！  892
统信【启动盘制作工具】使用介绍  502
统信桌面专业版【一个U盘做多个系统启动盘】的方法  444
信刻全自动档案蓝光光盘检测一体机  389
本周热议
我的信创开放社区兼职赚钱历程 40
今天你签到了吗？ 27
信创开放社区邀请他人注册的具体步骤如下 15
如何玩转信创开放社区—从小白进阶到专家 15
方德桌面操作系统 14
我有15积分有什么用? 13
用抖音玩法闯信创开放社区——用平台宣传企业产品服务 13
如何让你先人一步获得悬赏问题信息？（创作者必看） 12
2024中国信创产业发展大会暨中国信息科技创新与应用博览会 9
中央国家机关政府采购中心：应当将CPU、操作系统符合安全可靠测评要求纳入采购需求 8
热门标签更多

添加我为好友，拉您入交流群！

请使用微信扫一扫!