Is there concurrent & self-expiring & ordered hash map in java

Question

I'm using ConcurrentHashMap from google guava (via MapMaker), but that implementation isn't ordered. There is ConcurrentSkipListMap in google guava, but that structure can't expire.

Is there any structure that can do both?

Answer 1

I'd use ConcurrentSkipListMap and iterate the map periodically to purge expired stuff. Since the skiplist is unbounded this opens up a possibility of a memoryleak, when the eviction thread cannot catch up, but in practice this seems very, very unlikely unless you do something extreme.I've also done something like this when I didn't want to use a background thread:

static AtomicInteger cnt = new AtomicInteger();

Val put(K key, V val){
    //Do the usual stuff
    if(cnt.getAndIncrement() % 100 == 0){
        //iterate map and evict stuff
    }
}

The if(cnt.getAndIncrement() % 100 == 0) may have been a "clever optimization", so perhaps you could just iterate and evict everytime like matt b suggests.

Oh just one caveat when you do this.... Be sure to break equality between different entities when the timestamps coincide:

class Entity implaments Comparable<Entity>{
    static AtomicInteger SEQ = new AtomicInteger();
    int id = SEQ.getAndIncrement();
    long timeStamp = System.currentTimeMillis();

    int compareTo(Entity other){
        // compare by timestamp
        // If timestamps are equal, don't just return 0 yet!!
        // Compare by id and return 0 ONLY IF the id equals.
        // Otherwise entities disappear from your ordered map and 
        // it's really annoying to debug.
}