title: How to implement a most-recently-used cache
body: <p>What would be the best way to implement a most-recently-used cache of objects?</p>
  
  <p>Here are the requirements and restrictions...</p>
  
  <ul>
  <li>Objects are stored as key/value Object/Object pairs, so the interface would be a bit like Hashtable get/put</li>
  <li>A call to 'get' would mark that object as the most recently used.</li>
  <li>At any time, the least recently used object can be purged from the cache.</li>
  <li>Lookups and purges must be fast (As in Hashtable fast)</li>
  <li>The number of Objects may be large, so list lookups are not good enough.</li>
  <li><strong>The implementation must be made using JavaME, so there is little scope for using third-party code or neat library classes from the standard Java libraries.</strong> For this reason I'm looking more for algorithmic answers rather than recommendations of off-the-peg solutions.</li>
  </ul>