Java time-based map/cache with expiring keys

Question

Do any of you know of a Java Map or similar standard data store that automatically purges entries after a given timeout? This means aging, where the old expired entries “age-out” automatically.

I know of ways to implement the functionality myself and have done it several times in the past, so I'm not asking for advice in that respect, but for pointers to a good reference implementation.

WeakReference based solutions like WeakHashMap are not an option, because my keys are likely to be non-interned strings and I want a configurable timeout that's not dependent on the garbage collector.

Ehcache is also an option I wouldn't like to rely on because it needs external configuration files. I am looking for a code-only solution.

Answer 1

Yes. Google Collections, or Guava as it is named now has something called MapMaker which can do exactly that.

ConcurrentMap<Key, Graph> graphs = new MapMaker()
   .concurrencyLevel(4)
   .softKeys()
   .weakValues()
   .maximumSize(10000)
   .expiration(10, TimeUnit.MINUTES)
   .makeComputingMap(
       new Function<Key, Graph>() {
         public Graph apply(Key key) {
           return createExpensiveGraph(key);
         }
       });

Update:

As of guava 10.0 (released September 28, 2011) many of these MapMaker methods have been deprecated in favour of the new CacheBuilder:

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
    .maximumSize(10000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build(
        new CacheLoader<Key, Graph>() {
          public Graph load(Key key) throws AnyException {
            return createExpensiveGraph(key);
          }
        });

Answer 2

This is a sample implementation that i did for the same requirement and concurrency works well. Might be useful for someone.

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 
 * @author Vivekananthan M
 *
 * @param <K>
 * @param <V>
 */
public class WeakConcurrentHashMap<K, V> extends ConcurrentHashMap<K, V> {

    private static final long serialVersionUID = 1L;

    private Map<K, Long> timeMap = new ConcurrentHashMap<K, Long>();
    private long expiryInMillis = 1000;
    private static final SimpleDateFormat sdf = new SimpleDateFormat("hh:mm:ss:SSS");

    public WeakConcurrentHashMap() {
        initialize();
    }

    public WeakConcurrentHashMap(long expiryInMillis) {
        this.expiryInMillis = expiryInMillis;
        initialize();
    }

    void initialize() {
        new CleanerThread().start();
    }

    @Override
    public V put(K key, V value) {
        Date date = new Date();
        timeMap.put(key, date.getTime());
        System.out.println("Inserting : " + sdf.format(date) + " : " + key + " : " + value);
        V returnVal = super.put(key, value);
        return returnVal;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (K key : m.keySet()) {
            put(key, m.get(key));
        }
    }

    @Override
    public V putIfAbsent(K key, V value) {
        if (!containsKey(key))
            return put(key, value);
        else
            return get(key);
    }

    class CleanerThread extends Thread {
        @Override
        public void run() {
            System.out.println("Initiating Cleaner Thread..");
            while (true) {
                cleanMap();
                try {
                    Thread.sleep(expiryInMillis / 2);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }

        private void cleanMap() {
            long currentTime = new Date().getTime();
            for (K key : timeMap.keySet()) {
                if (currentTime > (timeMap.get(key) + expiryInMillis)) {
                    V value = remove(key);
                    timeMap.remove(key);
                    System.out.println("Removing : " + sdf.format(new Date()) + " : " + key + " : " + value);
                }
            }
        }
    }
}

Git Repo Link (With Listener Implementation)

https://github.com/vivekjustthink/WeakConcurrentHashMap

Cheers!!

Answer 3

Apache Commons has decorator for Map to expire entries: PassiveExpiringMap It's more simple than caches from Guava.

P.S. be careful, it's not synchronized.

Answer 4

You can try out my implementation of a self-expiring hash map. This implementation does not make use of threads to remove expired entries, instead it uses DelayQueue that is cleaned up at every operation automatically.

Answer 5

Sounds like ehcache is overkill for what you want, however note that it does not need external configuration files.

It is generally a good idea to move configuration into a declarative configuration files ( so you don't need to recompile when a new installation requires a different expiry time ), but it is not at all required, you can still configure it programmatically. http://www.ehcache.org/documentation/user-guide/configuration

Answer 6

If anybody needs a simple thing, following is a simple key-expiring set. It might be converted to a map easily.

public class CacheSet<K> {
    public static final int TIME_OUT = 86400 * 1000;

    LinkedHashMap<K, Hit> linkedHashMap = new LinkedHashMap<K, Hit>() {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, Hit> eldest) {
            final long time = System.currentTimeMillis();
            if( time - eldest.getValue().time > TIME_OUT) {
                Iterator<Hit> i = values().iterator();

                i.next();
                do {
                    i.remove();
                } while( i.hasNext() && time - i.next().time > TIME_OUT );
            }
            return false;
        }
    };


    public boolean putIfNotExists(K key) {
        Hit value = linkedHashMap.get(key);
        if( value != null ) {
            return false;
        }

        linkedHashMap.put(key, new Hit());
        return true;
    }

    private static class Hit {
        final long time;


        Hit() {
            this.time = System.currentTimeMillis();
        }
    }
}

Answer 7

Typically, a cache should keep objects around some time and shall expose of them some time later. What is a good time to hold an object depends on the use case. I wanted this thing to be simple, no threads or schedulers. This approach works for me. Unlike SoftReferences, objects are guaranteed to be available some minimum amount of time. However, the do not stay around in memory until the sun turns into a red giant.

As useage example think of a slowly responding system that shall be able to check if a request has been done quite recently, and in that case not to perform the requested action twice, even if a hectic user hits the button several times. But, if the same action is requested some time later, it shall be performed again.

class Cache<T> {
    long avg, count, created, max, min;
    Map<T, Long> map = new HashMap<T, Long>();

    /**
     * @param min   minimal time [ns] to hold an object
     * @param max   maximal time [ns] to hold an object
     */
    Cache(long min, long max) {
        created = System.nanoTime();
        this.min = min;
        this.max = max;
        avg = (min + max) / 2;
    }

    boolean add(T e) {
        boolean result = map.put(e, Long.valueOf(System.nanoTime())) != null;
        onAccess();
        return result;
    }

    boolean contains(Object o) {
        boolean result = map.containsKey(o);
        onAccess();
        return result;
    }

    private void onAccess() {
        count++;
        long now = System.nanoTime();
        for (Iterator<Entry<T, Long>> it = map.entrySet().iterator(); it.hasNext();) {
            long t = it.next().getValue();
            if (now > t + min && (now > t + max || now + (now - created) / count > t + avg)) {
                it.remove();
            }
        }
    }
}

Answer 8

you can try Expiring Map http://www.java2s.com/Code/Java/Collections-Data-Structure/ExpiringMap.htm a class from The Apache MINA Project