Well, not exactly. We have to balance how much memory the cache structure takes with how much costs to get each data. It's a memory vs cost.

On the other hand, it does not require so much memory. For example, the LRU, in addition to the map, it also requires a double - linked list to know which will be the next evicted. But at the end, O(2N) it's just O(N).

And of course, if memory is a constraint, not CPU, you can always use plain arrays. In this case, 2X the size.

The only thing that I would consider is what happens if cached data is huge. In that case, a 2X (the cache entries + the victims) would be really relevant.