lru-map

Minimum LRU (Least Recently Used) cache based on Map object.

What

Essentially, what this project provides is a Map object with a limited maximum number of items.

The LRU algorithm is used to handle items that exceed the maximum number.

Also, the interface is almost the same as the Map object. The only difference is that you need to specify the maximum number of items.

Additionally, it does not do much to minimize the bundle size.

Why

When you cache data, you should always be concerned about the size of the cache.

Endless caching will eat up all of your resources.

Map objects are limited to a maximum number of items of approximately 2^24.

If it is exceeded, a RangeError will be thrown.

let count = 0;
const map = new Map();

while (count < Math.pow(2, 25)) {
  map.set(count, count);
  count++;
}

This does not occur because LRUMap cannot hold more than the maximum number of items.

Of course, if the maximum number is greater than 2^24, the result will be the same as for the Map object.

Definition of Used

"Used" is ambiguous, so we will clarify the situation.

Used" is defined as when the actual item is retrieved. That is, a reference by get is "used", but a reference by has is not "used".

Basic usage

LRU Map and Map look almost the same. You must always give maxSize as a constructor argument.

import { LRUMap } from "https://deno.land/x/lru_map@$VERSION/mod.ts";
const cache = new LRUMap(100);

After that, it is used in the same way as Map.

Initial entries

Initial entries are accepted as Map. The leftmost item is defined as the oldest, so if there are too many items, they are overwritten from the left.

import { LRUMap } from "https://deno.land/x/lru_map@$VERSION/mod.ts";
import { assertEquals } from "https://deno.land/std@$VERSION/testing/asserts.ts";

const map = new LRUMap(2, [[0, "left"], [1, "middle"], [2, "right"]]);
assertEquals([...map.values()], ["middle", "right"]);

Iteration

When iterating over an item, there are a few things to keep in mind.

LRU Map keeps items in Oldest Order. Repeatedly retrieving an item will return the items in the same order of oldest to newest.

import { LRUMap } from "https://deno.land/x/lru_map@$VERSION/mod.ts";
import { assertEquals } from "https://deno.land/std@$VERSION/testing/asserts.ts";

const map = new LRUMap(2, [[0, "left"], [1, "middle"], [2, "right"]]);
map.set(3, "rightmost");

assertEquals([...map.values()], ["right", "rightmost"]);

Side effects of Used

When an item is used, the item is considered most recently used.

As seen in Iteration, items are kept in order of oldest to newest, so when these operations are performed, the order of the items will change.

import { LRUMap } from "https://deno.land/x/lru_map@$VERSION/mod.ts";
import { assertEquals } from "https://deno.land/std@$VERSION/testing/asserts.ts";

const map = new LRUMap(2, [[0, "left"], [1, "right"]]);
assertEquals([...map.entries()], [[0, "left"], [1, "right"]]);

const left = map.get(0);
assertEquals([...map.entries()], [[[1, "right"], 0, "left"]]);

License

Copyright © 2022-present TomokiMiyauci.

Released under the MIT license