在Java中拥有一个仅按键排序的Multimap

Question

在Java中拥有一个仅按键排序的Multimap

26

我想要一个基于键进行排序的 c.g.c.c.Multimap，但值不应该被排序。我尝试使用 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中的现有（尚未发现的）功能，而不是使用这种hack。

注意：我不会让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

- Olivier Grégoire

1

你能给出一个输入/输出的例子吗？ - ant

你看过 http://download.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html 吗？ - Dan

@Dan：是的，我知道那个类，但我在这里说的是Guava的Multimap，而不是Map。 - Olivier Grégoire

c.g.c.c是什么？请不要在问题中使用这样的缩写。 - NomadMaker

8个回答

17

MultimapBuilder 在 Guava 16 中被引入：

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

这将按照自然顺序对您的键进行排序（MultimapBuilder :: treeKeys 还重载了一个接受自定义比较器的函数），并且与每个键相关联的值将保留在 LinkedList 中（ArrayList 和 HashSet 是其他选项之一）。

- gdejohn

8

虽然 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);
            }
        });
}

- Trevor Robinson

4

调用Multimaps.newMultimap，它可以让你灵活地创建一个Multimap，例如，支持TreeMap且值为ArrayLists的Multimap。

- Jared Levy

很有趣看到你写了Multimaps代码，但似乎没有人注意到。 - nsawaya

2

我想指出，另一个提出的解决方案，即"创建一个TreeMultimap，并将Ordering.arbitrary()用作值的比较器"，只有在MyObject没有覆盖equals()或hashcode()方法时才有效。Ordering.arbitrary()与equals不一致，使用对象标识，这使得它与TreeSet一起使用不是一个好主意。

- GFonte

1

这样怎么样：

    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会增加额外的开销。

- Paul Blessing

正如你所说，创建两个不同的Multimap太麻烦了。 - Olivier Grégoire

是的，我也更喜欢@ColinD的答案。 - Paul Blessing

1

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

为键类型和值类型（MyObject？）创建Comparator。然后使用create(Comparator keyComparator, Comparator valueComparator)创建地图。

使用比较器而不是实现Comparable的好处是，您可以使比较器特定于您想要的地图情况，并且它不会影响您的对象。只要您的比较器与equals一致，它可以执行任何您想要的操作。

- justkt

1

我并不真的喜欢这个。我说MyObject实现Comparable没有意义。这个声明的延伸是，逻辑上我也没有一个“默认”的MyObject比较器。我的目标真的是要有一个按其键排序的Multimap，但其键的值不应该被排序。 - Olivier Grégoire

0

对我来说，最好的解决方案是使用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());              
        }
    }

- Rahul k

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ColinD · Accepted Answer

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

另一个选择可能是创建一个 TreeMultimap，并将 Ordering.arbitrary() 用作值的 Comparator。