Mapping MultiMaps with Hibernate

Maarten Winkels

Hibernate is a very complete ORM library. One of the few ommisions is the possibility to map collections of collections. In this blog this omission is investigated and a solution is provided for the specific case of a Map of Sets.

Collection of Collections

Let's first take a look at a simple collection mapping. Here a person has a list of friends.

public class Person {
    private List friends;
}

    ...
    
        
        
        
    


...

This will lead to the following tables:

Person
ID
1
Friend
ID PERSON_FK POS
1 1 0
2 1 1

The Friend table has a foreign key to the Person table (PERSON_FK) and it also contains a column with the index in the list (POS). This is a very common mapping (There are other ways to model this in the database schema, but that is not relevant for this discussion).

Now let's say we want the Person-Friend relation to be a bit more specific. We have groups of friends, that have a certain common source, like relatives, schoolmates or any other type.

public class Person {
    private Map> friends;
}

The collection has turned from a simple collection into a collection of collections. The relationship did not necessarily change from one-to-many to many-to-many. I choose to model the relation as one-to-many in the first situation (rather weird to think that a Friend is only your Friend!) so we can leave that like this as well.

There would be a very simple change in table layout that could accomodate this new situation:

Person
ID
1
Friend
ID PERSON_FK POS SOURCE
1 1 0 CLASS_MATE
2 1 1 CLASS_MATE
3 1 0 RELATIVE

Only the Friend table has changed. The SOURCE column determines the key for the Map and the POS column determines the index in the list. The unique key on the Friend table has changed, though.

There is no way to configure Hibernate to handle this situation. The mapping would have to allow both a map-key and an index element, but it doesn't. The only way for Hibernate to work with this is to introduce a new Entity; FriendGroup.

public class Person {
    private Map groups;
}
public class FriendGroup {
    private List friends;
}

    ...
    
        
        
    


    ...
    
        
        
        
    


...
Person
ID
1
FriendGroup
ID PERSON_FK SOURCE
1 1 CLASS_MATE
2 1 RELATIVE
Friend
ID GROUP_FK POS
1 1 0
2 1 1
3 2 0

The new entity is mapped to a new table. The rationale behind this is that an Entity has identity (PK column in database and id field in code). A collection has no identity but belongs to an Entity. Collection elements have a foreign key to the primary key (identity) of the owner of the collection. For a collection of collections, the elements in the ultimate collection have no identity to point to, since the collection is not owned by an Entity, but by another collection. By introducing a new Entity, which is basically an identifier with a collection, we return to the simple situation.
The same holds for components. A component has no identity and therefore can not contain a collection, since there would be no identity to point to.

Introducing the concept of recursive collections (collections of collections) in Hibernate will be rather tricky. It touches upon a large part of the library. There is one case in which the problem can be resolved by simple means, this is in the case of a Map of Sets.

Map of Sets

Let's say we have Persons and Orders and a Person has many orders and each order has a certain PaymentStatus.

public class Person {
    private Map> ordersByPaymentStatus;
}

Using the above code would still be rather hard with Hibernate, so we'll turn to the Apache commons-collections library for a convenient class

public class Person {
    private MultiMap ordersByPaymentStatus;
}

N.B.: We have to drop the generic parameters to the interface. The MultiMap extends the general Map interface but not the generic Map interface. The put method allows for simple values, but the get method returns a collection (list) of these values.

The MultiMap will maintain a list of items (values) for each key, but we will not worry about the order in those lists, and interact with them as simple java.util.Collections.

Because the implementation of the collection that we want to use (MultiHashMap) differs from the normal Map implementation that Hibernate uses (HashMap), we have to create a UserCollectionType. This is one of the interfaces that Hibernates provides for extension. This interface basically describes how Hibernate will interact with any collection implementation. The implementation of this UserCollectionType is pretty straightforward.

public class MultiMapType implements UserCollectionType {

    public boolean contains(Object collection, Object entity) {
        return ((MultiMap) collection).containsValue(entity);
    }

    public Iterator getElementsIterator(Object collection) {
        return ((MultiMap) collection).values().iterator();
    }

    public Object indexOf(Object collection, Object entity) {
        for (Iterator i = ((MultiMap) collection).entrySet().iterator(); i.hasNext();) {
            Map.Entry entry = (Map.Entry) i.next();    
            Collection value = (Collection) entry.getValue();
            if (value.contains(entity)) {
                return entry.getKey();
            }
        }
        return null;
    }

    public Object instantiate() {
        return new MultiHashMap();
    }

    public PersistentCollection instantiate(SessionImplementor session, CollectionPersister persister) throws HibernateException {
        return new PersistentMultiMap(session);
    }

    public PersistentCollection wrap(SessionImplementor session, Object collection) {
        return new PersistentMultiMap(session, (MultiMap) collection);
    }

    public Object replaceElements(Object original, Object target, CollectionPersister persister, Object owner, Map copyCache, SessionImplementor session) throws HibernateException {

        MultiMap result = (MultiMap) target;
        result.clear();
        
        Iterator iter = ( (java.util.Map) original ).entrySet().iterator();
        while ( iter.hasNext() ) {
            java.util.Map.Entry me = (java.util.Map.Entry) iter.next();
            Object key = persister.getIndexType().replace( me.getKey(), null, session, owner, copyCache );
            Collection collection = (Collection) me.getValue();
            for (Iterator iterator = collection.iterator(); iterator.hasNext();) {
                Object value = persister.getElementType().replace( iterator.next(), null, session, owner, copyCache );
                result.put(key, value);
            }
        }
        
        return result;
    }
    
}

The first two methods are very simple and will probably be the same for every collection implementation. Note that the values() method of MultiHashMap will flatten the collection and return an iterator that will iterate over all values in the lists.
For a MultiMap to implement the indexOf(...) method we will have to inspect the list that is associated with the key to see if it contains the specified element.
The instantiate(...) and wrap(...) methods are related. The parameterless instantiate() method must return an implementation of the non-persistent collection type, in our case MultiHashMap. The second instantiate method must return a PersistentCollection. This is a specialized Hibernate collection, that knows how to persist collections of this Type. We will come back to this in greater detail later. The wrap(...) method will be used by Hibernate to transform a non-persistent collection into a persistent collection. The difference between the last two methods is that the wrapped collection is backed by the collection passed in and therefore already initialized, while the instantiated collection is used to load a new collection possibly lazily and therefore not yet initialized.
The replaceElements(...) method will copy the content from the original to the target, using the types for key and value to copy those objects. This implementation has to iterate both the map and the collections that are values in the map to copy each key and value in turn.

Persisting a MultiMap is very similar to persisting a normal Map. The only difference is that the values in the MultiMap are collections. Hibernate cannot handle collections as values, so we need to implement a specialized PersistentMultiMap. You can find the sources for both classes described here as attachements to this blog.

public class PersistentMultiMap extends PersistentMap implements MultiMap {
{

    public PersistentMultiMap(SessionImplementor session, MultiMap map) {
        super(session, map);
    }

    public PersistentMultiMap(SessionImplementor session) {
        super(session);
    }

The PersistentMultiMap extends PersistentMap because its behaviour is very similar to the Map. It also implements the MultiMap interface, so it can be substituted for MultiMap collections in entity objects. Because of this interface we have to implement one additional method:

    public Object remove(Object key, Object item) {
        Object old = isPutQueueEnabled() ? readElementByIndex(key) : UNKNOWN;
        if (old == UNKNOWN) {
            write();
            return ((MultiMap) map).remove(key, item);
        } else {
            queueOperation(new RemoveItem(key, item));
            return old;
        }
    }

    private class RemoveItem implements DelayedOperation {

        private final Object key;

        private final Object item;

        private RemoveItem(Object key, Object item) {
            this.key = key;
            this.item = item;
        }

        public Object getAddedInstance() {
            return null;
        }

        public Object getOrphan() {
            return item;
        }

        public void operate() {
            ((MultiMap) map).remove(key, item);
        }

    }

The remove(Object key, Object item) method is the only addition of the MultiMap to the Map interface. It removes the item from the collection that is keyed by the key. The implementation is mostly copied from any of the collection operations in the PersistentCollections. The DelayedOperation mechnism is used by Hibernate to support operations on not fully initialized collections.

One of the most important changes to the behaviour in the PersistentMap is the entries(...) method. This method is used by Hibernate to iterate all elements (both key and value). In the case of a MultiMap we have to provide an iterator that will return all the values in the collections in the MultiMap, together with the key that the collection is bound to as a Map.Entry. To this end we introduce a new implementation of the Iterator interface.

    @Override
    public Iterator entries(CollectionPersister persister) {
        return new KeyValueCollectionIterator(super.entries(persister));
    }

    private final static class KeyValueCollectionIterator implements Iterator {

        private final Iterator parent;

        private Object key;

        private Iterator current;

        private KeyValueCollectionIterator(Iterator parent) {
            this.parent = parent;
            move();
        }

        public boolean hasNext() {
            return key != null;
        }

        public Object next() {
            if (key == null) {
                throw new NoSuchElementException();
            } else {
                DefaultMapEntry result = new DefaultMapEntry(key, current.next());
                if (!current.hasNext()) {
                    move();
                }
                return result;
            }
        }

        private void move() {
            while (this.parent.hasNext()) {
                Map.Entry entry = (Entry) this.parent.next();
                key = entry.getKey();
                current = ((Collection) entry.getValue()).iterator();
                if (current.hasNext()) {
                    return;
                }
            }
            key = null;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

    }

The rest of the class is concerned with dirty checking. To do dirty checking and lazy updates, Hibernate keeps a snapshot of all entities and collections that are loaded from the database into memory. At flush time the cuirrent state of the objects in memory is compared with the snapshot state and differences are persisted to the database. The snapshot is created by the getSnapshot(CollectionPersister persister) method. While taking a snapshot, deep copies have to be made of all values in the collection. The snapshot is another MultiMap.

    @Override
    public Serializable getSnapshot(CollectionPersister persister) throws HibernateException {
        EntityMode entityMode = getSession().getEntityMode();

        MultiHashMap clonedMap = new MultiHashMap(map.size());
        Iterator iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry e = (Map.Entry) iter.next();
            Collection collection = (Collection) e.getValue();
            for (Iterator i = collection.iterator(); i.hasNext();) {
                final Object copy = persister.getElementType().deepCopy(i.next(), entityMode, persister.getFactory());
                clonedMap.put(e.getKey(), copy);
            }
        }
        return clonedMap;
    }

The snapshot is held in the session and can be fetched through the getSnapshot() method. The equalsSnapshot(...), getDeletes(...), needsInserting(...) and needsUpdating(...) methods are used to check the differences.
The equalsSnapshot(...) is used as a shortcut to determine whether further dirty checking is necessary.
The getDeletes(...) method must return an iterator over either the keys or the values that are removed from the collection. These values are not necessarily removed from the database, but the relation between the two entities (collection owner and value) will be removed. Note that in this implementation items that have moved in the map will also be returned. A move will be regarded by a remove and insert by this implementation (this is also the case in the standard PersistentMap implementation from Hibernate).
The needsInserting(...) and needsUpdating(...) check the snapshot for the collection that is associated with the same key as the entry that is to be checked. The implementation relies on a correctly implemented equals(...) and hashCode() method on the entity type (as does a lot of Hibernate code).

    @Override
    public boolean equalsSnapshot(CollectionPersister persister) throws HibernateException {
        Map sn = (Map) getSnapshot();
        if (sn.size() != map.size())
            return false;
        Type elemType = persister.getElementType();
        for (Iterator i = sn.entrySet().iterator(); i.hasNext();) {
            Map.Entry entry = (Map.Entry) i.next();
            Map oldState = getCollectionAsIdentityMap((Collection) entry.getValue());
            Collection newState = (Collection) map.get(entry.getKey());
            for (Iterator iter = newState.iterator(); iter.hasNext();) {
                Object newValue = iter.next();
                Object oldValue = oldState.get(newValue);
                if (newValue != null && oldValue != null && elemType.isDirty(oldValue, newValue, getSession())) {
                    return false;
                }
            }
        }
        return true;
    }

    private Map getCollectionAsIdentityMap(Collection collection) {
        Map map = new HashMap();
        for (Iterator iter = collection.iterator(); iter.hasNext();) {
            Object element = iter.next();
            map.put(element, element);
        }
        return map;
    }

    @Override
    public Iterator getDeletes(CollectionPersister persister, boolean indexIsFormula) throws HibernateException {
        Set result = new HashSet();
        Map sn = (Map) getSnapshot();
        for (Iterator i = sn.entrySet().iterator(); i.hasNext();) {
            Map.Entry entry = (Entry) i.next();
            Collection oldState = (Collection) entry.getValue();
            Collection newState = (Collection) map.get(entry.getKey());
            for (Iterator j = oldState.iterator(); j.hasNext();) {
                Object element = j.next();
                if (!(newState.contains(element))) {
                    result.add(element);
                }
            }
        }
        return result.iterator();
    }

    @Override
    public boolean needsInserting(Object entry, int i, Type elemType) throws HibernateException {
        Map.Entry e = (Entry) entry;
        Map sn = (Map) getSnapshot();
        Collection oldState = (Collection) sn.get(e.getKey());
        return oldState == null || !oldState.contains(e.getValue());
    }

    @Override
    public boolean needsUpdating(Object entry, int i, Type elemType) throws HibernateException {
        Map.Entry e = (Entry) entry;
        Map sn = (Map) getSnapshot();
        Collection collection = (Collection) sn.get(e.getKey());
        if (collection == null) {
            return false;
        }
        for (Iterator iter = collection.iterator(); iter.hasNext();) {
            Object oldValue = iter.next();
            if (oldValue != null && oldValue.equals(e.getValue())) {
                return e.getValue() != null && elemType.isDirty(oldValue, e.getValue(), getSession());
            }
        }
        return false;
    }

}

Now this code can simply be used by adding a collection-type attribute to your Map in the Hibernate mapping.

  
    ...
    
      
      
      
    
  
  
    ...
  

Now the map will be kept in sync with the database state.

This code will also work for many-to-many associations or value maps. Unfortunately in these situations the HBM2DDL functionality in Hibernate will generate a unique constraint that prevents the Map from containing multiple values for the same key. If you do not use HBM2DDL but write your schema manually the code will work for you. The reason why Hibernate does not generate this unique constraint for one-to-many maps is that the foreign-key column for a one-to-many is normally in the childs entity column. Since children without a parent might be present in the database the unique constraint might pose problems in the case of multiple nulls.

Conclusion

Hibernate can be used to persist MultiMaps. This requires some custom code and a good understanding of how to extend Hibernate. Extending Hibernate to work with other types of recursive collections might be a lot more difficult.

Comments (10)

  1. Nicko Cadell - Reply

    January 3, 2008 at 5:25 pm

    Hi,

    This sounds like a great enhancement, however I can't find the sources for the classes that you say are attachments to this blog.

    Thanks,
    Nicko

  2. nfeybesse - Reply

    May 8, 2008 at 10:17 am

    Hi,

    Yes,

    It will be very nice if you could attach the source files of this enhancement !

    Thanks
    Nicolas

  3. Maarten Winkels - Reply

    June 3, 2008 at 10:16 pm

    Unfortunately, the attachements to this blog have been lost. The complete source code of the (2) classes needed for the mechanism described in this blog are included in the text of the blog.
    To use the code, simply cut and paste the classes together.

    Regards,

    Maarten Winkels

  4. Pat - Reply

    February 13, 2009 at 8:53 pm

    This seems so generally useful that it should be part of the standard hibernate package.

  5. Pat - Reply

    February 13, 2009 at 9:08 pm

    (Additional comment)

    You say that Map<string, list> cannot be handled, but then you prove that it can be. After all a list can be considered TreeMap This is actually better in hibernate than a regular list because:

    * sparse lists are now possible
    * the element indicies as storied in the db can have gaps to allow inserting new elements without renumbering all elements.

  6. prabu - Reply

    April 15, 2009 at 7:09 am

    Hi,

    I tried the Map of Sets solution.
    See below for the mapping. In spite of cascade option set the AclObject is not geting saved and
    i get the following errors
    "object references an unsaved transient instance - save the transient instance before flushing"

    Any pointers would be of great help

    Thanks

    ....

  7. prabu - Reply

    April 15, 2009 at 7:14 am

    Sorry the xml is ignored coz of spl chars
    Here it is..

    <class>
    ....
    <map name="acl" table="GROUP_OBJECTS" cascade="save-update,delete" collection-type="MultiMapType">
    <key column="GROUPID" />
    <map-key column="OBJECTTYPEID" type="objectType"/>
    <one-to-many class="AclObject" />
    </map>
    </class>

    <class name="AclObject" table="GROUP_OBJECTS" lazy="false">

    <id name="id" column="ID" type="java.lang.Integer">
    <generator class="increment"/>
    </id>

    <property name="groupId" column="USERGROUPID" type="java.lang.Integer" not-null="true"/>

    <property name="objectType" column="OBJECTTYPEID" type="objectType" not-null="true"/>

    <property name="objectId" column="OBJECTID" type="java.lang.String" not-null="true"/>

    </class>

  8. Brian - Reply

    December 15, 2009 at 11:28 pm

    Can anybody tell me how to use a java.lang.Integer as the mapped type, rather than some user-defined class?

  9. Peter - Reply

    February 18, 2010 at 10:20 pm

    Has anyone tried this with Maps ie: Map<key, Map>? I've been able to get Map<key, List> to work but would like to get the above to work as well. Any ideas?

  10. Mark - Reply

    July 13, 2011 at 9:58 am

    Hi,

    Thanks for this, it's been very useful. However, MultiMap.putAll doesn't work with the above code (it uses the existing PersistentMap.putAll that puts the value collections into the MultiMap rather than each key, value pair). The following works for me if added to PersistentMultiMap:

    /**
    * @see java.util.Map#putAll(java.util.Map puts)
    */
    @Override
    public void putAll(Map puts) {
    if ( puts.size()>0 ) {
    initialize( true );
    Iterator itr = puts.entrySet().iterator();
    while ( itr.hasNext() ) {
    Map.Entry entry = ( Entry ) itr.next();
    Collection collection = (Collection) entry.getValue();
    for( Object value : collection) {
    put( entry.getKey(), value );
    }
    }
    }
    }

Add a Comment