2

我想根据值的某些属性对 Java TreeMap 进行排序。具体来说，我想TreeMap<Integer, Hashset<Integer>>根据 的大小对 a 进行排序Hashset<Integer>。为了实现这一点，我做了以下工作：

比较器类：

private static class ValueComparer implements Comparator<Integer> {
    private Map<Integer, HashSet<Integer>>  map = null;
    public ValueComparer (Map<Integer, HashSet<Integer>> map){
        super();
        this.map = map;
    }

@Override
    public int compare(Integer o1, Integer o2) {
        HashSet<Integer> h1 = map.get(o1);
        HashSet<Integer> h2 = map.get(o2);

        int compare = h2.size().compareTo(h1.size());

        if (compare == 0 && o1!=o2){
            return -1;
        }
        else {
            return compare;
        }
    }
}

一个使用示例：

TreeMap<Integer, HashSet<Integer>> originalMap = new TreeMap<Integer, HashSet<Integer>>();

//load keys and values into map

ValueComparer comp = new ValueComparer(originalMap);
TreeMap<Integer, HashSet<Integer>> sortedMap = new TreeMap<Integer, HashSet<Integer>>(comp);
sortedMap.putAll(originalMap);

问题：

originalMap当包含超过 2 个相同大小的值时，这不起作用。对于其他情况，它可以正常工作。当映射中两个以上的值大小相同时，新排序映射中的第三个值为 null 并在我尝试访问它时抛出 NullPointerException。

我无法弄清楚问题是什么。如果有人能指出，我会很好。

更新： 这是一个在两个值具有相同大小时有效的示例：http: //ideone.com/iFD9c 在上面的示例中，如果您取消注释第 52-54 行，此代码将失败 - 这就是我的问题所在。

4

6 回答 6

6

更新：你不能仅仅因为你想避免重复的键不被删除-1而返回。ValueComparator检查合同Comparator.compare。

当您将 a 传递Comparator给TreeMap您时，您会计算一个（“新”）放置条目的位置。没有（计算的）密钥可以在TreeMap.

如果要按orginalMap值的大小对值进行排序，可以执行以下操作：

public static void main(String[] args) throws Exception {

    TreeMap<Integer, HashSet<Integer>> originalMap = 
        new TreeMap<Integer, HashSet<Integer>>();

    originalMap.put(0, new HashSet<Integer>() {{ add(6); add(7); }});
    originalMap.put(1, new HashSet<Integer>() {{ add(6); }});
    originalMap.put(2, new HashSet<Integer>() {{ add(9); add(8); }});


    ArrayList<Map.Entry<Integer, HashSet<Integer>>> list = 
        new ArrayList<Map.Entry<Integer, HashSet<Integer>>>();
    list.addAll(originalMap.entrySet());

    Collections.sort(list, new Comparator<Map.Entry<Integer,HashSet<Integer>>>(){
        public int compare(Map.Entry<Integer, HashSet<Integer>> o1,
                           Map.Entry<Integer, HashSet<Integer>> o2) {

            Integer size1 = (Integer) o1.getValue().size();
            Integer size2 = (Integer) o2.getValue().size();
            return size2.compareTo(size1);
        }
    });

    System.out.println(list);
}
于 2011-10-06T10:36:26.610 回答
1

您的比较器不尊重 Comparator 合同： if compare(o1, o2) < 0， thencompare(o2, o1)应该是> 0。当两个大小相同且整数不相同时，您必须找到一种确定性的方法来比较您的元素。在这种情况下，您也许可以使用System.identityHashCode()整数来比较它们。

也就是说，我真的很想知道你可以用这样的地图做什么：你不能创建新的整数并使用它们从地图中获取值，你不能修改它所拥有的集合。

旁注：您的比较器代码示例使用mapanddata来引用相同的地图。

于 2011-10-06T10:38:23.630 回答
1

您的比较器逻辑（我不确定我是否遵循如果设置大小相等但它们的键不同则返回 -1 的原因）不应影响 Map 本身在您调用时返回的内容get(key)。

你确定你没有在初始地图中插入空值吗？这段代码是什么样的？

于 2011-10-06T10:38:40.690 回答
1

您可以让 TreeMap 仅按键排序。无法创建按值排序的 TreeMap，因为您会得到 StackOverflowException。

想想看。要从树中获取元素，您需要执行比较，但要执行比较，您需要获取元素。

您必须在其他集合中对其进行排序或使用树，您必须将整数（来自条目值）也封装到条目键中，并使用从键中获取的整数定义比较器。

于 2011-10-06T10:57:36.283 回答
0

假设您不能使用返回 0 和 Set 的比较器，这可能会起作用：将所有元素添加originalMap.entrySet()到 an中ArrayList，然后ArrayList使用 your对其进行排序ValueComparer，并根据需要将其更改return 0为。

然后将排序ArrayList中的所有条目添加到LinkedHashMap.

于 2011-10-06T10:50:53.457 回答
0

I had a similar problem as the original poster. I had a TreeMap i wanted to sort on a value. But when I made a comparator that looked at the value, i had issues because of the breaking of the comparator that JB talked about. I was able to use my custom comparator and still observe the contract. When the valuse I was looking at were equal, i fell back to comparing the keys. I didn't care about the order if values were equal.

    public int compare(String a, String b) {
    if(base.get(a)[0] == base.get(b)[0]){ //need to handle when they are equal
        return a.compareTo(b);
    }else if (base.get(a)[0] < base.get(b)[0]) {
        return -1;
    } else {
        return 1;
    } // returning 0 would merge keys
于 2013-09-19T12:38:12.673 回答