title: Keep cache(map) small by finding last used element efficiently
body: <p>I have a java application that serves resampled areas of a big tiled image. </p>
  
  <p>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. </p>
  
  <p>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?</p>
  
  <p>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. </p>
  
  <p>Here's an excerpt from the code I'm using currently:</p>
  
  <pre><code>Map&lt;Point, BufferedImage&gt; loadedImages = new ConcurrentHashMap&lt;&gt;();
  Deque&lt;Point&gt; lastUsed = new ConcurrentLinkedDeque&lt;&gt;();
  
  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() &gt; 1000) {
          loadedImages.remove(lastUsed.pollFirst());
      }
      //do stuff with img
  }
  </code></pre>
  
  <p>This isn't optimal because the image that was loaded the longest time ago could have just been accessed a second ago.</p>