Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Nested Maps or combined keys in java

Tags:

java

hashmap

key

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)

like image 258
PhoneixS Avatar asked Nov 17 '11 13:11

PhoneixS


5 Answers

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);
} 
like image 139
Xavi López Avatar answered Oct 24 '22 00:10

Xavi López


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>
like image 32
John B Avatar answered Oct 24 '22 00:10

John B


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.

like image 41
Fred Foo Avatar answered Oct 23 '22 22:10

Fred Foo


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).

like image 32
Vivien Barousse Avatar answered Oct 23 '22 22:10

Vivien Barousse


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.

like image 1
Stefan Avatar answered Oct 23 '22 22:10

Stefan