Java many to many association map

问题:

I have two classes, ClassA and ClassB, as well as a "many to many" AssociationClass. I want a structure that holds the associations between A and B so that I can find the counterpart for each instance of A or B.

I thought of using a Hashmap, with pair keys:

Hasmap<Pair<ClassA, ClassB>, AssociationClass> associations;

This way, I can add and remove an association between two instances of ClassA and ClassB, and I can query a relation for two given instances.

However, I miss the feature of getting all associations defined for a given instance of ClassA or ClassB.

I could do it by brute force and loop over all keys of the map to search for associations between a given instance, but this is inefficient and not elegant.

Do you know of any data structure / free library that enables this? I don't want to reinvent the wheel.

NB: This is not a "database" question. These objects are pure POJO used for live computation, I don't need persistence stuff.

回答1:

Here's my implementation based on guava Multimap:

public class ImmutableBiMultimap<K, V> {
    private final ImmutableSetMultimap<K, V> kToV;
    private final ImmutableSetMultimap<V, K> vToK;

    public ImmutableBiMultimap (SetMultimap<K, V> keyToValueMap) {
        kToV = ImmutableSetMultimap.copyOf(keyToValueMap);

        SetMultimap<V, K> valueToKeyMap = HashMultimap.create();
        for (Entry<K, V> entry : kToV.entries()) {
            valueToKeyMap.put(entry.getValue(), entry.getKey());
        }

        vToK = ImmutableSetMultimap.copyOf(valueToKeyMap);
    }

    public ImmutableSet<V> getValuesForKey(K key) {
        return kToV.get(key);
    }

    public ImmutableSet<K> getKeysForValue(V value) {
        return vToK.get(value);
    }
}

回答2:

Thanks for your suggestions.

I finally reinvented the wheel ... I have written a generic class for holding associations. I use two maps of maps, synchronized.

The associations holder provides the following methods

void setAssociation(LeftClass left, RightClass right, AssociationClass assoc);
AssociationClass getAssociation(LeftClass left, RightClass right);
Map<RightClass, AssociationClass> getAssocationsLeft(LeftClass left);
Map<LeftClass, AssociationClass> getAssocationsRight(RightClass right); 
void removeAssociation(LeftClass left, RightClass right);

Here is the code:

import java.util.HashMap;

/** This class holds many to many associations between two classes. */
public class AssociationHolder<LeftClass, RightClass, AssociationClass> {

    // -------------------------------------------------------
    // Attributes
    // -------------------------------------------------------

    private HashMap<LeftClass, HashMap<RightClass, AssociationClass>> associationsLeft = 
        new HashMap<LeftClass, HashMap<RightClass,AssociationClass>>();
    private HashMap<RightClass, HashMap<LeftClass, AssociationClass>> associationsRight = 
        new HashMap<RightClass, HashMap<LeftClass,AssociationClass>>();     

    // -------------------------------------------------------
    // Methods
    // -------------------------------------------------------

    /** 
     *  Set an association between two instance.
     *  Any prior association is overwritten.
     */
    public void setAssociation(LeftClass left, RightClass right, AssociationClass association) {

        // Get the map for the left 
        HashMap<RightClass, AssociationClass> leftMap = this.associationsLeft.get(left);

        // No association defined yet for this left key ? => Create new map
        if (leftMap == null) {
            leftMap = new HashMap<RightClass, AssociationClass>();
            this.associationsLeft.put(left, leftMap);
        }

        // Get the map for the right 
        HashMap<LeftClass, AssociationClass> rightMap = this.associationsRight.get(right);

        // No association defined yet for this right key ? => Create new map
        if (rightMap == null) {
            rightMap = new HashMap<LeftClass, AssociationClass>();
            this.associationsRight.put(right, rightMap);
        }

        // Set the assoication on both maps
        leftMap.put(right, association);
        rightMap.put(left, association);        

    } 

    /** @return null if no association found. */
    public AssociationClass getAssociation(LeftClass left, RightClass right) {

        // Use left maps (could have used the right one as well)
        HashMap<RightClass, AssociationClass> leftMap = this.associationsLeft.get(left);
        if (leftMap == null) return null;
        return leftMap.get(right);
    }

    /** Get all associations defined for a given Left instance.  */
    public HashMap<RightClass, AssociationClass> getAssociationsLeft(LeftClass left) {

        HashMap<RightClass, AssociationClass> leftMap = this.associationsLeft.get(left);

        // No map defined ? return empty one instead of null
        if (leftMap == null) {
            return new HashMap<RightClass, AssociationClass>();
        } else {
            return leftMap;
        }   
    }

    /** Get all associations defined for a given Right instance.  */
    public HashMap<LeftClass, AssociationClass> getAssociationsRight(RightClass right) {

        HashMap<LeftClass, AssociationClass> rightMap = this.associationsRight.get(right);

        // No map defined ? return empty one instead of null
        if (rightMap == null) {
            return new HashMap<LeftClass, AssociationClass>();
        } else {
            return rightMap;
        }   
    }

    /** 
     *  Remove an association between two instances.
     */
    public void removeAssociation(LeftClass left, RightClass right) {
        HashMap<RightClass, AssociationClass> leftMap = this.getAssociationsLeft(left);
        HashMap<LeftClass, AssociationClass> rightMap = this.getAssociationsRight(right);
        leftMap.remove(right);      
        rightMap.remove(left);  
    }
}

I hope this can help someone in the future.

回答3:

Maybe the Multimap or the BiMap from the Google Collections Library can do what you need.

回答4:

This looks like a problem in which you have data that you want to get using multiple keys. You want to search by ClassA and also by ClassB. This usually leads to multiple maps atop the data so that each map keeps a search key into the underlying data. Perhaps something like this would work:

public class Data {

  public ClassA a;
  public ClassB b;
  public AssociationClass association;

}

Map<ClassA, Data> aData;
Map<ClassB, Data> bData;
Map<AssociationClass, Data> associationData;

Inserting goes like this:

Data data = new Data()

aData.put(data.a, data);
bData.put(data.b, data);
associationData.put(data.association, data);

Getting the data you can query each of the maps to get what you want. You can even have your Pair class as another index into the data:

Map<Pair<ClassA, ClassB>, Data> pairData;

The problem with this approach is that if the underlying data changes a lot you must make sure that all maps are in sync. If this is mostly a readonly problem then you create the maps and then just query the one with your key into the data.

回答5:

Using your AssociationClass, you could just have ClassA and ClassB both contain a reference to AssociationClass:

private AssociationClass association;

Or, a different method...

ClassA can contain:

private List<ClassB> classBList;

and ClassB can contain:

private List<ClassA> classAList;

By implementing this, you can access your associations from within the associated class.

回答6:

rmarimon is right that it requires two maps, but I think you want A-B, not A-data and B-data.

So you just simply need two maps:

    Hashmap bByA = new HashMap();
    Hashmap aByB = new HashMap();

This gives you everything you seem to want, free and easy.

回答7:

Why not put a map in each class?

class ClassA {
    ...
    private Map<ClassB, AssociationClass> associations
            = HashMap<ClassB, AssociationClass>();
    ...
}

class ClassA {
    ...
    private Map<ClassA, AssociationClass> associations
            = HashMap<ClassB, AssociationClass>();
    ...
}