仅在 Java 中按键对 Multimap 进行排序

Having a Multimap sorted on keys only in Java

提问by Olivier Grégtheitroade

I would like to have a c.g.c.c.Multimapthat is sorted based on keys only. The values shouldn't be sorted. I've tried to build something with guava's TreeMultimap, but I can't use it because the value type doesn't implement Comparable.

我想要一个c.g.c.c.Multimap仅基于键排序的。不应该对值进行排序。我试图用 guava's 构建一些东西TreeMultimap，但我不能使用它，因为值类型没有实现Comparable.

public class MyObject /* doesn't implement Comparable */ {
  private String name;
  private int score;
  // Getters/setters are implemented
  public static Function<MyObject,Integer> myObjectToScore {
    @Override public Integer apply (MyObject o) { return o.score; }
  }
  public static Multimap<Integer,MyObject> indexOnScore(Iterable<MyObject> i) {
    Multimap<Integer,MyObject> m = Multimaps.index(i, myObjectToScore());
    // Do the sort of the keys.
    return m;
  }
}

I've thought about getting a SortedSetof the keys, then iterating over each of these keys in the sorted set to fetch the various values, but I was hoping using an existing (yet undiscovered) feature in Guava rather than using this kind of hack.

我想过获取一个SortedSet键，然后遍历排序集中的每个键以获取各种值，但我希望使用 Guava 中现有的（尚未发现的）功能，而不是使用这种hack。

Note: I won't make MyObjectimplement Comparablebecause it makes no sense with my actual object.

注意：我不会MyObject实现，Comparable因为它对我的实际对象没有意义。

---

---

Example of input/output:

输入/输出示例：

Set<MyObject> s = Sets.newHashSet(
  new MyObject("a", 2),
  new MyObject("b", 3),
  new MyObject("c", 1),
  new MyObject("d", 3),
  new MyObject("e", 1)
); // Assuming constructor MyObject(String name, int score)

for (Map.Entry<Integer, MyObject> e: MyObject.indexedOnScore(s).entries()) {
  System.out.printf("%d -> %s%n", e.getKey(), e.getValue().getName());
}

Prints:

印刷：

1 -> c // or switched with line below
1 -> e
2 -> a
3 -> b // or switched with line below
3 -> d

采纳答案by ColinD

Multimaps.indexreturns an ImmutableListMultimap, so you wouldn't be able to sort it after creating it. You could, however, first create a sorted copy of your Iterable<MyObject>and feed that to Multimap.index... ImmutableListMultimapkeeps things in the same order it was given them.

Multimaps.index返回ImmutableListMultimap，因此您将无法在创建后对其进行排序。但是，您可以先创建一个已排序的副本Iterable<MyObject>并将其提供给Multimap.index...ImmutableListMultimap使事物保持与给定顺序相同的顺序。

public static ImmutableMultimap<Integer, MyObject> indexOnScore(Iterable<MyObject> i) {
  List<MyObject> sorted = Ordering.natural().onResultOf(myObjectToScore())
      .sortedCopy(i);
  return Multimaps.index(sorted, myObjectToScore());
}

Another option might be to create a TreeMultimapand use Ordering.arbitrary()as the Comparatorfor the values.

另一种选择可能是创建 aTreeMultimap并将Ordering.arbitrary()其Comparator用作值。

回答by gdejohn

MultimapBuilderwas introduced in Guava 16:

MultimapBuilder在 Guava 16 中引入：

<K extends Comparable<? super K>, V> ListMultimap<K, V> multimap() {
    return MultimapBuilder.treeKeys().linkedListValues().build();
}

That keeps your keys sorted by their natural order (treeKeys()is also overloaded to accept a custom comparator), and the values associated with each key are maintained in a LinkedList(ArrayListand HashSetare among the other options).

这使您的键按其自然顺序排序（treeKeys()也被重载以接受自定义比较器），并且与每个键关联的值保存在LinkedList(ArrayList和HashSet其他选项中)。

回答by Trevor Robinson

Though the OP's specific situation seems to have been answered using immutable multimap building functions, I needed a mutable version of what he was asking for. In case it helps anyone, here's the generic method I ended up creating:

虽然 OP 的具体情况似乎已经使用不可变的多图构建函数得到了回答，但我需要一个他所要求的可变版本。如果它对任何人有帮助，这是我最终创建的通用方法：

static <K, V> Multimap<K, V> newTreeArrayListMultimap(
    final int expectedValuesPerKey)
{
    return Multimaps.newMultimap(new TreeMap<K, Collection<V>>(),
        new Supplier<Collection<V>>()
        {
            @Override
            public Collection<V> get()
            {
                return new ArrayList<V>(expectedValuesPerKey);
            }
        });
}

回答by Jared Levy

Call Multimaps.newMultimap, which gives you the flexibility to create, for example, a Multimap backed by TreeMap whose values are ArrayLists.

调用Multimaps.newMultimap，这使您可以灵活地创建，例如，由值为 ArrayList 的 TreeMap 支持的 Multimap。

回答by GFonte

I'd like to point out that the alternative proposed solution, namely "to create a TreeMultimap and use Ordering.arbitrary() as the Comparator for the values", only works if MyObject doesn't override equals() or hashcode(). Ordering.arbitrary() is inconsistent with equals and uses object identity instead, which makes it not a good idea to use it in conjunction with a TreeSet.

我想指出替代的建议解决方案，即“创建一个 TreeMultimap 并使用 Ordering.arbitrary() 作为值的比较器”，仅当 MyObject 不覆盖 equals() 或 hashcode() 时才有效。Ordering.arbitrary() 与 equals 不一致，而是使用对象标识，这使得将它与 TreeSet 结合使用不是一个好主意。

回答by justkt

You can do it with TreeMultimapif you use Comparators.

如果您使用比较器，则可以使用TreeMultimap来完成。

Create a Comparatorfor the key type and the value type (MyObject?). Then use create(Comparator keyComparator, Comparator valueComparator)to make the map.

为键类型和值类型 ( ?)创建一个ComparatorMyObject。然后使用create(Comparator keyComparator, Comparator valueComparator)制作地图。

The benefit of using a Comparator over implementing Comparable is that you can make the Comparator specific to the situation that you want with the map and it doesn't effect your object in general. As long as your Comparator is consistent with equals it can do whatever you want.

与实现 Comparable 相比，使用 Comparator 的好处是您可以使 Comparator 特定于您想要的地图情况，并且它通常不会影响您的对象。只要您的 Comparator 与 equals 一致，它就可以为所欲为。

回答by Paul Blessing

How about this:

这个怎么样：

    public static Multimap<Integer, MyObject> indexOnScore(Iterable<MyObject> i) {
        Multimap<Integer, MyObject> m = Multimaps.index(i, myObjectToScore());

        Multimap<Integer, MyObject> sortedKeys = Multimaps.newMultimap(
                Maps.<Integer, Collection<MyObject>>newTreeMap(),
                new Supplier<Collection<MyObject>>() {
                    @Override
                    public Collection<MyObject> get() {
                        return Lists.newArrayList(); // Or a Set if appropriate
                    }
                }
        );

        sortedKeys.putAll(m);

        return sortedKeys;
    }

There would be the overhead of creating two separate Multimaps in this case, though.

Multimap但是，在这种情况下创建两个单独的s会产生开销。

回答by Rahul k

Best solution which always works for me is to use Multimap & TreeMultiMap. this will order results in ascending order on keys even if you have multiple duplicate keys. Solution below:

始终对我有用的最佳解决方案是使用 Multimap 和 TreeMultiMap。即使您有多个重复的键，这也会对键的结果进行升序排序。解决方法如下：

Multimap<Double, Integer> map= TreeMultimap.create(Ordering.natural().reverse(),         Ordering.natural());

if (!map.isEmpty()) {               
                printMap(map);
            }

public static <K, V> void printMap(Multimap<Double, Integer> map) throws Exception {
        for (Map.Entry<Double, Integer> entry : map.entries()) {
            System.out.println("Key : " + entry.getKey() 
                + " Value : " + entry.getValue());              
        }
    }