Remove oldest entry in Map() with O(1) time complexity JS-CodePudding

If we want to keep fixed size of a map - 3 entries and remove oldest touched entry, when new one is created, how do we do it with constant time? (I got told it's possible)

If we do such operations:

let cache = new Map()

cache.set('one', 1);
cache.set('two', 2);
cache.set('three', 3);

cache.set('two', 'two');

cache.set('four', 4);

I'd expect map then to be:

{
    ['three', 3],
    ['two', 'two'],
    ['four', 4],
}

I can think only of having O(n) solution for invalidation, but it defeats whole purpose of cache.

CodePudding user response：

Maps are iterated in the order in which the keys were created. So you can use that to do

const cache = new Map();
const keysIter = cache.keys();
function set(key, value) {
    cache.set(key, value);
    if (cache.size > 3) {
        cache.delete(keysIter.next().value);
    }
}

If however by "oldest touched" you want to refer to updates, not just to creation (e.g. in your example, cache.set('five', 5) would evict ['three', 3] not ['two', 'two']), you will need to keep track of these touches yourself, e.g. in a circular buffer. Or maybe just call cache.delete(key) every time before "updating", so that the cache.set(key, value) always creates a new entry at the end.