19

If we have Student and Course entity and the relationship between them is many to many i.e a Student can take many courses and a course can be taken by many students. If we have to represent this relationship what is the best data structure through which we can represent this relationship. If we use hashmap with student as the key and list of courses that student took as the value then we need another hashmap through which we can represent course to student relationship. Are there any best ways to represent this relationship so that searching is fast.

Vaishu13
  • 435
  • 7
  • 16
  • 1
    possible duplicate of [Java many to many association map](http://stackoverflow.com/questions/2571652/java-many-to-many-association-map), [Model structure in many to many relationship](http://stackoverflow.com/questions/14219954/model-structure-in-many-to-many-relationship) – rid Jul 19 '15 at 07:06
  • http://stackoverflow.com/questions/473862/is-there-a-many-to-many-collection-in-java-using-generics-domain-model-not-per – assylias Jul 19 '15 at 07:25
  • Tree is what you need here – Ankur Anand Jul 19 '15 at 09:59
  • I looked at both the links but the first one is more related to hibernate and the second one is using Map. I have already mentioned in my question that I am not looking for a Map implementation. I am not sure how a tree would solve this problem – Vaishu13 Jul 19 '15 at 11:45
  • You can try and use a general directed acyclic graph. – poorvank Jul 20 '15 at 07:10
  • i think it is the best answer.You can use BidiMap in Apache Commons Collections library.You can map key-to-value also value-to-key: http://stackoverflow.com/questions/1383797/java-hashmap-how-to-get-key-from-value – Sarkhan Dec 18 '16 at 19:55

2 Answers2

8

I think it's appropriate to use a combination of data structures. Here is a small example: 

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

And here is an example usage:

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
  • 992
  • 11
  • 26
1

A bi-directional graph can be used to implements many-to-many relationship where each node can be connected to many other nodes

Dhruv Singh
  • 2,185
  • 2
  • 11
  • 17