For comparison's sake, here's a simple LRU in Erlang: http://erlangquicktips.heroku.com/2008/10/05/an-erlang-lru-m...
In Java, LinkedHashMap[1] is well-suited to building LRU caches. [1] http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHas...
However, one should be aware of that "Note that insertion order is not affected if a key is re-inserted into the map".
Because of that, a timestamps update must do:
Cache.remove(key);
Cache.put(key,value);
Also, I am too lazy to chrck it, but I do not think this will have the same big-O as the C++ code.