@Entity @Table(name="map_value")
public class MapValue {

    @Id @GeneratedValue @Column(name="id", unique=true, nullable=false)
    private Long id;

    @Column(name="name", unique=true, nullable=false)
    private String name;

//[...getters/setters...]

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((getName() == null) ? 0 : getName().hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if(this == obj) return true;
        if(obj == null || !(obj instanceof MapValue)) return false;
        MapValue other = (MapValue) obj;
        if(getName() == null) {
            if(other.getName() != null) {
                return false;
            }
        } else if(!getName().equals(other.getName())) {
            return false;
        }
        return true;
    }
}

@Entity
@Table(name="map_key", uniqueConstraints = {
        @UniqueConstraint(columnNames = {"name","default_map_value_id"})
})
public class MapKey {

    @Id @GeneratedValue @Column(name="id", unique=true, nullable=false)
    private Long id;

    @Column(name="name", nullable=false)
    private String name;

    @ManyToOne @JoinColumn(name="default_map_value_id", nullable=false)
    private MapValue defaultValue;

//[...getters/setters...]

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((getDefaultValue() == null) ? 0 : getDefaultValue().hashCode());
        result = prime * result + ((getName() == null) ? 0 : getName().hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if(this == obj) return true;
        if(obj == null || !(obj instanceof MapKey)) return false;
        MapKey other = (MapKey) obj;
        if(getDefaultValue() == null) {
            if(other.getDefaultValue() != null) {
                return false;
            }
        } else if(!getDefaultValue().equals(other.getDefaultValue())) {
            return false;
        }
        if(getName() == null) {
            if(other.getName() != null) {
                return false;
            }
        } else if(!getName().equals(other.getName())) {
            return false;
        }
        return true;
    }
}

@Entity @Table(name="map_holder")
public class MapHolder {

    @Id @GeneratedValue @Column(name="id", unique=true, nullable=false)
    private Long id;

    @ManyToMany
    @JoinTable(name="map_key_map_value",
        joinColumns=@JoinColumn(name="map_holder_id", nullable=false),
        inverseJoinColumns=@JoinColumn(name="map_value_id", nullable=false))
    @MapKeyJoinColumn(name="map_key_id", nullable=false)
    private Map<MapKey,MapValue> map;

//[...getters/setters...]
}

Session session = sessionFactory.openSession();
Transaction tx = session.beginTransaction();
MapHolder mapHolder = (MapHolder) session.get(MapHolder.class, mapHolderId);
// This passes - the map is not empty at this point:
assert(mapHolder.getMap().size() > 0);
MapValue mapValue = new MapValue();
mapValue.setName(valueString);
session.save(mapValue);
MapKey mapKey = new MapKey();
mapKey.setDefaultValue(mapValue);
mapKey.setName(keyString);
session.save(mapKey);
mapHolder.getMap().put(mapKey, mapValue);
tx.commit();
session.close();