Keep a counter of the number of insertions and gets. Every time data is accessed or written to, store the current number of the counter in a hash map (with the same key as the data), with the value being a tuple of that number and the data itself. Keep track of the lowest possible number of data that has been get/putd. (remember that when items are updated, the cache does not change size and therefore there will now be a missing number in the otherwise consecutive entries; this does not affect most of the strategy). When items are get/putd, check to see if the current cache size is below the max size, or if the key is already in the cache. Update it with the new number and the new data (for a put). If it doesn't exist, check the existing entries one by one and replace the first entry that has a number of the current counter - the max size of the cache.