问题
当下互联网技术成熟, 越来越多的趋向去中心化, 分布式, 流计算, 使得很多以前在数据库侧做的事情放到了 Java 端. 今天有人问道, 如果数据库字段没有索引, 那么应该如何根据该字段去重? 大家都一致认为用 Java 来做, 但怎么做呢?
解答
忽然想起以前写过 list 去重的文章, 找出来一看. 做法就是将 list 中对象的 hashcode 和 equals 方法重写, 然后丢到 HashSet 里, 然后取出来. 这是最初刚学 Java 的时候像被字典一样背写出来的答案. 就比如面试, 面过号称做了 3 年 Java 的人, 问 Set 和 HashMap 的区别可以背出来, 问如何实现就不知道了. 也就是说, 初学者只背特性. 但真正在项目中使用的时候你需要确保一下是不是真的这样. 因为背书没用, 只能相信结果. 你需要知道 HashSet 如何帮我做到去重了. 换个思路, 不用 HashSet 可以去重吗? 最简单, 最直接的办法不就是每次都拿着和历史数据比较, 都不相同则插入队尾. 而 HashSet 只是加速了这个过程而已.
首先, 给出我们要排序的对象 User
- @Data
- @Builder
- @AllArgsConstructor
- public class User {
- private Integer id;
- private String name;
- }
- List<User> users = Lists.newArrayList(
- new User(1, "a"),
- new User(1, "b"),
- new User(2, "b"),
- new User(1, "a"));
目标是取出 id 不重复的 user, 为了防止扯皮, 给个规则, 只要任意取出 id 唯一的数据即可, 不用拘泥 id 相同时算哪个.
用最直观的办法
这个办法就是用一个空 list 存放遍历后的数据.
- @Test
- public void dis1() {
- List<User> result = new LinkedList<>();
- for (User user : users) {
- boolean b = result.stream().anyMatch(u -> u.getId().equals(user.getId()));
- if (!b) {
- result.add(user);
- }
- }
- System.out.println(result);
- }
用 HashSet
背过特性的都知道 HashSet 可以去重, 那么是如何去重的呢? 再深入一点的背过根据 hashcode 和 equals 方法. 那么如何根据这两个做到的呢? 没有看过源码的人是无法继续的, 面试也就到此结束了.
事实上, HashSet 是由 HashMap 来实现的 (没有看过源码的时候曾经一直直观的以为 HashMap 的 key 是 HashSet 来实现的, 恰恰相反). 这里不展开叙述, 只要看 HashSet 的构造方法和 add 方法就能理解了.
public HashSet() {
- map = new HashMap<>();
- }
- /**
- * 显然, 存在则返回 false, 不存在的返回 true
- */
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
那么, 由此也可以看出 HashSet 的去重复就是根据 HashMap 实现的, 而 HashMap 的实现又完全依赖于 hashcode 和 equals 方法. 这下就彻底打通了, 想用 HashSet 就必须看好自己的这两个方法.
在本题目中, 要根据 id 去重, 那么, 我们的比较依据就是 id 了. 修改如下:
- @Override
- public boolean equals(Object o) {
- if (this == o) {
- return true;
- }
- if (o == null || getClass() != o.getClass()) {
- return false;
- }
- User user = (User) o;
- return Objects.equals(id, user.id);
- }
- @Override
- public int hashCode() {
- return Objects.hash(id);
- }
- //hashcode
- result = 31 * result + (element == null ? 0 : element.hashCode());
其中, Objects 调用 Arrays 的 hashcode, 内容如上述所示. 乘以 31 等于 x<<5-x.
最终实现如下:
- @Test
- public void dis2() {
- Set<User> result = new HashSet<>(users);
- System.out.println(result);
- }
使用 Java 的 Stream 去重
回到最初的问题, 之所以提这个问题是因为想要将数据库侧去重拿到 Java 端, 那么数据量可能比较大, 比如 10w 条. 对于大数据, 采用 Stream 相关函数是最简单的了. 正好 Stream 也提供了 distinct 函数. 那么应该怎么用呢?
users.parallelStream().distinct().forEach(System.out::println);
没看到用 lambda 当作参数, 也就是没有提供自定义条件. 幸好 Javadoc 标注了去重标准:
Returns a stream consisting of the distinct elements
(according to {@link Object#equals(Object)}) of this stream.
我们知道, 也必须背过这样一个准则: equals 返回 true 的时候, hashcode 的返回值必须相同. 这个在背的时候略微有些逻辑混乱, 但只要了解了 HashMap 的实现方式就不会觉得拗口了. HashMap 先根据 hashcode 方法定位, 再比较 equals 方法.
所以, 要使用 distinct 来实现去重, 必须重写 hashcode 和 equals 方法, 除非你使用默认的.
那么, 究竟为啥要这么做? 点进去看一眼实现.
- <P_IN> Node<T> reduce(PipelineHelper<T> helper, Spliterator<P_IN> spliterator) {
- // If the stream is SORTED then it should also be ORDERED so the following will also
- // preserve the sort order
- TerminalOp<T, LinkedHashSet<T>> reduceOp
- = ReduceOps.<T, LinkedHashSet<T>>makeRef(LinkedHashSet::new, LinkedHashSet::add,
- LinkedHashSet::addAll);
- return Nodes.node(reduceOp.evaluateParallel(helper, spliterator));
- }
内部是用 reduce 实现的啊, 想到 reduce, 瞬间想到一种自己实现 distinctBykey 的方法. 我只要用 reduce, 计算部分就是把 Stream 的元素拿出来和我自己内置的一个 HashMap 比较, 有则跳过, 没有则放进去. 其实, 思路还是最开始的那个最直白的方法.
- @Test
- public void dis3() {
- users.parallelStream().filter(distinctByKey(User::getId))
- .forEach(System.out::println);
- }
- public static <T> Predicate<T> distinctByKey(Function<? super T, ?> keyExtractor) {
- Set<Object> seen = ConcurrentHashMap.newKeySet();
- return t -> seen.add(keyExtractor.apply(t));
- }
当然, 如果是并行 stream, 则取出来的不一定是第一个, 而是随机的.
上述方法是至今发现最好的, 无侵入性的. 但如果非要用 distinct. 只能像 HashSet 那个方法一样重写 hashcode 和 equals.
小结
会不会用这些东西, 你只能去自己练习过, 不然到了真正要用的时候很难一下子就拿出来, 不然就冒险用. 而若真的想大胆使用, 了解规则和实现原理也是必须的. 比如, LinkedHashSet 和 HashSet 的实现有何不同.
附上贼简单的 LinkedHashSet 源码:
- public class LinkedHashSet<E>
- extends HashSet<E>
- implements Set<E>, Cloneable, java.io.Serializable {
- private static final long serialVersionUID = -2851667679971038690L;
- public LinkedHashSet(int initialCapacity, float loadFactor) {
- super(initialCapacity, loadFactor, true);
- }
- public LinkedHashSet(int initialCapacity) {
- super(initialCapacity, .75f, true);
- }
- public LinkedHashSet() {
- super(16, .75f, true);
- }
- public LinkedHashSet(Collection<? extends E> c) {
- super(Math.max(2*c.size(), 11), .75f, true);
- addAll(c);
- }
- @Override
- public Spliterator<E> spliterator() {
- return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
- }
- }
来源: https://www.cnblogs.com/woshimrf/p/java-list-distinct.html