algorithm - 通过有效地找到最后使用的元素来保持缓存( map )小

Question

我有一个 Java 应用程序，可以为大平铺图像的重新采样区域提供服务。

因为连续的区域查询通常彼此靠近，所以将图像切片缓存在 HashMap 中是有意义的。现在我想防止这个缓存无限增长。

为了不损失性能，我需要一个 O(1)/O(logN) 方法来查找最长时间未被访问的 map 元素。有没有办法做到这一点，它与仅从缓存中删除随机元素相比如何？

堆或 bst 将允许我保持排序的最后访问列表，但更新其中一个中的最后访问将花费线性时间。

这是我目前使用的代码的摘录:

Map<Point, BufferedImage> loadedImages = new ConcurrentHashMap<>();
Deque<Point> lastUsed = new ConcurrentLinkedDeque<>();

int getRGB(double tileX, double tileY) {
    Point point = new Point((int) tileX, (int) tileY);
    if (!loadedImages.containsKey(point)) {
        loadedImages.put(point, ImageIO.read(new File("R:\\tiles\\22\\" + point.y + "_" + point.x + ".jpg")));
        lastUsed.addLast(point);
    }
    BufferedImage img = loadedImages.get(point);
    if (loadedImages.size() > 1000) {
        loadedImages.remove(lastUsed.pollFirst());
    }
    //do stuff with img
}

这不是最优的，因为加载时间最长的图像可能在一秒钟前才被访问。

Answer 1

LinkedHashMap 与 Collections.synchronizedMap(linkedHashMap) 一起完成了这个技巧。 LinkedHashMap 的 removeEldestEntry 方法允许定义何时删除最后访问的条目的条件。

final int MAX_BUF_SIZE = 1000;

Map<Point, BufferedImage> loadedImages = new LinkedHashMap(MAX_BUF_SIZE + 1, .75F, true) {

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_BUF_SIZE;
    }
};

int getRGB(double tileX, double tileY) {
    Point point = new Point((int) tileX, (int) tileY);
    if (!loadedImages.containsKey(point)) {
        loadedImages.put(point, ImageIO.read(new File("R:\\tiles\\22\\" + point.y + "_" + point.x + ".jpg")));
    }

    BufferedImage img = loadedImages.get(point);
    //do stuff with img..
}