用于表示多对多关系的数据结构

Question

如果我们有学生(Student)和课程(Course)实体，它们之间的关系是多对多，即一个学生可以选修多门课程，一个课程也可以被多名学生选修。如果我们要表示这种关系，最好的数据结构是什么？如果我们使用哈希映射(HashMap)，以学生为键(key)，以学生所选课程的列表为值(value)，那么我们需要另一个哈希映射来表示课程到学生的关系。有没有更好的方法来表示这种关系，以便搜索更快。

- Vaishu13

---

可能是Java多对多关联映射的重复问题，多对多关系中的模型结构。 - rid

https://dev59.com/FnRB5IYBdhLWcg3w6LR2 - assylias

树是你在这里需要的。 - Ankur Anand

我查看了这两个链接，但第一个链接更相关于Hibernate，而第二个链接则使用Map。我已经在我的问题中提到，我不想要一个Map实现。我不确定一棵树如何解决这个问题。 - Vaishu13

你可以尝试使用通用的有向无环图。 - poorvank

我认为这是最好的答案。您可以在Apache Commons Collections库中使用BidiMap。您可以将键映射到值，也可以将值映射到键：https://dev59.com/fnM_5IYBdhLWcg3waiiJ - Sarkhan

Answer 1

我认为结合使用多种数据结构是恰当的。以下是一个小例子：

public class ManyToManyMap<S, C> {
    private Map<S, Set<C>> firstToSecondMap = new HashMap<>();

    private Map<C, Set<S>> secondToFirstMap = new HashMap<>();

    public void put(S first, C second) {
        if (!firstToSecondMap.containsKey(first)) {
            firstToSecondMap.put(first, new HashSet<>());
        }
        firstToSecondMap.get(first).add(second);

        if (!secondToFirstMap.containsKey(second)) {
            secondToFirstMap.put(second, new HashSet<>());
        }
        secondToFirstMap.get(second).add(first);
    }

    public Set<C> getFirst(S first) {
        return firstToSecondMap.get(first);
    }

    public Set<S> getSecond(C second) {
        return secondToFirstMap.get(second);
    }

    public Set<C> removeByFirst(S first) {
        Set<C> itemsToRemove = firstToSecondMap.remove(first);
        for (C item : itemsToRemove) {
            secondToFirstMap.get(item).remove(first);
        }

        return itemsToRemove;
    }

    public Set<S> removeBySecond(C second) {
        Set<S> itemsToRemove = secondToFirstMap.remove(second);
        for (S item : itemsToRemove) {
            firstToSecondMap.get(item).remove(second);
        }

        return itemsToRemove;
    }
}

下面是一个使用示例：

ManyToManyMap<String, String> mmMap = new ManyToManyMap<>();

mmMap.put("Tom", "Math");
mmMap.put("Tom", "Java");
mmMap.put("Tom", "Java");
mmMap.put("Mary", "Java");

Set<String> coursesByStudent = mmMap.getFirst("Tom"); // Java, Math
Set<String> studentByCourse = mmMap.getSecond("Java"); // Tom, Mary

mmMap.removeByFirst("Tom");
studentByCourse = mmMap.getSecond("Java"); // Mary

- dim

Answer 2

双向图可用于实现多对多关系，其中每个节点可以连接到许多其他节点。

- Dhruv Singh