Java Map 与 TimeToLive 与每个键/值对相关联

Question

最近，我(在一次采访中)被要求设计 HashMap ，并将 TTL 与每个键相关联。我使用下面给出的类似方法完成了它，但根据他的说法，这不是一个好方法，因为这需要在整个 map 上迭代，如果 map 大小以百万为单位，那么这将是一个瓶颈。

有没有更好的方法来做同样的事情？此外，他只关心线程在后台继续运行，尽管下一个 TTL 是在几个小时之后。

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);
            }
        }
    }
}

Answer 1

最好使用LinkedHashMap，这样您就可以保留插入顺序。事实上，LinkedHashMap 是从 HashMap 扩展而来的。如果运行线程是问题，那么您可以通过扩展 LinkedHashMap 来创建映射的自定义实现。在类内部，重写 get 方法。

编辑:基于onkar的评论。最好重写 get 而不是 put，因为这会阻止检索过期的项目。

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);
    }
}