有这样一个场景：

需要把Android手机中所有的图片按文件夹分类查出，并将文件夹排序。

我的实现方式是这样的：

  1. 使用MediaStore将所有的图片文件的路径查出，得到一个List
  2. 遍历List，按文件所处文件夹的路径将文件按文件夹分类，得到一个Map<String,List<String>>。也就是相册路径与其相片路径列表的对应。

由于为了区分同名相册，Map中Key使用的是文件夹的绝对路径。那么怎么将上述Map按文件夹排序呢？我想到了使用TreeMap，实现如下：

new TreeMap<>(new Comparator<String>() {
        @Override
        public int compare(String lhs, String rhs) {
            return ((new File(lhs)).getName()).compareTo(new File(rhs).getName());
        }
});

传入一个Comparator，按照文件夹的名称来排序Key不就行啦！然而结果略微有点不正常，同名的相册会被覆盖额额额。Map不是按照Key的compareTo方法来判断是否覆盖已有项么？

然而并不是这样，Map的文档写得很清楚，是通过containsKey来判断的，然而这个函数是要看具体实现的：

Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)

TreeMap的实现是这个鬼样子：

public boolean containsKey(Object key) {
        return getEntry(key) != null;
}

看看getEntry(key):

final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
}

因为我定义了comparator，所以要看看getEntryUsingComparator(key):

final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
}

可以看到是遍历整个Tree，将待检查的key与Tree中所有Key进行比较。若cpr.compare(k, p.key);结果为0，表示两个key相同，也就是指Map中已经存在这个Key了，于是就可以开开心心地覆盖了。。。

我原以为提供的Comparator只是用来排序的啊啊啊啊啊，你居然用来检查唯一性了！！！！好吧，其实文档中有写额

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

人家已经明明白白地告诉我通过Comparator判断得到的相等要跟通过equals判断的相一致啊啊啊。

解决方法

那么该怎么写Comparator才能既保证按照文件夹名称排序，也保证同名文件夹的比较结果不为0呢（为0就表示相等了）？

文件夹名称相同就再接着比较其绝对路径不就OK啦，反正同名文件夹怎么排都是一样的：

new TreeMap<>(new Comparator<String>() {
        @Override
        public int compare(String lhs, String rhs) {
            int result = ((new File(lhs)).getName()).compareTo(new File(rhs).getName());

            return result == 0 ? lhs.compareTo(rhs) : result;
        }
});

下面检查一下这个Comparator是不是符合compare的规范:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

It is generally the case, but not strictly required that (compare(x, y)==0) == (x.equals(y)). Generally speaking, any comparator that violates this condition should clearly indicate this fact. The recommended language is "Note: this comparator imposes orderings that are inconsistent with equals."

  • 第一条：
    • 当文件夹同名时，使用的是String的compareTo()方法，没问题
    • 当文件夹不同名时，也是使用String的compareTo()方法，没问题
  • 第二条：
    • 若X,Y同名，Y,Z同名：那就是按照绝对路径比较，没问题
    • 若X,Y同名，Y,Z不同名：Y,Z是按照文件夹名称比较的，而X Y文件夹名相同，故成立。
    • 若X,Y不同名，Y,Z同名，X与Z按文件夹名比较，相当于X Y比较，成立。
    • 若 X,Y不同名，Y,Z不同名，则全按照文件夹名称比较，故成立。
  • 第三条： 显然三者绝对路径都相同，故成立！（废话，就是要实现这个好么）

PS: 我是为了说服自己这么写不会出bug了才写这么多的。。。