乐趣区

关于前端:List对象去重失败引发了我对Java8中distinct的思考

jiezi

list 的转 map 的另一种猜测

Java8 应用 lambda 表达式进行函数式编程能够对汇合进行十分不便的操作。一个比拟常见的操作是将 list 转换成 map，个别应用 Collectors 的 toMap() 办法进行转换。一个比拟常见的问题是当 list 中含有雷同元素的时候，如果不指定取哪一个，则会抛出异样。因而，这个指定是必须的。

当然，应用 toMap() 的另一个重载办法，能够间接指定。这里，咱们想探讨的是另一种办法：在进行转 map 的操作之前，能不能应用 distinct() 先把 list 的反复元素过滤掉，而后转 map 的时候就不必思考反复元素的问题了。
《2020 最新 Java 根底精讲视频教程和学习路线！》

应用 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 不雷同，两个对象显然不雷同。猜测是正确的。

论断

  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;
}
退出移动版