查看: 1709|回复: 0

[Java学习] Java中对List去重 Stream去重的解决方法

发表于 2018-5-5 09:31:02

问题

当下互联网技术成熟,越来越多的趋向去中心化、分布式、流计算,使得很多以前在数据库侧做的事情放到了Java端。今天有人问道,如果数据库字段没有索引,那么应该如何根据该字段去重?大家都一致认为用Java来做,但怎么做呢?

解答

忽然想起以前写过list去重的文章,找出来一看。做法就是将list中对象的hashcode和equals方法重写,然后丢到HashSet里,然后取出来。这是最初刚学Java的时候像被字典一样背写出来的答案。就比如面试,面过号称做了3年Java的人,问Set和HashMap的区别可以背出来,问如何实现就不知道了。也就是说,初学者只背特性。但真正在项目中使用的时候你需要确保一下是不是真的这样。因为背书没用,只能相信结果。你需要知道HashSet如何帮我做到去重了。换个思路,不用HashSet可以去重吗?最简单,最直接的办法不就是每次都拿着和历史数据比较,都不相同则插入队尾。而HashSet只是加速了这个过程而已。

首先,给出我们要排序的对象User

  1. @Data
  2. @Builder
  3. @AllArgsConstructor
  4. public class User {
  5. private Integer id;
  6. private String name;
  7. }
  8. List<User> users = Lists.newArrayList(
  9. new User(1, "a"),
  10. new User(1, "b"),
  11. new User(2, "b"),
  12. new User(1, "a"));
复制代码

目标是取出id不重复的user,为了防止扯皮,给个规则,只要任意取出id唯一的数据即可,不用拘泥id相同时算哪个。

用最直观的办法

这个办法就是用一个空list存放遍历后的数据。

  1. @Test
  2. public void dis1() {
  3. List<User> result = new LinkedList<>();
  4. for (User user : users) {
  5. boolean b = result.stream().anyMatch(u -> u.getId().equals(user.getId()));
  6. if (!b) {
  7. result.add(user);
  8. }
  9. }
  10. System.out.println(result);
  11. }
复制代码

用HashSet

背过特性的都知道HashSet可以去重,那么是如何去重的呢? 再深入一点的背过根据hashcode和equals方法。那么如何根据这两个做到的呢?没有看过源码的人是无法继续的,面试也就到此结束了。

事实上,HashSet是由HashMap来实现的(没有看过源码的时候曾经一直直观的以为HashMap的key是HashSet来实现的,恰恰相反)。这里不展开叙述,只要看HashSet的构造方法和add方法就能理解了。

  1. public HashSet() {
  2. map = new HashMap<>();
  3. }
  4. /**
  5. * 显然,存在则返回false,不存在的返回true
  6. */
  7. public boolean add(E e) {
  8. return map.put(e, PRESENT)==null;
  9. }
复制代码

那么,由此也可以看出HashSet的去重复就是根据HashMap实现的,而HashMap的实现又完全依赖于hashcode和equals方法。这下就彻底打通了,想用HashSet就必须看好自己的这两个方法。

在本题目中,要根据id去重,那么,我们的比较依据就是id了。修改如下:

  1. @Override
  2. public boolean equals(Object o) {
  3. if (this == o) {
  4. return true;
  5. }
  6. if (o == null || getClass() != o.getClass()) {
  7. return false;
  8. }
  9. User user = (User) o;
  10. return Objects.equals(id, user.id);
  11. }
  12. @Override
  13. public int hashCode() {
  14. return Objects.hash(id);
  15. }
  16. //hashcode
  17. result = 31 * result + (element == null ? 0 : element.hashCode());
复制代码

其中, Objects调用Arrays的hashcode,内容如上述所示。乘以31等于x<<5-x。

最终实现如下:

  1. @Test
  2. public void dis2() {
  3. Set<User> result = new HashSet<>(users);
  4. System.out.println(result);
  5. }
复制代码

使用Java的Stream去重

回到最初的问题,之所以提这个问题是因为想要将数据库侧去重拿到Java端,那么数据量可能比较大,比如10w条。对于大数据,采用Stream相关函数是最简单的了。正好Stream也提供了distinct函数。那么应该怎么用呢?

  1. users.parallelStream().distinct().forEach(System.out::println);
复制代码

没看到用lambda当作参数,也就是没有提供自定义条件。幸好Javadoc标注了去重标准:

  1. Returns a stream consisting of the distinct elements
  2. (according to {[url=home.php?mod=space&uid=17823]@LINK[/url] Object#equals(Object)}) of this stream.
复制代码

我们知道,也必须背过这样一个准则:equals返回true的时候,hashcode的返回值必须相同. 这个在背的时候略微有些逻辑混乱,但只要了解了HashMap的实现方式就不会觉得拗口了。HashMap先根据hashcode方法定位,再比较equals方法。

所以,要使用distinct来实现去重,必须重写hashcode和equals方法,除非你使用默认的。

那么,究竟为啥要这么做?点进去看一眼实现。

  1. <P_IN> Node<T> reduce(PipelineHelper<T> helper, Spliterator<P_IN> spliterator) {
  2. // If the stream is SORTED then it should also be ORDERED so the following will also
  3. // preserve the sort order
  4. TerminalOp<T, LinkedHashSet<T>> reduceOp
  5. = ReduceOps.<T, LinkedHashSet<T>>makeRef(LinkedHashSet::new, LinkedHashSet::add, LinkedHashSet::addAll);
  6. return Nodes.node(reduceOp.evaluateParallel(helper, spliterator));
  7. }
复制代码

内部是用reduce实现的啊,想到reduce,瞬间想到一种自己实现distinctBykey的方法。我只要用reduce,计算部分就是把Stream的元素拿出来和我自己内置的一个HashMap比较,有则跳过,没有则放进去。其实,思路还是最开始的那个最直白的方法。

  1. @Test
  2. public void dis3() {
  3. users.parallelStream().filter(distinctByKey(User::getId))
  4. .forEach(System.out::println);
  5. }
  6. public static <T> Predicate<T> distinctByKey(Function<? super T, ?> keyExtractor) {
  7. Set<Object> seen = ConcurrentHashMap.newKeySet();
  8. return t -> seen.add(keyExtractor.apply(t));
  9. }
复制代码

当然,如果是并行stream,则取出来的不一定是第一个,而是随机的。

上述方法是至今发现最好的,无侵入性的。但如果非要用distinct。只能像HashSet那个方法一样重写hashcode和equals。

小结

会不会用这些东西,你只能去自己练习过,不然到了真正要用的时候很难一下子就拿出来,不然就冒险用。而若真的想大胆使用,了解规则和实现原理也是必须的。比如,LinkedHashSet和HashSet的实现有何不同。

附上贼简单的LinkedHashSet源码:

  1. public class LinkedHashSet<E>
  2. extends HashSet<E>
  3. implements Set<E>, Cloneable, java.io.Serializable {
  4. private static final long serialVersionUID = -2851667679971038690L;
  5. public LinkedHashSet(int initialCapacity, float loadFactor) {
  6. super(initialCapacity, loadFactor, true);
  7. }
  8. public LinkedHashSet(int initialCapacity) {
  9. super(initialCapacity, .75f, true);
  10. }
  11. public LinkedHashSet() {
  12. super(16, .75f, true);
  13. }
  14. public LinkedHashSet(Collection<? extends E> c) {
  15. super(Math.max(2*c.size(), 11), .75f, true);
  16. addAll(c);
  17. }
  18. @Override
  19. public Spliterator<E> spliterator() {
  20. return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
  21. }
  22. }
复制代码

补充:

Java中List集合去除重复数据的方法

1. 循环list中的所有元素然后删除重复

  1. public static List removeDuplicate(List list) {
  2. for ( int i = 0 ; i < list.size() - 1 ; i ++ ) {
  3. for ( int j = list.size() - 1 ; j > i; j -- ) {
  4. if (list.get(j).equals(list.get(i))) {
  5. list.remove(j);
  6. }
  7. }
  8. }
  9. return list;
  10. }
复制代码

2. 通过HashSet踢除重复元素

  1. public static List removeDuplicate(List list) {
  2. HashSet h = new HashSet(list);
  3. list.clear();
  4. list.addAll(h);
  5. return list;
  6. }
复制代码

3. 删除ArrayList中重复元素,保持顺序

  1. // 删除ArrayList中重复元素,保持顺序
  2. public static void removeDuplicateWithOrder(List list) {
  3. Set set = new HashSet();
  4. List newList = new ArrayList();
  5. for (Iterator iter = list.iterator(); iter.hasNext();) {
  6. Object element = iter.next();
  7. if (set.add(element))
  8. newList.add(element);
  9. }
  10. list.clear();
  11. list.addAll(newList);
  12. System.out.println( " remove duplicate " + list);
  13. }
复制代码

4.把list里的对象遍历一遍,用list.contain(),如果不存在就放入到另外一个list集合中

  1. public static List removeDuplicate(List list){
  2. List listTemp = new ArrayList();
  3. for(int i=0;i<list.size();i++){
  4. if(!listTemp.contains(list.get(i))){
  5. listTemp.add(list.get(i));
  6. }
  7. }
  8. return listTemp;
  9. }
复制代码



回复

使用道具 举报