Java判断两个List是否相同

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

一、背景

昨天写项目时遇到一个需求，要求第一次把服务端请求回来的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

最后编辑于：2017.12.10 02:38:23

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