Nested Maps or combined keys in java

问题:

I need a Map to make a cache in Java for same values that I have two String keys. My question it's better to make nested Maps (one for each key) or make some type of custom key maked with the two Strings?

Access to data on cache will all time accessed with the two keys and I don't need group it by any of that two keys.

Then if is better combine string key in only one what it's better?

• Custom class with custom getHash method. But then the problem is what hash function implement?

• Simply concatenate two strings together. For example:

  cache.put(key1+key2, value)

回答1:

You can either make nested maps or use a custom class defining hashCode().

It's usually not a good idea to concatenate the keys, you can end up with collisions, as in the case with keys 1 and 22 and keys 12 and 2. They'd map to the same value 122.

If you'll always use both keys, using a single Map will always be a little more efficient, and you can always define your own adapter to the map that will take two arguments:

public class MyCache { 

    private Map<MyKey, Object> cache = new HashMap<MyKey, Object>();

    public Object getObject(Object key1, Object key2){
        return cache.get(new MyKey(key1, key2));
    }
    public void putObject(Object key1, Object key2, Object value){
        cache.put(new MyKey(key1, key2), value);
    }
}

Remember to define equals() and hashCode() in your custom key class (add checks for nullity if needed).

public int hashCode() {
    int result = 17;
    result = 37 * result + keyA.hashCode();
    result = 37 * result + keyB.hashCode();
    return result;
}

public boolean equals(Object another) { 
    return another.keyA.equals(keyA) && another.keyB.equals(keyB);
} 

回答2:

You may want to consider Guava's Table classes. They implement a Map with two keys per value. This may provide a more readable solution than a composite key depending on your requirements.

Table<String, String, MyValue>

回答3:

it's better to make nested Maps (one for each key) or make some type of custom key maked with the two Strings?

A single hashtable with a composite key type may have better locality of reference. It will almost certainly take less memory and be a bit faster, though how much depends on your application.

Designing a custom hash function can be tricky, but you can start with a function that just takes the already-defined hashes of the composite key's members and XORs them together. You could also take the string route, but then make sure you concatenate the members with some marker in between them (such as ":") that is unlikely to occur in them.

回答4:

Using combined keys seems more logical to me, and easier to use (you don't have to worry about the nested map being instancied).

About the combination of the keys, use a custom class. It makes more sense semantically, and prevents colisions if you have similar strings. Such a colision could appear if you have the key ["ab", "c"] and the key ["a", "bc"].

Remember when you write your custom class, you need to write the equals and hashCode methods correctly, or your cache might not work (and might suffer performance issues as well).

回答5:

I had a similar problem with a caching system that needed to use method paramaters for the key generation. I ended up writing a wrapper class similar to Xavi's answer.

public final class ArrayWrapper 
{
    private final Object[] array;

    public ArrayWrapper(final Object... array)
    {
        this.array = array;
    }

    public Object[] getArray()
    {
        return this.array;
    }

    public boolean equals(Object o)
    {
        if (o == null) return false;
        if (o == this) return true;
        if (o instanceof ArrayWrapper)
        {
            return Arrays.equals(this.array, ((ArrayWrapper)o).array);
        }
        return false;
    }

    private int hashCode(Object o)
    {
        if (o == null) return 0;
        return o.hashCode();
    }

    public int hashCode()
    {
        int sum = 17;
        if (this.array != null) for(int i = 0;i<this.array.length;i++)
        {
            sum = 37 * sum + this.hashCode(this.array[i]);
        }
        return sum;
    }

    public String toString()
    {
        if (this.array != null)
        {
            return "Wrapper " + Arrays.toString(array);
        }
        else return "Wrapper []";
    }
}

Create a new Wrapper and use it as a key to the Map. You can also write a custom map and overload the get and put methods to accept an array (for get also vararg) instead of having to wrap it manually.

回答6:

I think that using nested maps is less optimal way. I agree with your second thought - implement a custom class with overriden hashCode

public int hashCode(){
   return str1+str2.hashCode();
}

and equals

public boolean equals(Object o){
   //compare both keys here
}

Also don't forget to override the same methods in the stored object's class.

Then, in case of ["ab", "c"] you will have the same hash code, but different equals result