title: Sorted Keys data structure for LRU and MRU cache eviction policies
body: <p>I am working on a simple data structure that will implement a cache eviction policy. The two possible scenarios I want to implement are <a href="http://en.wikipedia.org/wiki/Cache_algorithms#Examples" rel="nofollow">LRU and MRU</a> </p>
  
  <p>I am looking for a map-like data structure where keys are possibly time (or maybe just auto incremented integer) to know which cache block is most recently used or least recently used. And values are the IDs of the blocks.</p>
  
  <p>Is there an existent Data structure that sorts the data by the keys on insert, and retrieves the value of a certain key in O(1) time?</p>
  
  <p>For instance Java's HashMap has the constant time lookup, but I will need to get all keys, sort them and pick the last or the first depending on the algorithm I am implementing. Is <a href="http://docs.oracle.com/javase/6/docs/api/java/util/SortedMap.html" rel="nofollow">SortedMap</a> what I should go for? Do you suggest any other data structures that work well with LRU and MRU implementations?</p>
  
  <p>Thanks</p>