Java Map with TimeToLive Associated with each key/value pair

user_4115835 0
Viewed 748

Recently I was asked (in an interview) to design HashMap with TTL associated with each key. I done it using similar approach given below but as per him this is not a good approach as this would need iteration on whole map and if map size is in million then this would be a bottleneck.

Is there any better approach to do the same? Moreover- He was only concerned that a thread is kept running in background though the next TTL is hours later.

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);
            }
        }
    }
}
ttl hashmap java
3 Answers

It would be better to use a LinkedHashMap so that you could preserve the insertion order. Infact LinkedHashMap extends from a HashMap. If running a thread is the problem, then you could create a custom implementation of the map by extending the LinkedHashMap. Inside the class, override the get method.

EDIT : Based on onkar's comment. It is better to override the get instead of put as this would prevent retrieval of expired items.

public class MyLinkedHashMap<K> extends LinkedHashMap<K, Date> {
    
    private static final long expiryTime = 100000L;
    private long currentOldest = 0L;

    @Override
    public Date get(Object key) {
        long currentTime = new Date().getTime();
        if ((currentOldest > 0L) && (currentOldest + expiryTime) < currentTime) {
            // even the oldest key has not expired.
            return super.get(key);
        }

        Iterator<Map.Entry<K, Date>> iter = this.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry<K, Date> entry = iter.next();
            long entryTime = entry.getValue().getTime();
            if (currentTime >= entryTime + expiryTime) {
                iter.remove();
            } else {
                // since this is a linked hash map, order is preserved.
                // All the elements after the current entry came later.
                // So no need to check the remaining elements if the current is not expired.
                currentOldest = entryTime;
                break;
            }
        }

        return super.get(key);
    }
}
user_78044770

Extending HashMap and it's Entry class and adding new entry for expiry time and override get method to return value only if expiry time is in past i.e expiryTime<System.getCurrentTimeInMilis()

user_176067500

When you talk TTLs, and you want to access them by order of their TTL values, you should use PriorityQueue or PriorityBlockingQueue or HeapMaps (idk if Java has a HeapMap implementation tho).

Whenever you insert an item, it gets shuffled to its proper ordering position withing the Collection.

So if you only want to take out TTLs that have expired, you just check/take, and you will get the eariest expired first, and you keep check/take until you hit the first whose TTL has not expired yet. That's where you stop. Because PriorityQueues guarantee that (if you did the compareTo functions properly) all elemets are sorted at all times, so after hitting the first un-expired entry, a) that entry will be closest to expiry and b) all the others will have a later expiry. The last item in the queue - independent of the sequence you put them there - will be the one with the latest expiry.

user_19320110
Related