Least Recently Used (LRU) cache algorithm
A finite key-value map using the Least Recently Used (LRU) algorithm, where the most recently-used items are "kept alive" while older, less-recently used items are evicted to make room for newer items.
Useful when you want to limit use of memory to only hold commonly-used things.
Terminology & design
-
Based on a doubly-linked list for low complexity random shuffling of entries.
-
The cache object iself has a "head" (least recently used entry) and a
"tail" (most recently used entry).
-
The "oldest" and "newest" are list entries -- an entry might have a "newer" and
an "older" entry (doubly-linked, "older" being close to "head" and "newer"
being closer to "tail").
-
Key lookup is done through a key-entry mapping native object, which on most
platforms mean O(1)
complexity. This comes at a very low memory cost (for
storing two extra pointers for each entry).
Fancy ASCII art illustration of the general design:
entry entry entry entry
______ ______ ______ ______
| head |.newer => | |.newer => | |.newer => | tail |
.oldest = | A | | B | | C | | D | = .newest
|______| <= older.|______| <= older.|______| <= older.|______|
removed <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- added
Example
let c = new LRUMap(3)
c.set('adam', 29)
c.set('john', 26)
c.set('angela', 24)
c.toString()
c.get('john')
c.toString()
c.set('zorro', 141)
c.toString()
Usage
Recommended: Copy the code in lru.js or copy the lru.js and lru.d.ts files into your source directory. For minimal functionality, you only need the lines up until the comment that says "Following code is optional".
Using NPM: yarn add lru_map
(note that because NPM is one large flat namespace, you need to import the module as "lru_map" rather than simply "lru".)
Using AMD: An AMD module loader like amdld
can be used to load this module as well. There should be nothing to configure.
Testing:
- Run tests with
npm test
- Run benchmarks with
npm run benchmark
ES compatibility: This implementation is compatible with modern JavaScript environments and depend on the following features not found in ES5:
const
and let
keywordsSymbol
including Symbol.iterator
Map
Note: If you need ES5 compatibility e.g. to use with older browsers, please use version 2 which has a slightly less feature-full API but is well-tested and about as fast as this implementation.
Using with TypeScript
This module comes with complete typing coverage for use with TypeScript. If you copied the code or files rather than using a module loader, make sure to include lru.d.ts
into the same location where you put lru.js
.
import {LRUMap} from './lru'
console.log('LRUMap:', LRUMap)
API
The API imitates that of Map
, which means that in most cases you can use LRUMap
as a drop-in replacement for Map
.
export class LRUMap<K,V> {
constructor(limit :number, entries? :Iterable<[K,V]>);
constructor(entries :Iterable<[K,V]>);
size :number;
limit :number;
oldest :Entry<K,V>;
newest :Entry<K,V>;
assign(entries :Iterable<[K,V]>) : void;
set(key :K, value :V) : LRUMap<K,V>;
shift() : [K,V] | undefined;
get(key :K) : V | undefined;
has(key :K) : boolean;
find(key :K) : V | undefined;
delete(key :K) : V | undefined;
clear() : void;
keys() : Iterator<K>;
values() : Iterator<V>;
entries() : Iterator<[K,V]>;
[Symbol.iterator]() : Iterator<[K,V]>;
forEach(fun :(value :V, key :K, m :LRUMap<K,V>)=>void, thisArg? :any) : void;
toJSON() : Array<{key :K, value :V}>;
toString() : string;
}
interface Entry<K,V> {
key :K;
value :V;
}
If you need to perform any form of finalization of items as they are evicted from the cache, wrapping the shift
method is a good way to do it:
let c = new LRUMap(123);
c.shift = function() {
let entry = LRUMap.prototype.shift.call(this);
doSomethingWith(entry);
return entry;
}
The internals calls shift
as entries need to be evicted, so this method is guaranteed to be called for any item that's removed from the cache. The returned entry must not include any strong references to other entries. See note in the documentation of LRUMap.prototype.set()
.
MIT license
Copyright (c) 2010-2016 Rasmus Andersson https://rsms.me/
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.