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

data-structures collections java

2022-09-03 02:51:54

如果我们有学生和课程实体，并且它们之间的关系是多对多的，即学生可以参加许多课程，而一门课程可以由许多学生参加。如果我们必须表示这种关系，那么我们可以表示这种关系的最佳数据结构是什么。如果我们使用以学生为键的哈希图，并将学生作为值的课程列表，那么我们需要另一个哈希图，通过该哈希图，我们可以表示课程与学生的关系。是否有任何最佳方法来表示这种关系，以便快速搜索。

答案 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

答案 2

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