比较两个List是否相等（相同元素）-蒲公英云

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

　　最近做的一个项目，需要校验两个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;
}