比较两个集合是否相等

朱雀 2020-09-13 11:11 976阅读 0赞

如题，怎么比较两个集合是否相等呢？比如：

List listA = \{1,1,2,3,4\}

List listB = \{1,2,3,4,5\}

### 思路一： ###

1、首先，两个集合的长度必须要一样，一个长度是3，一个是4，那两个集合必然不相等；

2、listA  要包含  listB 里面的每一个元素

3、listB  要包含  listA 里面的每一个元素

代码实现：

/**
         * 比较两个集合是否相等
         * @param a
         * @param b
         * @return
         */
        public static boolean isEqualCollection(final Collection a, final Collection b) {
            if (a.size() != b.size()) {
                return false;
            }
            for (Iterator ita = a.iterator(); ita.hasNext(); ) {
                if (!b.contains(ita.next())) {
                    return false;
                }
            }
            for (Iterator itb = b.iterator(); itb.hasNext(); ) {
                if (!a.contains(itb.next())) {
                    return false;
                }
            }
            return true;
        }

测试：

public static void main(String[] args) {
            List<Integer> lista = Arrays.asList(1, 1, 2, 3, 4);
            List<Integer> listb = Arrays.asList(1, 2, 3, 4, 5);
            List<Integer> listc = Arrays.asList(2, 1, 4, 3, 1);
            boolean equalCollectionAB = isEqualCollection(lista, listb);
            System.out.println("A和B是否相等：" + equalCollectionAB);
            boolean equalCollectionAC = isEqualCollection(lista, listc);
            System.out.println("A和C是否相等：" + equalCollectionAC);
        }

结果：

![20191010133755369.png][]

总结：

两个集合相互遍历，利用contains方法，确保两个集合 你中有我，我中有你，且长度相同。

但是如果两个集合中的数据量较大时，遍历的话，复杂度就是O(n)，我们下面来测试一下，A、B两个集合，各有十万条数据

public static void main(String[] args) {
            List<Integer> lista = new ArrayList<>();
            for (int i = 0; i < 100000; i++) {
                lista.add(i);
            }
            List<Integer> listb = new ArrayList<>();
            for (int i = 0; i < 100000; i++) {
                listb.add(i);
            }
            long start = System.currentTimeMillis();
            boolean equalCollection = isEqualCollection(lista, listb);
            long cost = System.currentTimeMillis() - start;
            System.out.println("A和B是否相等：" + equalCollection + "，耗时：" + cost + "ms");
        }

测试结果为：

![2019101013482059.png][]

还是蛮耗时的，需要五六秒的时间

### 思路二： ###

1、首先，两个集合的长度必须要一样，一个长度是3，一个是4，那两个集合必然不相等；

2、listA 里面的每个元素都在listB里，且元素的个数相同

代码实现：

public static boolean isEqualCollectionFast(final Collection a, final Collection b) {
            if (a.size() != b.size()) {
                return false;
            }
            Map mapa = getMap(a);
            Map mapb = getMap(b);
    
            if (mapa.size() != mapb.size()) {
                return false;
            }
    
            Iterator it = mapa.keySet().iterator();
    
            while (it.hasNext()) {
                Object obj = it.next();
                if (getFreq(obj, mapa) != getFreq(obj, mapb)) {
                    return false;
                }
            }
            return true;
        }
    
    
    private static Integer INTEGER_ONE = new Integer(1);
    
    
        /**
         * 集合转map，值就是key出现的次数
         *
         * @param coll
         * @return
         */
        public static Map getMap(final Collection coll) {
            Map count = new HashMap();
            Iterator it = coll.iterator();
            while (it.hasNext()) {
                Object obj = it.next();
                Integer c = (Integer) (count.get(obj));
                if (null == c) {
                    count.put(obj, INTEGER_ONE);
                } else {
                    count.put(obj, new Integer(c.intValue() + 1));
                }
            }
            return count;
        }
    
        /**
         * 获取map的值（频率）
         *
         * @param obj
         * @param freqMap
         * @return
         */
        private static final int getFreq(final Object obj, final Map freqMap) {
            Integer count = (Integer) freqMap.get(obj);
            if (null == count) {
                return 0;
            }
            return count.intValue();
        }

测试：

public static void main(String[] args) {
            List<Integer> lista = new ArrayList<>();
            for (int i = 0; i < 100000; i++) {
                lista.add(i);
            }
            List<Integer> listb = new ArrayList<>();
            for (int i = 0; i < 100000; i++) {
                listb.add(i);
            }
            long start = System.currentTimeMillis();
            boolean equalCollection = isEqualCollectionFast(lista, listb);
            long cost = System.currentTimeMillis() - start;
            System.out.println("快速比较-A和B是否相等：" + equalCollection + "，耗时：" + cost + "ms");
        }

测试结果为：

![20191010135459279.png][]

发现换了一种写法，两个十万数据量的集合作比较，性能提升了185倍。所以我们平时开发过程中，要善于使用一级缓存、二级缓存等来帮助我们提高性能。

下面是不同数据量的情况，两种写法的性能比较

| 条数\时间 | 一般   | 快速 | 倍数  |
| --------- | ------ | ---- | ----- |
| 100       | 0ms    | 0ms  | ——    |
| 1000      | 6ms    | 1ms  | 6倍   |
| 10000     | 62ms   | 8ms  | 8倍   |
| 100000    | 5794ms | 25ms | 231倍 |

[20191010133755369.png]: /images/1599995491615.png
[2019101013482059.png]: /images/1599995474456.png
[20191010135459279.png]: /images/1599995459257.png