使用TreeMap的排序问题

Question

我试图将一些键值放入 HashMap 中，然后尝试使用 TreeMap 进行排序，如下所示。问题是，如果映射中存在相似的值，那么排序后它会考虑其中的任何一个。

   import java.util.*;

public class HashmapExample {

            public static void main(String[] args) {

            HashMap<String,Integer> map = new HashMap<String,Integer>();
            ValueComparator bvc =  new ValueComparator(map);
            TreeMap<String,Integer> sorted_map = new TreeMap(bvc);

            map.put("A",99);
            map.put("B",67);
            map.put("C",123);
            map.put("G",67);
            map.put("F",67);
            map.put("H",67);
            map.put("D",6);

            System.out.println("unsorted map");
            for (String key : map.keySet()) {
                System.out.println("key/value: " + key + "/"+map.get(key));
            }

            sorted_map.putAll(map);

            System.out.println("results after sorting");
            for (String key : sorted_map.keySet()) {
                System.out.println("key/value: " + key + "/"+sorted_map.get(key));
            }
        }

    }

    class ValueComparator implements Comparator {

      Map base;
      public ValueComparator(Map base) {
          this.base = base;
      }

      public int compare(Object a,Object b) {

        if((Integer)base.get(a) > (Integer)base.get(b)) {
          return 1;
        } else if((Integer)base.get(a) == (Integer)base.get(b)) {
          return 0;
        } else {
          return -1;
        }
      }
    }

之后的输出如下所示，

unsorted map
key/value: D/6
key/value: A/99
key/value: F/67
key/value: H/67
key/value: C/123
key/value: B/67
key/value: G/67
results after sorting
key/value: D/6
key/value: F/67
key/value: A/99
key/value: C/123

对于 B、G、F 和 H 键，我给出的值为 67。对地图进行排序后，它仅显示 F 值并删除 B、G 和 H 值。我想显示输出如下

    key/value: D/6
    key/value: B/67
    key/value: G/67
    key/value: F/67
    key/value: H/67
    key/value: A/99
    key/value: C/123

Answer 1

键 B、G 和 H 被消除的原因是因为您提供的比较器仅根据值进行比较。由于它们都具有相同的值，因此它们都是相等的键，这意味着其中一个将覆盖其他键。

要打印出您想要的内容，您的比较器需要首先比较这些值，然后如果它们相等，则比较键。

int compare(Comparable key1, Comparable key2) {
   // I'm guessing you are doing something like:
   // return map.get(key1).compareTo(map.get(key2));

    // you can change it to something like
    int result = key1.compareTo(key2);
    if ( result == 0 ) {
      result= key1.compareTo(key2) 
    }

    return result;

}

Answer 2

不要将 TreeSet 用于此目的或使 smt 类似

class ValueComparator implements Comparator<String> {
    private final Map<String, Integer> base;

    public ValueComparator(Map<String, Integer> base) {
        this.base = base;
    }

    public int compare(String a, String b) {
        int compareInts = base.get(a).compareTo(base.get(b));
        if (compareInts == 0) {
            return a.compareTo(b);
        } else {
            return compareInts;
        }
    }
}

Answer 3

TreeSet 会删除重复项，即当compareTo() == 0 时。

我建议您让比较器在值相同时比较键，并且您应该得到。

key/value: D/6
key/value: B/67
key/value: F/67
key/value: G/67
key/value: H/67
key/value: A/99
key/value: C/123

Answer 4

正如大家所说，您的比较代码已损坏。用这个替换它。这不会考虑具有相同值但不同键的两对相等。

  public int compare(Object a,Object b) {

    if((Integer)base.get(a) > (Integer)base.get(b)) {
      return 1;
    } else if((Integer)base.get(a) == (Integer)base.get(b)) {
      return ((String)a).compareTo((String)b);
    } else {
      return -1;
    }

  }

Answer 5

你的比较器有问题。例如，compare 方法对于 G 和 F 返回 0。因此，树状图没有与其中之一关联的键值对。

您需要研究比较器。

Answer 6

根据杰夫的回答，我写了一个通用版本：

public class MapValueComparator<K extends Comparable<K>, V extends Comparable<V>> implements Comparator<K> {
    private final Map<K, V> base;
    private final boolean ascending;

    public MapValueComparator(Map<K, V> base) {
        this.base = base;
        this.ascending = true;
    }

    public MapValueComparator(Map<K, V> base, boolean ascending) {
        this.base = base;
        this.ascending = ascending;
    }

    @Override
    public int compare(K a, K b) {
        int r = base.get(a).compareTo(base.get(b));
        if (r == 0)
            r = a.compareTo(b);

        if (ascending)
            return r;
        else
            return -r;
    }
}

它可以按如下方式使用：

Map<String,Integer> map = new HashMap<String,Integer>();
// add some contents to map ...

MapValueComparator<String, Integer> mvc = new MapValueComparator<String, Integer>(map);
TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(mvc);
sorted_map.putAll(map);