Object cache data structure with "object expiration"

Question

Which data structure in Java would be best to implement an in-memory object cache, where objects have an individual expiration time?

Basically for the cache I could use a Map (where key could be a String) which offers the put and get methods, and use a ordered list of "timestamp"+"object" pairs to manage the expiration time. So a cleanup thread could check the first list entry and delete the object when its expiration time passed. (Deletion of the first element should be in O(1) time)

Answer 1

What you're describing building is basically my ExpiringMap. There are other similar implementations, such as Guava (see CacheBuilder) - though I don't believe it supports per-entry expiration as ExpiringMap does.

Answer 2

Caching frameworks are pretty mature now:

• EhCache: http://ehcache.org/
• Memcached: http://memcached.org/

However, if you insist on reinventing the wheel, remember to account for memory utilisation. All too often I see a badly implemented cache (HashMap) effectively turn into a memory leak.

See Cowan's answer here: Java's WeakHashMap and caching: Why is it referencing the keys, not the values?