Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 4b4d770

Browse filesBrowse files
trekhlebtrekhleb
committed
Add an example of the LRU Cache based on the Map.
1 parent 69c3a16 commit 4b4d770
Copy full SHA for 4b4d770

File tree

4 files changed

+216
-3
lines changed
Filter options

4 files changed

+216
-3
lines changed

‎src/data-structures/lru-cache/LRUCache.js

Copy file name to clipboardExpand all lines: src/data-structures/lru-cache/LRUCache.js
+3-3Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ class LinkedListNode {
2424
* Implementation of the LRU (Least Recently Used) Cache
2525
* based on the HashMap and Doubly Linked List data-structures.
2626
*
27-
* Current implementation allows to have fast (O(1)) read and write operations.
27+
* Current implementation allows to have fast O(1) (in average) read and write operations.
2828
*
2929
* At any moment in time the LRU Cache holds not more that "capacity" number of items in it.
3030
*/
@@ -43,7 +43,7 @@ class LRUCache {
4343

4444
/**
4545
* Returns the cached value by its key.
46-
* Time complexity: O(1).
46+
* Time complexity: O(1) in average.
4747
* @param {string} key
4848
* @returns {any}
4949
*/
@@ -56,7 +56,7 @@ class LRUCache {
5656

5757
/**
5858
* Sets the value to cache by its key.
59-
* Time complexity: O(1).
59+
* Time complexity: O(1) in average.
6060
* @param {string} key
6161
* @param {any} val
6262
*/

‎src/data-structures/lru-cache/LRUCacheOnMap.js

Copy file name to clipboard
+53Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/* eslint-disable no-restricted-syntax, no-unreachable-loop */
2+
3+
/**
4+
* Implementation of the LRU (Least Recently Used) Cache
5+
* based on the (ordered) Map data-structure.
6+
*
7+
* Current implementation allows to have fast O(1) (in average) read and write operations.
8+
*
9+
* At any moment in time the LRU Cache holds not more that "capacity" number of items in it.
10+
*/
11+
class LRUCacheOnMap {
12+
/**
13+
* Creates a cache instance of a specific capacity.
14+
* @param {number} capacity
15+
*/
16+
constructor(capacity) {
17+
this.capacity = capacity; // How many items to store in cache at max.
18+
this.items = new Map(); // The ordered hash map of all cached items.
19+
}
20+
21+
/**
22+
* Returns the cached value by its key.
23+
* Time complexity: O(1) in average.
24+
* @param {string} key
25+
* @returns {any}
26+
*/
27+
get(key) {
28+
if (!this.items.has(key)) return undefined;
29+
const val = this.items.get(key);
30+
this.items.delete(key);
31+
this.items.set(key, val);
32+
return val;
33+
}
34+
35+
/**
36+
* Sets the value to cache by its key.
37+
* Time complexity: O(1).
38+
* @param {string} key
39+
* @param {any} val
40+
*/
41+
set(key, val) {
42+
this.items.delete(key);
43+
this.items.set(key, val);
44+
if (this.items.size > this.capacity) {
45+
for (const headKey of this.items.keys()) {
46+
this.items.delete(headKey);
47+
break;
48+
}
49+
}
50+
}
51+
}
52+
53+
export default LRUCacheOnMap;

‎src/data-structures/lru-cache/README.md

Copy file name to clipboardExpand all lines: src/data-structures/lru-cache/README.md
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,8 @@ The functions `get()` and `set()` must each run in `O(1)` average time complexit
1616

1717
## Implementation
1818

19+
### Version 1: Doubly Linked List + Hash Map
20+
1921
See the `LRUCache` implementation example in [LRUCache.js](./LRUCache.js). The solution uses a `HashMap` for fast `O(1)` (in average) cache items access, and a `DoublyLinkedList` for fast `O(1)` (in average) cache items promotions and eviction (to keep the maximum allowed cache capacity).
2022

2123
![Linked List](./images/lru-cache.jpg)
@@ -24,6 +26,16 @@ See the `LRUCache` implementation example in [LRUCache.js](./LRUCache.js). The s
2426

2527
You may also find more test-case examples of how the LRU Cache works in [LRUCache.test.js](./__test__/LRUCache.test.js) file.
2628

29+
### Version 2: Ordered Map
30+
31+
The first implementation that uses doubly linked list is good for learning purposes and for better understanding of how the average `O(1)` time complexity is achievable while doing `set()` and `get()`.
32+
33+
However, the simpler approach might be to use a JavaScript [Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map) object. The `Map` object holds key-value pairs and **remembers the original insertion order** of the keys. We can use this fact in order to keep the recently-used items in the "end" of the map by removing and re-adding items. The item at the beginning of the `Map` is the first one to be evicted if cache capacity overflows. The order of the items may checked by using the `IterableIterator` like `map.keys()`.
34+
35+
See the `LRUCacheOnMap` implementation example in [LRUCacheOnMap.js](./LRUCacheOnMap.js).
36+
37+
You may also find more test-case examples of how the LRU Cache works in [LRUCacheOnMap.test.js](./__test__/LRUCacheOnMap.test.js) file.
38+
2739
## Complexities
2840

2941
| | Average |

‎src/data-structures/lru-cache/__test__/LRUCacheOnMap.test.js

Copy file name to clipboard
+148Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
import LRUCache from '../LRUCacheOnMap';
2+
3+
describe('LRUCacheOnMap', () => {
4+
it('should set and get values to and from the cache', () => {
5+
const cache = new LRUCache(100);
6+
expect(cache.get('key-1')).toBeUndefined();
7+
8+
cache.set('key-1', 15);
9+
cache.set('key-2', 16);
10+
cache.set('key-3', 17);
11+
expect(cache.get('key-1')).toBe(15);
12+
expect(cache.get('key-2')).toBe(16);
13+
expect(cache.get('key-3')).toBe(17);
14+
expect(cache.get('key-3')).toBe(17);
15+
expect(cache.get('key-2')).toBe(16);
16+
expect(cache.get('key-1')).toBe(15);
17+
18+
cache.set('key-1', 5);
19+
cache.set('key-2', 6);
20+
cache.set('key-3', 7);
21+
expect(cache.get('key-1')).toBe(5);
22+
expect(cache.get('key-2')).toBe(6);
23+
expect(cache.get('key-3')).toBe(7);
24+
});
25+
26+
it('should evict least recently used items from cache with cache size of 1', () => {
27+
const cache = new LRUCache(1);
28+
expect(cache.get('key-1')).toBeUndefined();
29+
30+
cache.set('key-1', 15);
31+
expect(cache.get('key-1')).toBe(15);
32+
33+
cache.set('key-2', 16);
34+
expect(cache.get('key-1')).toBeUndefined();
35+
expect(cache.get('key-2')).toBe(16);
36+
37+
cache.set('key-2', 17);
38+
expect(cache.get('key-2')).toBe(17);
39+
40+
cache.set('key-3', 18);
41+
cache.set('key-4', 19);
42+
expect(cache.get('key-2')).toBeUndefined();
43+
expect(cache.get('key-3')).toBeUndefined();
44+
expect(cache.get('key-4')).toBe(19);
45+
});
46+
47+
it('should evict least recently used items from cache with cache size of 2', () => {
48+
const cache = new LRUCache(2);
49+
expect(cache.get('key-21')).toBeUndefined();
50+
51+
cache.set('key-21', 15);
52+
expect(cache.get('key-21')).toBe(15);
53+
54+
cache.set('key-22', 16);
55+
expect(cache.get('key-21')).toBe(15);
56+
expect(cache.get('key-22')).toBe(16);
57+
58+
cache.set('key-22', 17);
59+
expect(cache.get('key-22')).toBe(17);
60+
61+
cache.set('key-23', 18);
62+
expect(cache.get('key-21')).toBeUndefined();
63+
expect(cache.get('key-22')).toBe(17);
64+
expect(cache.get('key-23')).toBe(18);
65+
66+
cache.set('key-24', 19);
67+
expect(cache.get('key-21')).toBeUndefined();
68+
expect(cache.get('key-22')).toBeUndefined();
69+
expect(cache.get('key-23')).toBe(18);
70+
expect(cache.get('key-24')).toBe(19);
71+
});
72+
73+
it('should evict least recently used items from cache with cache size of 3', () => {
74+
const cache = new LRUCache(3);
75+
76+
cache.set('key-1', 1);
77+
cache.set('key-2', 2);
78+
cache.set('key-3', 3);
79+
expect(cache.get('key-1')).toBe(1);
80+
expect(cache.get('key-2')).toBe(2);
81+
expect(cache.get('key-3')).toBe(3);
82+
83+
cache.set('key-3', 4);
84+
expect(cache.get('key-1')).toBe(1);
85+
expect(cache.get('key-2')).toBe(2);
86+
expect(cache.get('key-3')).toBe(4);
87+
88+
cache.set('key-4', 5);
89+
expect(cache.get('key-1')).toBeUndefined();
90+
expect(cache.get('key-2')).toBe(2);
91+
expect(cache.get('key-3')).toBe(4);
92+
expect(cache.get('key-4')).toBe(5);
93+
});
94+
95+
it('should promote the node while calling set() method', () => {
96+
const cache = new LRUCache(2);
97+
98+
cache.set('2', 1);
99+
cache.set('1', 1);
100+
cache.set('2', 3);
101+
cache.set('4', 1);
102+
expect(cache.get('1')).toBeUndefined();
103+
expect(cache.get('2')).toBe(3);
104+
});
105+
106+
it('should promote the recently accessed item with cache size of 3', () => {
107+
const cache = new LRUCache(3);
108+
109+
cache.set('key-1', 1);
110+
cache.set('key-2', 2);
111+
cache.set('key-3', 3);
112+
expect(cache.get('key-1')).toBe(1);
113+
114+
cache.set('key-4', 4);
115+
expect(cache.get('key-1')).toBe(1);
116+
expect(cache.get('key-3')).toBe(3);
117+
expect(cache.get('key-4')).toBe(4);
118+
expect(cache.get('key-2')).toBeUndefined();
119+
});
120+
121+
it('should promote the recently accessed item with cache size of 4', () => {
122+
const cache = new LRUCache(4);
123+
124+
cache.set('key-1', 1);
125+
cache.set('key-2', 2);
126+
cache.set('key-3', 3);
127+
cache.set('key-4', 4);
128+
expect(cache.get('key-4')).toBe(4);
129+
expect(cache.get('key-3')).toBe(3);
130+
expect(cache.get('key-2')).toBe(2);
131+
expect(cache.get('key-1')).toBe(1);
132+
133+
cache.set('key-5', 5);
134+
expect(cache.get('key-1')).toBe(1);
135+
expect(cache.get('key-2')).toBe(2);
136+
expect(cache.get('key-3')).toBe(3);
137+
expect(cache.get('key-4')).toBeUndefined();
138+
expect(cache.get('key-5')).toBe(5);
139+
140+
cache.set('key-6', 6);
141+
expect(cache.get('key-1')).toBeUndefined();
142+
expect(cache.get('key-2')).toBe(2);
143+
expect(cache.get('key-3')).toBe(3);
144+
expect(cache.get('key-4')).toBeUndefined();
145+
expect(cache.get('key-5')).toBe(5);
146+
expect(cache.get('key-6')).toBe(6);
147+
});
148+
});

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.