Dry run, capacity 3: state after each operation (keys listed LRU -> MRU) ======================================================================== # operation returns LRU -> MRU ptr-writes same as LinkedHashMap? 1 put(1,A) - [1] 4 yes 2 put(2,B) - [1,2] 4 yes 3 put(3,C) - [1,2,3] 4 yes 4 get(1) A [2,3,1] 6 yes 5 put(4,D) - (evicts 2) [3,1,4] 6 yes 6 get(2) null [3,1,4] 0 yes 7 put(3,C2) - (replace, refresh) [1,4,3] 6 yes 8 put(5,E) - (evicts 1) [4,3,5] 6 yes 9 get(4) D [3,5,4] 6 yes 10 get(1) null [3,5,4] 0 yes ptr-writes = pointer assignments on list nodes made by HashMapLruCache for that operation. A miss costs 0, a hit costs 6 (unlink 2 + link 4), a new insert 4 (+2 for the eviction unlink). None depends on the cache size.