比较两个List是否相等（相同元素）

深藏阁楼爱情的钟 2022-04-06 12:20 617阅读 0赞

最近做的一个项目，需要校验两个List是否相等的问题，我们看看如何比较两个数组相等。数组是一个连续的内存空间，所以一般来说，两个数组相等，就是意味着他们有相同的长度，相同的元素，以及相同的顺序。我们看看JDK的Arrays.equals()实现就一目了然了。

public static boolean equals(int[] a, int[] a2) {
    	if (a==a2) return true;
    	if (a==null || a2==null) return false;
    	int length = a.length;
    	if (a2.length != length) return false;
    	for (int i=0; i<length; i++)
    		if (a[i] != a2[i]) return false;
    	return true;
    }

大致分成下面4个步骤：

a.检查是否指向同一个地址（不同引用）；

b.非空检查；

c.长度检查；

d.顺序和对应的元素相等检查。（依次比较，只要一个不等就返回false）

而对于List来说，没有固定的顺序(ArrayList底层是数组，可以用数组的比较方法；但是其他的List，如LinkedList，就不一样了。)，或者说顺序对List来说不是一个重要的属性。所以可以考虑其他方式来检查两个List是不是包含相同的元素。

如JDK的Collection.containsAll()，只是是对每个元素进行contains()操作。但是List允许重复的元素，所以这里无法比较重复元素的数量：

public boolean containsAll(Collection<?> c) {
    	for (Object e : c)
    		if (!contains(e))
    			return false;
    	return true;
    }

那么，如何对无序的元素进行equal比较呢？

比较简便直观的方法，就是分别对两个list排序，然后一个一个比较，只要不相等，则返回false，如果全部都相等，则返回true。

if (a.size() !=b.size())
        return false;
    Collections.sort(a);
    Collections.sort(b);
    for (int i = 0; i <a.size(); i++) {
        if(!a.get(i).equals(b.get(i)))
           return false;
    }
    return true;

但是这样两次排序，效率还是比较低的。所以可以通过Map来实现：

先存入HashMap，key为元素，value为出现的次数，然后再逐个元素比较出现的次数，这样能确保元素都包含，而且出现次数相同。

如下代码所示，具体可以参考org.apache.commons.collections.CollectionUtils.isEqualCollection() 。（CollectionUtils中大量使用了getCardinalityMap()的特性）

private static final Integer INTEGER_ONE = 1;
    public static boolean isEqualCollection(Collection a, Collection b){
        if (a.size() !=b.size()) {  // size是最简单的相等条件
           return false;
        }
        Map mapa = getCardinalityMap(a); 
        Map mapb = getCardinalityMap(b);
       
        // 转换map后，能去掉重复的，这时候size就是非重复项，也是先决条件
        if (mapa.size() !=mapb.size()) {  
           return false;
        }
        Iterator it =mapa.keySet().iterator();
        while (it.hasNext()) {
           Object obj = it.next();
           // 查询同一个obj，首先两边都要有，而且还要校验重复个数，就是map.value
           if (getFreq(obj,mapa) != getFreq(obj, mapb)) {
               return false;
           }
        }
        return true;
    }
    /**
     * 以obj为key，可以防止重复，如果重复就value++
     * 这样实际上记录了元素以及出现的次数
     */
    public static Map getCardinalityMap(Collection coll) {
        Map count = new HashMap();
        for (Iterator it =coll.iterator(); it.hasNext();) {
           Object obj =it.next();
           Integer c =(Integer) count.get(obj);
           if (c == null)   
               count.put(obj, INTEGER_ONE);
           else {
               count.put(obj, newInteger(c.intValue() + 1));
           }
        }
        return count;
    }
    private static final int getFreq(Objectobj, Map freqMap) {
        Integer count =(Integer) freqMap.get(obj);
        if (count != null) {
           return count.intValue();
        }
        return 0;
    }

文章来源：[http://blog.csdn.net/tiwerbao/article/details/42836305][http_blog.csdn.net_tiwerbao_article_details_42836305]

[http_blog.csdn.net_tiwerbao_article_details_42836305]: http://blog.csdn.net/tiwerbao/article/details/42836305