如何在Java中实现多重映射功能？

Question

我希望在Java中拥有MultiMap的功能，提供与cpp MultiMap相同的功能，以便我可以拥有具有相同值的多个键。容器中的多个元素可以具有等效的键。我认为这将起作用：

TreeMap<Key, TreeMap<Key, Value> >. 

非常感谢您的帮助。

- rt56

---

Guava拥有多重映射的实现。 - Andy Turner

Apache Commons也。http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/MultiMap.html - markspace

你需要将多个键映射为相同的值，或者将多个值映射为相同的键吗？ - Razib

@Razib：是的，我两种方式都需要。而且我不能使用Guava和其他工具包。我需要在Java中实现它。 - rt56

@rt56，Guava确实是Java中的一部分。或者你的意思是你不能使用外部库吗？ - Vivin Paliath

@VivinPaliath 是的，我不能使用外部库。 - rt56

Answer 1

如果您想要一致的语义，您需要自己制定。实现的最简单方法是使用一个支持多个值的Map<K, List<V>>。这样您就可以将一个键映射到多个值。

但是，关于语义，您需要考虑一些事情。例如，假设您有以下multimap：

a -> [1, 2, 3]
b -> [4, 5]

以上示例的大小将被报告为2，但如果您考虑到Map可以表示为以下形式，则也可以解释为5：

a -> 1
a -> 2
a -> 3
b -> 4
b -> 5

这也会影响到你返回的值。返回[1, 2, 3, 4, 5]而不是[[1, 2, 3], [4, 5]]更有意义。这也适用于entry set; 您可能希望返回如上所示的键值对。

因此，一个可能的实现方式是实现Map<K, V>并使用支持的Map<K, List<V>>。然后，您将不得不实现各种方法，同时遵守multimap语义。

如果您不关心语义，但只想将单个键映射到多个值，则可以直接使用Map<K, List<V>>，仍然可以获得所需的结果。

- Vivin Paliath

---

但是让我们看一个场景，我想为同一个值拥有多个键。使用这种实现方式，我必须在所有的值中进行搜索。比如说，A映射到[1,2,3]，B映射到[2]。现在我想知道具有值2的键，应该是A和B两个。 总的来说，这种方法并不适用于双向映射。 - rt56

@rt56 这是一个双向映射表，或者在这种情况下是一个双向多重映射表，它与普通的多重映射表不同。要使其工作，您还必须维护从值到键的后备。 - Vivin Paliath

Answer 2

Vivin Paliath的回答是正确的。我会添加更多信息和代码。

Map#computeIfAbsent

要将多个值与一个键配对，请使用集合作为值类型。通常，集合是List或Set。或者对于更复杂的结构，可以使用Map。

例如，假设我们想跟踪哪些员工将在一周的哪些日子工作。

我们将Employee定义为记录。

record Employee( int empNum , String name ) { }

创建一些样本数据。

Employee alice = new Employee( 1 , "Alice" );
Employee bob = new Employee( 2 , "Bob" );
Employee carol = new Employee( 3 , "Carol" );

每个员工都映射到一组星期几值。对于星期几，我们可以使用在java.time.DayOfWeek上定义的枚举对象。因此，我们需要一个Map < Employee, Set < DayOfWeek > >。

Map < Employee, Set < DayOfWeek > > workDaysForEachEmployee = new HashMap <>();

假设我们想要将星期一分配给爱丽丝。

在早期的Java中

这是旧的方法来进行分配。我们尝试检索现有的集合值。我们进行空值检查，以查看是否确实存在现有的集合值。如果是这样，我们就添加到它，并将其放回到映射中。如果没有，我们实例化一个新的集合，添加到其中，并将其放入映射中。

Set < DayOfWeek > assignedDays = workDaysForEachEmployee.get( alice );
if ( null == assignedDays )
{
    assignedDays = EnumSet.noneOf( DayOfWeek.class );
}
assignedDays.add( DayOfWeek.MONDAY );
workDaysForEachEmployee.put( alice , assignedDays );

运行时。

workDaysForEachEmployee.toString() = {Employee[empNum=1, name=Alice]=[MONDAY]}

在现代的Java 8+

现代的Java引入了lambdas，这是一种将代码作为参数传递的紧凑方式。

我们可以使用lambdas和其他新的Java 8功能将上面看到的代码减少到一行。

我们调用Map#computeIfAbsent。在这个调用中，我们传递一个lambda。这个lambda创建一个集合来保存值。如果map已经有了一个包含所需集合的条目，那么lambda就不会被执行。无论如何，这个computeIfAbsent方法都会返回一个集合值，在我们的例子中是Set< DayOfWeek >。

• 如果集合值存在（已经映射到一个键），则返回该值。在我们的情况下，如果员工已经被放入具有一组天数的映射中，则检索并返回该集合。
• 如果集合值不存在，则实例化一个新的集合并返回。

无论哪种情况，预先存在或新实例化，我们最终都会得到一个集合，用于添加我们的DayOfWeek对象，以便为alice键设置。

workDaysForEachEmployee
        .computeIfAbsent( alice , ( x -> EnumSet.noneOf( DayOfWeek.class ) ) )  // Returns a `Set< DayOfWeek >`, either a retrieved existing set, or a fresh new set. 
        .add( DayOfWeek.MONDAY );

在上面的代码中，我们通过调用EnumSet.noneOf(DayOfWeek.class)来实例化一个新的集合。 EnumSet类是Set的一种实现，高度优化以包含枚举对象，使用非常少的内存，并且执行速度非常快。 如果您使用另一种类型，例如List，则可以使用new ArrayList<>()。 workDaysForEachEmployee.toString() = {Employee[empNum=1, name=Alice]=[MONDAY]}

- Basil Bourque

Answer 3

我认为在这种情况下guava BiMap是最好的选择。既然您不想使用它，那么您可以创建自己的集合 - TwoWayHashMap之类的东西：

public class TwoWayHashmap<K extends Object, V extends Object> {

  private Map<K,V> forward = new Hashtable<K, V>();
  private Map<V,K> backward = new Hashtable<V, K>();

  public synchronized void add(K key, V value) {
    forward.put(key, value);
    backward.put(value, key);
  }

  public synchronized V getForward(K key) {
    return forward.get(key);
  }

  public synchronized K getBackward(V key) {
    return backward.get(key);
  }
}

请访问附加链接以获取更多详细信息。

- Razib

---

OP说他不能使用Guava。 - Vivin Paliath