仅在 Java 中按键排序 Multimap

Question

我想要一个仅根据键排序的 cgccMultimap 。不应对值进行排序。我尝试使用 guava 的 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;
  }
}

我考虑过获取键的 SortedSet ，然后迭代排序集中的每个键以获取各种值，但我希望使用 Guava 中现有的（尚未发现的）功能而不是使用这种黑客。

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

---

输入/输出示例：

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());
}

打印：

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

Answer 1

对我来说总是有效的最佳解决方案是使用 Multimap &树多重映射。即使您有多个重复的键，这也会按键的升序对结果进行排序。解决方案如下：

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());              
        }
    }

Answer 2

Multimaps.index 返回一个 ImmutableListMultimap，因此在创建它后您将无法对其进行排序。但是，您可以首先创建 Iterable 的排序副本，并将其提供给 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());
}

另一种选择可能是创建一个 TreeMultimap 并使用 Ordering.graduatery() 作为值的 Comparator。

Answer 3

MultimapBuilder是在 Guava 16 中引入的：

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

这使您的键按其自然顺序排序（MultimapBuilder::treeKeys 也被重载以接受自定义比较器），以及与每个键关联的值维护在 LinkedList 中（ArrayList 和 HashSet 是其他选项）。

Answer 4

尽管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);
            }
        });
}

Answer 5

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

Answer 6

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

Answer 7

怎么样：

    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;
    }

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

Answer 8

您可以使用 TreeMultimap 来完成此操作 如果您使用比较器。

创建一个 比较器 用于键类型和值类型（MyObject？）。然后使用 create(Comparator keyComparator, Comparator valueComparator) 来制作地图。

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