[Someone]

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);

Only doing the latter will not move the item to its correct location.

Also, I am too lazy to chrck it, but I do not think this will have the same big-O as the C++ code.