Keep cache(map) small by finding last used element efficiently

Question

I have a java application that serves resampled areas of a big tiled image.

Because consecutive area queries are often close to each other, it makes sense to cache the image tiles in a hash map. Now I would like to keep this cache from growing indefinitely.

To not lose performance I need a O(1)/O(logN) method of finding the map element that hasn't been accessed for the longest time. Is there a way of doing this and how does it compare to just removing random elements from the cache?

A heap or bst would allow me to keep the list of last accesses sorted, but updating the last access in one of those would take linear time.

Here's an excerpt from the code I'm using currently:

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
}

This isn't optimal because the image that was loaded the longest time ago could have just been accessed a second ago.

Answer 1

A LinkedHashMap together with Collections.synchronizedMap(linkedHashMap) did the trick. The removeEldestEntry method of the LinkedHashMap allows to define a condition on when to remove the last accessed entry.

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..
}

Answer 2

Use LinkedHashMap as LRUCache - Simple Example:

public class LRULinkedHashMap extends LinkedHashMap<Integer, String> {

    /**
     * 
     */
    private static final long serialVersionUID = 1L;
    private int capacity;

    public LRULinkedHashMap(int capacity) {
        // initialise the capacity, and when to 'double' the capacity (75% of capacity) and 
        // 'true' if the ordering should be done based on the last
        // access (from least-recently accessed to most-recently accessed) 
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }


    /**
     * Returns true if this map should remove its eldest entry. 
     * This method is invoked by put and putAll after inserting a new entry into the map. 
     * It provides the implementor with the opportunity to remove the eldest entry each 
     * time a new one is added. This is useful if the map represents a cache: it allows 
     * the map to reduce memory consumption by deleting stale entries.
     */
    @Override
    protected boolean removeEldestEntry(Entry<Integer, String> eldest) {
        // this will return true and remove the eldest entry every time the size of the map
        // is bigger than the capacity - the size() will never go beyond double the capacity
        // (it will double automatically when it hits 75% of original capacity) as this ensures
        // any 'put' entry over the capacity is removes the eldest object 
        return size() > this.capacity;
    }



    public static void main(String[] args) {
        // TODO Auto-generated method stub

        // Last Recently Used LinkedHashMap Cache
        LRULinkedHashMap cache = new LRULinkedHashMap(6);

        // put some objects into the map
        cache.put(1, "one");
        System.out.println(cache);
        cache.put(2, "two");
        System.out.println(cache);
        cache.put(3, "three");
        System.out.println(cache);
        cache.put(4, "four");
        System.out.println(cache);
        cache.put(5, "five");
        System.out.println(cache);
        cache.put(6, "six"); // capacity (6) reached
        System.out.println(cache + "  <-- Capacity Reached");
        cache.put(7, "seven"); // 1 is removed - eldest
        System.out.println(cache + "  <-- 1 removed");
        cache.put(8, "eight"); // 2 is removed - next eldest
        // access an object before it is removed
        System.out.println(cache + "  <-- 2 Removed");
        cache.get(4); // 4 retrieved placed after 8 - nothing removed (we've only changed the order, not put anything into the map)
        System.out.println(cache + "  <-- '4' Retrieved, access order changed only");
        cache.put(9, "nine"); // 3 is removed - next eldest (4 was retrieved!) 
        System.out.println(cache + "  <-- 3 Removed");
        cache.put(10, "ten"); // 5 removed - next eldest
        // first item is always the eldest - will be next to go if item retrieved or put in map
        System.out.println(cache + "  <-- 5 Removed");

    }

}