1
\$\begingroup\$

I needed a way to cache a large number of objects with two different types of keys.

In my case:

  • A String key represents my object in a serialized form. This way if I get the same serialized object from an outside source, I an easily determine if it already exist and avoid re-parsing it (I just re-put() the existing entry to make it freshly cached).
  • The second key is an Integer index, which is used as a light ID of the object for inter-process communications.

I also wanted the access to a value with both key types to be \$O(1)\$, since I use both pretty often. I am using one LRU map with strong references to the values, and a second map with weak references. This way when an entry is removed from the first map, I expect the second map to release the value object as soon as the GC is invoked.

My only concern is that the second map still keeps the redundant keys after their values are released, which is bad in case of large keys. I thought of using a ReferenceQueue or a WeakHashMap somehow to delete those keys, but couldn't yet come up with a satisfying implementation.

I added a Thread to deal with deleting the unused keys in the weak references map.

import java.lang.ref.WeakReference;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * An LRU cache with double mapping - two keys of different types are used
 * for accessing each cached  value.
 * 
 * @author Eliyahu
 *
 * @param <K1> - first key type.
 * @param <K2> - second key type.
 * @param <V> - values type.
 */
public class DoubleMappedLRU<K1, K2, V> {
    private final Map<K1, V> strongRefMap;
    private final Map<K2, WeakReference<V>> weakRefMap;

    /**
     * Constructs a new DoubleMappedLRU with the specified capacity.
     * 
     * @param capacity - the maximum number of values in the cache.
     */
    public DoubleMappedLRU(int capacity) {
        strongRefMap = createSyncedLRUMap(capacity);
        weakRefMap = new HashMap<K2, WeakReference<V>>();

         /**
         * This thread occasionally iterates the weakRefMap and removes keys with deleted values.
         */
        new Thread("clean deleted keys") {
            WeakReference<DoubleMappedLRU<K1, K2, V>> lruRef = 
                    new WeakReference<DoubleMappedLRU<K1, K2, V>>(DoubleMappedLRU.this);
            @Override
            public void run() {
                while (lruRef.get() != null) {
                    try {
                        Map<K2, WeakReference<V>> wm = lruRef.get().weakRefMap;
                        synchronized (DoubleMappedLRU.this) {
                            for (K2 key : wm.keySet()) {
                                if (wm.get(key) != null && wm.get(key).get() == null {
                                    wm.remove(key);
                                }
                            }
                        }

                        Thread.sleep(1000);
                    } catch (InterruptedException iex) {
                        return;
                    } catch (Exception ex) {
                        ex.printStackTrace();
                    }
                }
            }
        }.start();
    }

    /**
     * Caches the specified value with the two specified keys in this double mapping.
     * 
     * @param key1 - first key for the value
     * @param key2 - second key for the value
     * @param value - the value to cache
     */
    public synchronized void put(K1 key1, K2 key2, V value) {
        strongRefMap.put(key1, value);
        weakRefMap.put(key2, new WeakReference<V>(value));
    }

    /**
     * Returns the value to which the specified key is mapped, 
     * or null if this map contains no mapping for the key. 
     * @param key - the key whose associated value is to be returned 
     * 
     * @return the value to which the specified key is mapped, 
     * or null if this map contains no mapping for the key 
     */
    public synchronized V get1(K1 key) {
        return strongRefMap.get(key);
    }

    /**
     * Returns the value to which the specified key is mapped, 
     * or null if this map contains no mapping for the key. 
     * @param key - the key whose associated value is to be returned 
     * 
     * @return the value to which the specified key is mapped, 
     * or null if this map contains no mapping for the key 
     */
    public synchronized V get2(K2 key) {
        WeakReference<V> ref = weakRefMap.get(key);
        if (ref != null) {
            return ref.get();
        }
        return null;
    }

    private static <K, V> Map<K, V> createLRUMap(final int maxEntries) {
        return new LinkedHashMap<K, V>(maxEntries+1, 0.75F, true) {
            private static final long serialVersionUID = -7654704024424510182L;

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > maxEntries;
            }
        };
    }

    private static <K, V> Map<K, V> createSyncedLRUMap(final int maxEntries) {
        Map<K, V> cache = createLRUMap(maxEntries);
        return (Map<K, V>)Collections.synchronizedMap(cache);
    }

    /**
     * Returns an Iteratable Collection of values, which is
     * a copied instance of the underlying mapped values.
     * <p>
     * This method return only a copy of the values to prevent
     * outside operations on the inner map structure.
     */
    public Collection<V> valuesCopy() {
        return new LinkedList<V>(strongRefMap.values());
    }

    /**
     * Returns a Set of type K1 keys, which is
     * a copied instance of the underlying mapped keys.
     * <p>
     * This method return only a copy of the keys to prevent
     * outside operations on the inner map structure.
     */
    public Set<K1> keySet1Copy() {
        return new HashSet<K1>(strongRefMap.keySet());
    }

    /**
     * Returns a Set of type K2 keys, which is
     * a copied instance of the underlying mapped keys.
     * <p>
     * This method return only a copy of the keys to prevent
     * outside operations on the inner map structure.
     */
    public Set<K2> keySet2Copy() {
        return new HashSet<K2>(weakRefMap.keySet());
    }
}
\$\endgroup\$
  • \$\begingroup\$ Is this code tested? Have you put a 'println' on the clean-up thread and seen it ever clean anything up? I see a number of issues in here, at least 2 of which mean the entries will never be GC'd, and the weak references will never be null. Additionally, there are some other less serious issue. But, this is a complicated subject, and it is possible you believe it actually works, but it does not. Do you have a way to remove anything from the K1 map? If not, the weak reference will never go 'null'. \$\endgroup\$ – rolfl Jan 2 '15 at 13:14
  • \$\begingroup\$ Second hint (ran out of space), when working with Weak References, it is almost always the case that you need to extend that class, not get direct instances of it. \$\endgroup\$ – rolfl Jan 2 '15 at 13:16
  • \$\begingroup\$ @rolfl You are right, the elements does not get GC'd, but I don't understand why... Ofcourse the K1 map entries are removed, when the cache reaches it's capacity. \$\endgroup\$ – Elist Jan 2 '15 at 13:59
  • \$\begingroup\$ What's the compelling reason to not use an existing cache implementation, such as Guava or Apache? \$\endgroup\$ – Eric Stein Jan 3 '15 at 0:11
  • \$\begingroup\$ @Eric - What implementation exist that gives me the described funcionality? \$\endgroup\$ – Elist Jan 3 '15 at 16:05
2
\$\begingroup\$

In this case, there are many things wrong.

The most significant, is that you never remove anything from the K1 map, as a result, that map always has a hard reference to the V value, which means the V value will never be GC'd, which in turn means WeakReferences referencing it will never 'go null'.

The right way to work with WeakReferences in a situation like this, is to extend them, and to include the keys as part of the reference.

Using a ReferenceQueue also allows you to clean references more efficiently.

I 'threw together' the following code which illustrates these right ways, and you can use that as a basis for further development.....

import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.HashMap;


public class DoubleWeakKey <A,B,V> {

    private static final class  DoubleReference<M,N,U> extends WeakReference<U> {

        private final M aKey;
        private final N bKey;
        public DoubleReference(M aKey, N bKey, U value, ReferenceQueue<U> queue) {
            super(value, queue);
            this.aKey = aKey;
            this.bKey = bKey;
        }

    }

    private final HashMap<A, DoubleReference<A,B,V>> aMap = new HashMap<>();
    private final HashMap<B, DoubleReference<A,B,V>> bMap = new HashMap<>();
    private final ReferenceQueue<V> refQueue = new ReferenceQueue<>();

    private final Object lock = new Object();


    public DoubleWeakKey() {
        Runnable cleaner = new Runnable() {
            public void run() {
                cleanQueue();
            }

        };
        Thread cleanThread = new Thread(cleaner, "DoubleWeakKey queue cleaner");
        cleanThread.setDaemon(true);
        cleanThread.start();
    }

    private void cleanQueue() {
        while (true) {
            try {
                @SuppressWarnings("unchecked")
                DoubleReference<A, B, V> cleaned = (DoubleReference<A, B, V>) refQueue.remove();
                clearReference(cleaned);
            } catch (InterruptedException e) {
                // ignore, this should be better.
                e.printStackTrace();
            }
        }

    }


    private void clearReference(DoubleReference<A,B,V> toClear) {
        synchronized (lock) {
            aMap.remove(toClear.aKey);
            bMap.remove(toClear.bKey);
        }
    }

    public void put(A aKey, B bKey, V value) {
        synchronized(lock) {
            DoubleReference<A, B, V> ref = new DoubleReference<>(aKey, bKey, value, refQueue);
            aMap.put(aKey, ref);
            bMap.put(bKey, ref);

        }
    }

    public V getA(A key) {
        synchronized(lock) {
            DoubleReference<A, B, V> ref = aMap.get(key);
            return ref == null ? null : ref.get();
        }
    }

    public V getB(B key) {
        synchronized(lock) {
            DoubleReference<A, B, V> ref = bMap.get(key);
            return ref == null ? null : ref.get();
        }
    }

}
\$\endgroup\$
  • \$\begingroup\$ rolfl - you keep saying that I never remove anything from the K1 map, but that's not true. K1 map entries are being automatically removed when removeEldestEntry returns true, and yet, the value object don't get GC'd. Anyway, thanks for your code example, I'll try integrate it into my system and see how it performs. \$\endgroup\$ – Elist Jan 3 '15 at 16:12
  • \$\begingroup\$ @Elist - I see that, now... Let me re-analyze that code segment \$\endgroup\$ – rolfl Jan 3 '15 at 16:20
  • \$\begingroup\$ Will appreciate that \$\endgroup\$ – Elist Jan 3 '15 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.