Tips on multiple key Map-wrapper

I'm creating a simple generic Map-wrapper with multiple keyed values.

I'm intending to use it with storing edges in a graph, where an edge goes from one vertex to another. Thus, I can fetch any of the two vertices in constant time instead of having to loop to find either to/from.

public class MultiMap {

    private Map map1;
    private Map map2;

    /**
     * @param map1
     * @param map2
     */
    public MultiMap() {
        this.map1 = new HashMap();
        this.map2 = new HashMap();
    }

    public void put(K1 key1, K2 key2, V value) {
        this.map1.put(key1, value);
        this.map2.put(key2, value);
    }

    ...

    public V removeByKey1(K1 key) {
        V res = this.map1.remove(key);
        K2 k = null;
        for (Map.Entry entry : this.map2.entrySet()) {
            if (entry.getValue() == res) {
                k = entry.getKey();
                break;
            }
        }
        this.map2.remove(k);
        return res;
    }

    public V removeByKey2(K2 key) {
        V res = this.map2.remove(key);
        K1 k = null;
        for (Map.Entry entry : this.map1.entrySet()) {
            if (entry.getValue() == res) {
                k = entry.getKey();
                break;
            }
        }
        this.map1.remove(k);
        return res;
    }

    ...
}

Is there better way of removing? E.g. using LinkedHashMap and then using the key index to do it in constant time instead of linear?

If there's something else not sitting right with you, tell me. All feedback appreciated.

Some notes about the current code:

-
extends Objects looks unnecessary in the class declaration:

public class MultiMap {

I'm not completely sure but the following seems to be the same:

public class MultiMap {

-
I'd rename res to oldValue or something more descriptive.

-
Modern IDEs use highlighting to separate local variables from fields, so don't need to use this.. It's rather noise.

-
Comments like this are just noise:

/**
 * @param map1
 * @param map2
 */

It doesn't say anything more than the code says. Furthermore, the constructor does not have any parameter like map1 or map2. (Clean Code by Robert C. Martin: Chapter 4: Comments, Noise Comments)

StackExchange Code Review Q#27148, answer score: 2