Java判断两个List是否相同

作者: 我是龙俊 | 来源:发表于2017-08-19 20:18 被阅读1098次

简书新手，第一次写博客，一是为了巩固一下，加深印象，二是留作一个底稿，方便以后查看。还有呢，就是希望在这里能得到大神得指点，以免误人子弟。
如有不足，敬请谅解，欢迎指正，谢谢！

一、背景

昨天写项目时遇到一个需求，要求第一次把服务端请求回来的List保存到本地，下次进来，需要判断服务端请求下来的List与本地保存的List是否相同，如果相同，则使用本地保存的；如果不同，则把服务端请求下来的List覆盖本地原先保存的。
so，我简单列了一下提纲：

1、先判断本地中是否有保存的，没有则把请求回来的保存的到本地中；

2、有则判断请求回来的与本地中List个数是否相等若不相等，则把请求回来的覆盖原先在本地中保存的；

3、若相等，遍历请求下来List与本地中保存的List各个元素是否一致若不一致，则把请求回来的覆盖原先在本地中保存的；

4、若一致，则不做操作，直接使用原先保存的

然而，这样遍历如果数据量小还好，如果数据量大的话就得考虑一下性能了。

二、实战（比较两个Java list是否相同的性能优化）

1、最粗暴的方法 (遍历两个List)

package com.example;

import java.util.ArrayList;

public class CheckDiffList {
    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        for (int i = 0; i < 10000; i++) {
            list1.add("test" + i);
            list2.add("test" + i * 2);
        }

        System.out.println(getDiffrent(list1, list2));

//        判断两个List内的元素是否相同
//        getDiffrent total times 2514359
//        false
    }

    /**
     * 判断两个List内的元素是否相同
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        if (list1.size() != list2.size()) {
            System.out.println("getDiffrent total times " + (System.nanoTime() - st));
            return false;
        }
        for (String str : list1) {
            if (!list2.contains(str)) {
                System.out.println("getDiffrent total times " + (System.nanoTime() - st));
                return false;
            }
        }
        System.out.println("getDiffrent total times " + (System.nanoTime() - st));
        return true;
    }
}

这种方法也就是我最初想到的，总共要循环的次数是两个List的size的乘积，从输出看耗时也是比较长的。

2、利用Java中为List提供的方法retainAll()

package com.example;

import java.util.ArrayList;
import java.util.List;

public class CheckDiffList {

    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        for (int i = 0; i < 10000; i++) {
            list1.add("test" + i);
            list2.add("test" + i * 2);
        }

        System.out.println(getDiffrent2(list1, list2));

//        判断两个List内的元素是否相同
//        getDiffrent2 total times 7563
//        false
    }

    /**
     * 判断两个List内的元素是否相同
     * <p>
     * 此方法有bug  见Food.class
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent2(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        System.out.println("getDiffrent2 total times " + (System.nanoTime() - st));
        return !list1.retainAll(list2);
    }
}

很显然，方法2比方法1耗时少很多。我们可以来看看retainAll()的源码

   /**
     * Retains only the elements in this list that are contained in the
     * specified collection.  In other words, removes from this list all
     * of its elements that are not contained in the specified collection.
     *
     * @param c collection containing elements to be retained in this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //调用自己的私有方法
        return batchRemove(c, true);
    }

    //如果此 collection 由于调用而发生更改，则返回 true
    //集合A比较与集合B的交集
    private boolean batchRemove(Collection<?> c, boolean complement) {
        //获得当前对象的所有元素
        final Object[] elementData = this.elementData;
       //w：标记两个集合公共元素的个数
        int r = 0, w = 0;
       //设置标志位
        boolean modified = false;
        try {
            //遍历集合A
            for (; r < size; r++)
               //判断集合B中是否包含集合A中的当前元素
                if (c.contains(elementData[r]) == complement)
                    //如果包含则直接保存。
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            // 如果 c.contains() 抛出异常
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
               //w为当前集合A的length
                w += size - r;
            }
            //如果集合A的大小放生改变
            if (w != size) {
                // clear to let GC do its work
               // 清除工作
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                //记录集合中元素的改变(add/remove)
                modCount += size - w;
                //设置当前数组的大小
                size = w;
               //返回为true
                modified = true;
            }
        }
        return modified;
    }

哈哈哈，源码我看得也不是特别懂，里边有涉及到关键字transient，还有List的contains()、System.arraycopy(Object src, int srcPos,Object dest, int destPos, int length)方法。

不过结论是retainAll方法的返回值：如果集合A数组的大小没有改变，则返回false。如果集合A和集合B是完全相同的集合，也会返回false。两个集合没有交集，才会返回true。
简单来说，判断两个集合是否有交集，有则返回false，无则返回true（这句话不严谨）。

还有为什么，我的注释上此方法用来判断两个List是否相同有bug，并不是说java这个方法有bug，而是我们直接使用来去判断两个list元素是否相同有bug，是由于List的contains()的方法导致的，这个demo中是List<String>，假如是List<Person>就会看到差别了。

List的contains()中调用的是object的equals方法，而String复写了Object的equals。这个我想另起一文来单独记录。哈哈哈，前后花了好几个小时才搞明白，只能怪自己技术太菜。

3、利用HashMap key唯一，value可以重复的特点，把list中各元素放到HashMap中

我们的需求是判断两个List中的元素是否相同,那么可以这样考虑：用一个map存放list的所有元素，其中的key为list1的各个元素，value为该元素出现的次数,接着把list2的所有元素也放到map里，如果已经存在则value+1，一旦value停止+1，说明有元素不同了，返回false。否则一直遍历直至list2中所有元素，返回true。这样我们只需循环m+n次，大大减少了循环的次数。

package com.example;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CheckDiffList {

    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        for (int i = 0; i < 10000; i++) {
            list1.add("test" + i);
            list2.add("test" + i * 2);
        }

        System.out.println(getDiffrent3(list1, list2));

//        判断两个List内的元素是否相同
//        getDiffrent3 total times 26976244
//        false
    }

     /**
     * 判断两个List内的元素是否相同
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent3(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        Map<String, Integer> map = new HashMap<String, Integer>(list1.size() + list2.size());
        for (String string : list1) {
            map.put(string, 1);
        }
        for (String string : list2) {
            Integer cc = map.get(string);
            if (cc != null) {
                map.put(string, ++cc);
                continue;
            }
            System.out.println("getDiffrent3 total times " + (System.nanoTime() - st));
            return false;
        }
        System.out.println("getDiffrent3 total times " + (System.nanoTime() - st));
        return true;
    }
}

（此方法又复习了HashMap使用key-value来映射和存储数据，Key必须惟一，value可以重复。HashMap是非同步的，所以线程不安全。呵呵，我之前对HashMap的理解也不够深。）

观察方法3我们只是随机取了一个list作为首次添加的标准，这样一旦我们的list2比list1的size大，则我们第二次put时的if判断也会耗时，所以有了方法4：

4、方法3的改进版（首先去判断list1、list2的size大小）

package com.example;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CheckDiffList {

    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        for (int i = 0; i < 10000; i++) {
            list1.add("test" + i);
            list2.add("test" + i * 2);
        }

        System.out.println(getDiffrent4(list1, list2));

//        判断两个List内的元素是否相同
//        getDiffrent4 total times   37313357
//        false
    }
    /**
     * 判断两个List内的元素是否相同
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent4(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        Map<String, Integer> map = new HashMap<String, Integer>(list1.size() + list2.size());
        List<String> maxList = list1;
        List<String> minList = list2;
        if (list2.size() > list1.size()) {
            maxList = list2;
            minList = list1;
        }
        for (String string : maxList) {
            map.put(string, 1);
        }
        for (String string : minList) {
            Integer cc = map.get(string);
            if (cc != null) {
                map.put(string, ++cc);
                continue;
            }
            return false;
        }
        System.out.println("getDiffrent4 total times " + (System.nanoTime() - st));
        return true;
    }
}

方法4对两个list的大小进行了判断，小的在最后添加，这样会减少循环里的判断，性能又有了一定的提升！但本例中方法4比方法3耗时还要长，我的理解是多做了一次判断两个集合size大小的判断，但是我觉得这个性能可以牺牲。

方法3和方法4都有共同的一个问题：假如某个list中有重复元素的话，由于map不允许有相同的key，所以方法失效！

三、小结

比较以上4种方法，耗时排行getDiffrent2<getDiffrent1<getDiffrent3<getDiffrent4，方法4比方法3多了一次判断，更耗时我可以理解，为什么3和4比1还耗时呢？

写的写的自己都写懵逼了，第一次写博客，原本是想探讨一下这4种方法的性能，结果成了提供了判断两个list是否相同的4种方法，欢迎各位大神指正，呵呵哒。

以下是完整的代码(注意这个类最好不要整体运行，因为方法2会改变list内的内容，建议分别运行1、2、3、4方法)

package com.example;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CheckDiffList {

    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        for (int i = 0; i < 10000; i++) {
            list1.add("test" + i);
            list2.add("test" + i * 2);
        }

        System.out.println(getDiffrent(list1, list2));
        System.out.println(getDiffrent2(list1, list2));
        System.out.println(getDiffrent3(list1, list2));
        System.out.println(getDiffrent4(list1, list2));

//        判断两个List内的元素是否相同
//        getDiffrent total times    2514359           
//        false
//        getDiffrent2 total times      7563      
//        false
//        getDiffrent3 total times  26976244      
//        false
//        getDiffrent4 total times  37313357   
//        false
    }
    
    /**
     * 判断两个List内的元素是否相同
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent4(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        Map<String, Integer> map = new HashMap<String, Integer>(list1.size() + list2.size());
        List<String> maxList = list1;
        List<String> minList = list2;
        if (list2.size() > list1.size()) {
            maxList = list2;
            minList = list1;
        }
        for (String string : maxList) {
            map.put(string, 1);
        }
        for (String string : minList) {
            Integer cc = map.get(string);
            if (cc != null) {
                map.put(string, ++cc);
                continue;
            }
            System.out.println("getDiffrent4 total times " + (System.nanoTime() - st));
            return false;
        }
        System.out.println("getDiffrent4 total times " + (System.nanoTime() - st));
        return true;
    }

    /**
     * 判断两个List内的元素是否相同
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent3(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        Map<String, Integer> map = new HashMap<String, Integer>(list1.size() + list2.size());
        for (String string : list1) {
            map.put(string, 1);
        }
        for (String string : list2) {
            Integer cc = map.get(string);
            if (cc != null) {
                map.put(string, ++cc);
                continue;
            }
            System.out.println("getDiffrent3 total times " + (System.nanoTime() - st));
            return false;
        }
        System.out.println("getDiffrent3 total times " + (System.nanoTime() - st));
        return true;
    }

    /**
     * 判断两个List内的元素是否相同
     * <p>
     * 此方法有bug  见Food.class
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent2(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        System.out.println("getDiffrent2 total times " + (System.nanoTime() - st));
        return !list1.retainAll(list2);
    }

    /**
     * 判断两个List内的元素是否相同
     *
     * @param list1
     * @param list2
     * @return
     */
    private static boolean getDiffrent(List<String> list1, List<String> list2) {
        long st = System.nanoTime();
        if (list1.size() != list2.size()) {
            System.out.println("getDiffrent total times " + (System.nanoTime() - st));
            return false;
        }
        for (String str : list1) {
            if (!list2.contains(str)) {
                System.out.println("getDiffrent total times " + (System.nanoTime() - st));
                return false;
            }
        }
        System.out.println("getDiffrent total times " + (System.nanoTime() - st));
        return true;
    }
}

本文参考http://www.cnblogs.com/czpblog/archive/2012/08/06/2625794.html
http://www.cnblogs.com/lyajs/p/5737410.html

网友评论

罗曼蒂克:都已经取到了直接使用和本地没区别。其次，md5啊
我是龙俊:@罗曼蒂克很✅啊
罗曼蒂克:@我是龙俊
List<Integer> lst=new ArrayList<>();
lst.add(1);
lst.add(2);
System.out.println(SecureUtil.md5(lst.toString()));

List<Integer> lst2=new ArrayList<>();
lst2.add(1);
lst2.add(2);
System.out.println(SecureUtil.md5(lst2.toString()));

lst2.add(3);
System.out.println(SecureUtil.md5(lst2.toString()));

结果是
04cd0e0151f352e7fd414d694a604136
04cd0e0151f352e7fd414d694a604136
49a5a960c5714c2e29dd1a7e7b950741
我是龙俊:md5什么意思
黑女2008:从你的需求来看，就直接把服务器返回的list放客户端就好了，干嘛还要判断？
我是龙俊:如果服务端返回的list和本地保存的相同，从本地读取的更快啊

Java判断两个List是否相同

一、背景

1、先判断本地中是否有保存的，没有则把请求回来的保存的到本地中；

2、有则判断请求回来的与本地中List个数是否相等若不相等，则把请求回来的覆盖原先在本地中保存的；

3、若相等，遍历请求下来List与本地中保存的List各个元素是否一致若不一致，则把请求回来的覆盖原先在本地中保存的；

4、若一致，则不做操作，直接使用原先保存的

二、实战（比较两个Java list是否相同的性能优化）

1、最粗暴的方法 (遍历两个List)

2、利用Java中为List提供的方法retainAll()

3、利用HashMap key唯一，value可以重复的特点，把list中各元素放到HashMap中

4、方法3的改进版（首先去判断list1、list2的size大小）

三、小结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java

Java开发那些事

Java学习笔记

WeLi的java学习

Java判断两个List是否相同

一、背景

1、先判断本地中是否有保存的， 没有则把请求回来的保存的到本地中；

2、有则判断请求回来的与本地中List个数是否相等 若不相等，则把请求回来的覆盖原先在本地中保存的；

3、若相等，遍历请求下来List与本地中保存的List各个元素是否一致 若不一致，则把请求回来的覆盖原先在本地中保存的；

4、若一致，则不做操作，直接使用原先保存的

二、实战（比较两个Java list是否相同的性能优化）

1、最粗暴的方法 (遍历两个List)

2、利用Java中为List提供的方法retainAll()

3、利用HashMap key唯一，value可以重复的特点，把list中各元素放到HashMap中

4、方法3的改进版（首先去判断list1、list2的size大小）

三、小结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java

Java开发那些事

Java学习笔记

WeLi的java学习

1、先判断本地中是否有保存的，没有则把请求回来的保存的到本地中；

2、有则判断请求回来的与本地中List个数是否相等若不相等，则把请求回来的覆盖原先在本地中保存的；

3、若相等，遍历请求下来List与本地中保存的List各个元素是否一致若不一致，则把请求回来的覆盖原先在本地中保存的；