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

list的转map的另一种猜想

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

当然，使用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()的注意事项

我们设计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不相同，两个对象显然不相同。猜想是正确的。

结论

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

搜索Java知音公众号，回复“后端面试”，送你一份Java面试题宝典.pdf

我们没法自定义过滤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()过滤掉，最终留下的都是不重复的。Java面试宝典PDF完整版

最终实现的程序如下

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,793评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,567评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,342评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,825评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,814评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,680评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,033评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,687评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,175评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,668评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,775评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,419评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,020评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,206评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,092评论 2赞 351
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,510评论 2赞 343