一个集合里有两个相同元素 高效的找出两个List中的不同元素

高效的找出两个List中的不同元素  

    如题 有List<String> list 和List<String> list 两个集合各有上万个元素 怎样取出两个集合中不同的元素？    方法 :遍历两个集合         package czp test;import java util ArrayList;import java util List;public class TestList {        public static void main（String[] args） {        List<String> list = new ArrayList<String>（）         List<String> list = new ArrayList<String>（）         for （int i = ; i < ; i++） {        list add（ test +i）         list add（ test +i* ）         }        getDiffrent（list list ）         //输出 total times         }        /**        * 获取连个List的不同元素        * @param list                 * @return        */        private static List<String> getDiffrent（List<String> list List<String> list ） {        long st = System nanoTime（）         List<String> diff = new ArrayList<String>（）         for（String str:list ）        {        if（！ntains（str））        {        diff add（str）         }        }        System out println（ total times +（System nanoTime（） st））         return diff;        }}        千万不要采用这种方法 总共要循环的次数是两个List的size相乘的积 从输出看耗时也是比较长的 那么我们有没有其他的方法呢？当然有

   方法 :采用List提供的retainAll（）方法         package czp test;import java util ArrayList;import java util List;public class TestList {        public static void main（String[] args） {        List<String> list = new ArrayList<String>（）         List<String> list = new ArrayList<String>（）         for （int i = ; i < ; i++） {        list add（ test +i）         list add（ test +i* ）         }        getDiffrent（list list ）         //输出 total times         getDiffrent （list list ）         //输出 getDiffrent total times         }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent （List<String> list List<String> list ） {        long st = System nanoTime（）         list retainAll（list ）         System out println（ getDiffrent total times +（System nanoTime（） st））         return list ;        }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent（List<String> list List<String> list ） {        long st = System nanoTime（）         List<String> diff = new ArrayList<String>（）         for（String str:list ）        {        if（！ntains（str））        {        diff add（str）         }        }        System out println（ getDiffrent total times +（System nanoTime（） st））         return diff;        }}   

    很遗憾 这种方式虽然只要几行代码就搞定 但是这个却更耗时 查看retainAll（）的源码         public boolean retainAll（Collection<?> c） {        boolean modified = false;        Iterator<E> e = iterator（）         while （e hasNext（）） {        if （！ntains（e next（））） {        e remove（）         modified = true;        }        }        return modified;        }        无需解释这个耗时是必然的 那么我们还有没有更好的办法呢？仔细分析以上两个方法中我都做了mXn次循环 其实完全没有必要循环这么多次 我们的需求是找出两个List中的不同元素 那么我可以这样考虑 用一个map存放lsit的所有元素 其中的key为lsit 的各个元素 value为该元素出现的次数 接着把list 的所有元素也放到map里 如果已经存在则value加 最后我们只要取出map里value为 的元素即可 这样我们只需循环m+n次 大大减少了循环的次数         package czp test;import java util ArrayList;import java util HashMap;import java util List;import java util Map;public class TestList {        public static void main（String[] args） {        List<String> list = new ArrayList<String>（）         List<String> list = new ArrayList<String>（）         for （int i = ; i < ; i++） {        list add（ test +i）         list add（ test +i* ）         }        getDiffrent（list list ）         //输出 total times         getDiffrent （list list ）         //输出 getDiffrent total times         getDiffrent （list list ）         //输出 getDiffrent total times         }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent （List<String> list List<String> list ） {        long st = System nanoTime（）         Map<String Integer> map = new HashMap<String Integer>（list size（）+list size（））         List<String> diff = new ArrayList<String>（）         for （String string : list ） {        map put（string ）         }        for （String string : list ） {        Integer cc = map get（string）         if（cc!=null）        {        map put（string ++cc）         continue;        }        map put（string ）         }        for（Map Entry<String Integer> entry:map entrySet（））        {        if（entry getValue（）== ）        {        diff add（entry getKey（））         }        }        System out println（ getDiffrent total times +（System nanoTime（） st））         return list ;        }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent （List<String> list List<String> list ） {        long st = System nanoTime（）         list retainAll（list ）         System out println（ getDiffrent total times +（System nanoTime（） st））         return list ;        }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent（List<String> list List<String> list ） {        long st = System nanoTime（）         List<String> diff = new ArrayList<String>（）         for（String str:list ）        {        if（！ntains（str））        {        diff add（str）         }        }        System out println（ getDiffrent total times +（System nanoTime（） st））         return diff;        }}   

    显然 这种方法大大减少耗时 是方法 的 / 是方法 的 / 这个性能的提升时相当可观的 但是 这不是最佳的解决方法 观察方法 我们只是随机取了一个list作为首次添加的标准 这样一旦我们的list 比list 的size大 则我们第二次put时的if判断也会耗时 做如下改进         package czp test;import java util ArrayList;import java util HashMap;import java util List;import java util Map;public class TestList {        public static void main（String[] args） {        List<String> list = new ArrayList<String>（）         List<String> list = new ArrayList<String>（）         for （int i = ; i < ; i++） {        list add（ test +i）         list add（ test +i* ）         }        getDiffrent（list list ）         getDiffrent （list list ）         getDiffrent （list list ）         getDiffrent （list list ） //        getDiffrent total times //        getDiffrent total times //        getDiffrent total times //        getDiffrent total times         }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent （List<String> list List<String> list ） {        long st = System nanoTime（）         Map<String Integer> map = new HashMap<String Integer>（list size（）+list size（））         List<String> diff = new ArrayList<String>（）         List<String> maxList = list ;        List<String> minList = list ;        if（list size（）>list size（））        {        maxList = list ;        minList = list ;        }        for （String string : maxList） {        map put（string ）         }        for （String string : minList） {        Integer cc = map get（string）         if（cc!=null）        {        map put（string ++cc）         continue;        }        map put（string ）         }        for（Map Entry<String Integer> entry:map entrySet（））        {        if（entry getValue（）== ）        {        diff add（entry getKey（））         }        }        System out println（ getDiffrent total times +（System nanoTime（） st））         return diff;        }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent （List<String> list List<String> list ） {        long st = System nanoTime（）         Map<String Integer> map = new HashMap<String Integer>（list size（）+list size（））         List<String> diff = new ArrayList<String>（）         for （String string : list ） {        map put（string ）         }        for （String string : list ） {        Integer cc = map get（string）         if（cc!=null）        {        map put（string ++cc）         continue;        }        map put（string ）         }        for（Map Entry<String Integer> entry:map entrySet（））        {        if（entry getValue（）== ）        {        diff add（entry getKey（））         }        }        System out println（ getDiffrent total times +（System nanoTime（） st））         return diff;        }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent （List<String> list List<String> list ） {        long st = System nanoTime（）         list retainAll（list ）         System out println（ getDiffrent total times +（System nanoTime（） st））         return list ;        }        /**        * 获取连个List的不同元素        * @param list         * @param list         * @return        */        private static List<String> getDiffrent（List<String> list List<String> list ） {        long st = System nanoTime（）         List<String> diff = new ArrayList<String>（）         for（String str:list ）        {        if（！ntains（str））        {        diff add（str）         }        }        System out println（ getDiffrent total times +（System nanoTime（） st））         return diff;        }}        这里对连个list的大小进行了判断 小的在最后添加 这样会减少循环里的判断 性能又有了一定的提升 正如一位朋友所说 编程是无止境的 只要你认真去思考了 总会找到更好的方法！ lishixinzhi/Article/program/Java/hx/201311/27046