工作中可能會使用到的數(shù)據(jù)結構和算法
背景
我們?nèi)粘５拈_發(fā)工作避免不了和數(shù)據(jù)打交道。展示數(shù)據(jù)時，接口返回的數(shù)據(jù)結構可能沒辦法直接拿來使用，需要做一層轉換；保存數(shù)據(jù)時，通過表單拿到的數(shù)據(jù)結構和接口定義的數(shù)據(jù)結構也可能不一致，需要做一層轉換；還有一些業(yè)務場景本身的需要，需要對數(shù)據(jù)的邏輯校驗等。因此避免不了會使用到一些常用的數(shù)據(jù)結構和算法。本文主要是討論在前端開發(fā)工作中，可能會使用到的數(shù)據(jù)結構和算法。
數(shù)據(jù)結構
棧
棧是一種特殊的線性表。它的特點是，只能在表的一端操作?？梢圆僮鞯亩朔Q為棧頂，不可以操作的另一端稱為棧底。棧的特性：先進后出。
原理
生活中的例子：蒸饅頭的籠屜、羽毛球筒。
實現(xiàn)
我們可以使用 JS 來模擬棧的功能。從數(shù)據(jù)存儲的方式來看，可以使用數(shù)組存儲數(shù)據(jù)，也可以使用鏈表存儲數(shù)據(jù)。因為數(shù)組是最簡單的方式，所以這里是用數(shù)組的方式來實現(xiàn)棧。
棧的操作包括入棧、出棧、清空、獲取棧頂元素、獲取棧的大小等。
class Stack {
constructor() {
// 存儲數(shù)據(jù)
this.items = [];
}
push(item) {
// 入棧
this.items.push(item);
}
pop() {
// 出棧
return this.items.pop();
}
top() {
// 獲取棧頂元素
return this.items[this.items.length - 1];
}
clear() {
// 清空棧
this.items = [];
}
size() {
// 獲取棧的大小
return this.items.length;
}
isEmpty() {
// 判斷棧是否為空
return this.items.length === 0;
}
}
應用
判斷括號是否匹配
方法一思路分析：
首先從頭到尾遍歷整個字符串； 當遇到字符"("則入棧，遇到字符")"則出棧； 出棧時，如果棧已經(jīng)為空，則返回 false； 當字符串遍歷完畢以后，判斷棧是否為空。
方法二思路分析：
聲明變量 num 為 0，并從頭到尾遍歷整個字符串； 當遇到字符"("則 num 加 1，遇到字符")"num 減 1； 在遍歷的過程中，當 num 減 1 時，num 的值已經(jīng)為 0 則返回 false； 當字符串遍歷完畢以后，判斷 num 是否為 0。
// 方式一：棧
function isPairing(str = '') {
const stack = new Stack();
for(let i of str) {
if (i === '(') {
stack.push(i);
} else if (i === ')') {
if (stack.isEmpty()) {
return false;
} else {
stack.pop();
}
}
}
return stack.size() === 0;
}
// 方式二：計數(shù)
function isPairing(str = '') {
let num = 0;
for(let i of str) {
if (i === '(') {
num++;
} else if (i === ')') {
if (num === 0) {
return false;
} else {
num--;
}
}
}
return num === 0;
}
判斷 HTML 標簽是否匹配
思路分析：
聲明變量 stack、nodes；并從頭遍歷 HTML 字符串，查找字符"<"的位置；
如果字符"<"的位置等于 0：
則繼續(xù)嘗試匹配 HTML 結束標簽，匹配成功并且與棧頂?shù)臉撕灻Q一致，則彈出棧頂；否則報錯； 匹配 HTML 結束標簽失敗以后，則嘗試匹配開始標簽的起始部分，然后循環(huán)匹配標簽屬性對，最后匹配開始標簽的結束部分。匹配完成以后，將匹配到的標簽壓入棧頂；并構建 node 節(jié)點數(shù)； 如果字符"<"的位置大于 0：
則 html.slice(0, pos)，創(chuàng)建文本節(jié)點。
function parseHtml(html = '') {
const startIndex = 0;
const endIndex = 0;
// 匹配標簽<div>、<br/>等標簽的開始部分"<div、<br"
const startTagOpen = /^<([a-zA-Z\d]+)/;
// 匹配標簽<div>、<br/>等標簽的閉合部分">、/>"
const startTagClose = /^\s*(\/?)>/;
// 匹配屬性
const attribute = /^\s*([\w-]+)(?:="([^"]*)")?\s*/;
// 匹配閉合標簽，例如</div>、</p>
const endTag = /^<\/([a-zA-Z\d]+)>/;
const stack = [];
const nodes = [];
while(html) {
// 查找<的起始位置
const index = html.indexOf('<');
if (index === 0) {
// 先匹配整體結束標簽，例如</div>、</p>
let endTagMatch = html.match(endTag);
if (endTagMatch) {
if (stack[stack.length - 1]) {
if (stack[stack.length - 1].tag === endTagMatch[1]) {
// 出棧
stack.pop();
advanced(endTagMatch[0].length);
continue;
} else {
throw new Error(`起始標簽和結束標簽不匹配: 起始標簽（${stack[stack.length - 1].tag}），結束標簽（${endTagMatch[0]}）`);
}
} else {
throw new Error(`${endTagMatch[0]}沒有起始標簽`);
}
}
// 然后匹配起始標簽的開始部分，例如<div>的<div、<p>的<p、<br/>的<br
let startTagOpenMatch = html.match(startTagOpen);
if (startTagOpenMatch) {
const node = {
nodeType: 1,
tag: startTagOpenMatch[1],
attrs: [],
children: [],
};
advanced(startTagOpenMatch[0].length);
let end, attr;
// 匹配標簽屬性列表
while(!(end = html.match(startTagClose)) && (attr = html.match(attribute))) {
advanced(attr[0].length);
node.attrs.push({
name: attr[1],
value: attr[2],
});
}
// 匹配起始標簽的結束部分
if (end) {
if (stack.length === 0) {
nodes.push(node);
} else {
stack[stack.length - 1].children.push(node);
}
// 自閉和標簽不加入棧中
if (end[1] !== '/') {
stack.push(node);
}
advanced(end[0].length);
}
}
} else {
// 文本
const node = {
nodeType: 3,
textContent: html.slice(0, index)
};
if (stack.length === 0) {
nodes.push(node);
} else {
stack[stack.length - 1].children.push(node);
}
advanced(node.textContent.length);
}
}
function advanced(n) {
html = html.substring(n);
}
return nodes;
}
parseHtml('<div id="test" class="a b"></div>');
parseHtml('<div id="test" class="a b">Hello World</div>');
parseHtml('開始<div id="test" class="a b">Hello World</div>');
parseHtml('<div id="test" class="a b"><br class="br" />Hello World</div>');
parseHtml('</div>');
parseHtml('<div></p>');
版本號比較大小
思路分析：
版本號 v1、v2 按照符號"."分割成數(shù)組，從左右依次進行大小比較； v1 大于 v2 返回 1，v2 小于 v2 返回-1，v1 等于 v2 返回 0。
/*
比較版本號大小
v1：第一個版本號
v2：第二個版本號
如果版本號相等，返回 0, * 如果第一個版本號低于第二個，返回 -1，否則返回 1.
*/
function compareVersion(v1, v2) {
if (!v1 && !v2) return 0;
if (!v1) return -1;
if (!v2) return 1;
const v1Stack = v1.split('.');
const v2Stack = v2.split('.');
const maxLen = Math.max(v1Stack.length, v2Stack.length);
for(let i = 0; i < maxLen; i++) {
// 必須轉整，否則按照字符順序比較大小
const prevVal = ~~v1Stack[i];
const currVal = ~~v2Stack[i];
if (prevVal > currVal) {
return 1;
}
if (prevVal < currVal) {
return -1;
}
}
return 0;
}
console.log(compareVersion("2.2.1", "2.2.01")); // 0
console.log(compareVersion("2.2.1", "2.2.0")); // 1
console.log(compareVersion("2.2.1", "2.1.9")); // 1
console.log(compareVersion("2.2", "2.1.1")); // 1
console.log(compareVersion("2.2", "2.2.1")); // -1
console.log(compareVersion("2.2.3.4.5.6", "2.2.2.4.5.12")); // 1
console.log(compareVersion("2.2.3.4.5.6", "2.2.3.4.5.12")); // -1
用途
Vue 模板編譯將模板字符串轉換成 AST。 自動更新最新版本的 NPM 包。 函數(shù)執(zhí)行上下文棧。
隊列
隊列也是一種特殊的線性表，它的特點是，只能在表的一端進行刪除操作，而在表的另一點進行插入操作?？梢赃M行刪除操作的端稱為隊首，而可以進行插入操作的端稱為隊尾。刪除一個元素稱為出隊，插入一個元素稱為入隊。和棧一樣，隊列也是一種操作受限制的線性表。隊列的特性：先進先出 (FIFO，F(xiàn)irst-In-First-Out)。
原理
生活中的例子：排隊買東西。
實現(xiàn)
我們也可以使用 JS 來模擬隊列的功能。從數(shù)據(jù)存儲的方式來看，可以使用數(shù)組存儲數(shù)據(jù)，也可以使用鏈表存儲數(shù)據(jù)。因為數(shù)組是最簡單的方式，所以這里是用數(shù)組的方式來實現(xiàn)隊列。
隊列的操作包括入隊、出隊、清空隊列、獲取隊頭元素、獲取隊列的長度等。
class Queue {
constructor() {
// 存儲數(shù)據(jù)
this.items = [];
}
enqueue(item) {
// 入隊
this.items.push(item);
}
dequeue() {
// 出隊
return this.items.shift();
}
head() {
// 獲取隊首的元素
return this.items[0];
}
tail() {
// 獲取隊尾的元素
return this.items[this.items.length - 1];
}
clear() {
// 清空隊列
this.items = [];
}
size() {
// 獲取隊列的長度
return this.items.length;
}
isEmpty() {
// 判斷隊列是否為空
return this.items.length === 0;
}
}
應用
約瑟夫環(huán)問題
有一個數(shù)組存放了 100 個數(shù)據(jù) 0-99，要求每隔兩個數(shù)刪除一個數(shù)，到末尾時再循環(huán)至開頭繼續(xù)進行，求最后一個被刪除的數(shù)字。
思路分析
創(chuàng)建隊列，將 0 到 99 的數(shù)字入隊； 循環(huán)隊列，依次出列隊列中的數(shù)字，對當前出隊的數(shù)字進行計數(shù) index + 1； 判斷當前出列的 index % 3 是否等于 0，如果不等于 0 則入隊； 直到隊列的長度為 1，退出循環(huán)，返回隊列中的數(shù)字。
function ring(arr) {
const queue = new Queue();
arr.forEach(v => queue.enqueue(v));
let index = 0;
while(queue.size() > 1) {
const item = queue.dequeue();
if (++index % 3 !== 0) {
queue.enqueue(item);
}
}
return queue.head();
}
斐波那契數(shù)列
斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學上，斐波那契數(shù)列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。
function fiboSequence(num) {
if (num < 2) return num;
const queue = [];
queue.push(0);
queue.push(1);
for(let i = 2; i < num; i++) {
const len = queue.length;
queue.push(queue[len - 2] + queue[len - 1]);
}
return queue;
}
打印楊輝三角
思路分析：
通過觀察發(fā)現(xiàn)，三角中的每一行數(shù)據(jù)都依賴于上一行的數(shù)據(jù)； 我們首先創(chuàng)建隊列 queue，用于存儲每一行的數(shù)據(jù)，供下一行數(shù)據(jù)使用； 然后初始化第一行的數(shù)據(jù) 1 入隊，這里需要兩個 for 循環(huán)嵌套，外層的 for 循環(huán)決定最終打印的總行數(shù)，內(nèi)層的 for 循環(huán)生成每行的數(shù)據(jù)； 在生成當前行的數(shù)據(jù)時，將隊列中的數(shù)據(jù)源依次出隊，然后將新生成的數(shù)據(jù)入隊；并記錄當前出隊的數(shù)據(jù)，供生成新數(shù)據(jù)使用。
function printYangHui(num) {
const queue = [];
// 存儲第一行數(shù)據(jù)
queue.push(1);
for(let i = 1; i <= num; i++) {
let rowArr = [];
// 填充空格
for(let j = 0; j < Math.floor((num - i) / 2); j++) {
rowArr.push('');
}
let prev = 0;
for(let j = 0; j < i; j++) {
const num = queue.shift();
queue.push(prev + num);
rowArr.push(num);
prev = num;
}
queue.push(1);
console.log(rowArr.join(' '));
}
}
printYangHui(10);
用途
實現(xiàn)洋蔥模型
完善代碼，實現(xiàn)輸出 1、2、3。
function createApp(){
return {
use(fn){},
run(){},
}
}
const app = createApp();
app.use((next)=>{
setTimeout(function(){
next();
})
console.log(new Date() ,'1');
})
app.use((next)=>{
console.log(new Date() ,'2');
next();
})
app.use((next)=>{
console.log(new Date() ,'3');
next();
})
app.run();
消息隊列
鏈表
由若干個結點鏈結成一個鏈表，稱之為鏈式存儲結構。
鏈表和數(shù)組的區(qū)別
鏈表和數(shù)組都可以存儲多個數(shù)據(jù)，那么鏈表和數(shù)組有什么區(qū)別呢？
數(shù)組需要一塊連續(xù)的內(nèi)存空間來存儲數(shù)據(jù)，對內(nèi)存的要求比較高。而鏈表卻相反，它并不需要一塊連續(xù)的內(nèi)存空間。鏈表是通過指針將一組零散的內(nèi)存塊串聯(lián)在一起。
相比數(shù)組，鏈表是一種稍微復雜一點的數(shù)據(jù)結構。兩者沒有好壞之分，各有各的優(yōu)缺點。
由于內(nèi)存存儲特性，數(shù)組可以實現(xiàn)快速的查找元素，但是在插入和刪除時就需要移動大量的元素。原因就在于相鄰元素在內(nèi)存中的位置也是緊挨著的，中間沒有空隙，因此就無法快速添加元素。而當刪除后，內(nèi)存空間中就會留出空隙，自然需要彌補。
分類
單向鏈表
雙向鏈表
單向循環(huán)鏈表
雙向循環(huán)鏈表
實現(xiàn)
const Node = function (data) {
this.data = data;
this.next = null;
}
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
node1.next = node2;
node2.next = node3;
應用
環(huán)形鏈表
給定一個鏈表，如何判斷鏈表中是否有環(huán)？
思路分析：
首先創(chuàng)建兩個指針 1 和 2，同時指向這個鏈表的頭節(jié)點。然后開始一個大循環(huán)，在循環(huán)體中，讓指針 1 每次向下移動一個節(jié)點，讓指針 2 每次向下移動兩個節(jié)點，然后比較兩個指針指向的節(jié)點是否相同。如果相同，則判斷出鏈表有環(huán)，如果不同，則繼續(xù)下一次循環(huán)。 例如鏈表 A->B->C->D->B->C->D，兩個指針最初都指向節(jié)點 A，進入第一輪循環(huán)，指針 1 移動到了節(jié)點 B，指針 2 移動到了 C。第二輪循環(huán)，指針 1 移動到了節(jié)點 C，指針 2 移動到了節(jié)點 B。第三輪循環(huán)，指針 1 移動到了節(jié)點 D，指針 2 移動到了節(jié)點 D，此時兩指針指向同一節(jié)點，判斷出鏈表有環(huán)。 假設從鏈表頭節(jié)點到入環(huán)點的距離是 D，鏈表的環(huán)長是 S。那么循環(huán)會進行 S 次，可以簡單理解為 O（N）。除了兩個指針以外，沒有使用任何額外存儲空間，所以空間復雜度是 O（1）。
const Node = function (data) {
this.data = data;
this.next = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const nodeD = new Node('D');
const nodeE = new Node('E');
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeC;
function isCircularLinkedList(head) {
if (head === null || head.next === null) {
return false;
}
let point1 = head;
let point2 = head;
do {
point1 = point1.next;
point2 = point2.next && point2.next.next;
} while(point1 && point2 && point1 !== point2);
if (point1 === point2) {
return true;
}
return false;
}
console.log(isCircularLinkedList(nodeA));
相交鏈表
判斷兩個單鏈表是否相交并求出相交的第一結點。
思路分析：
兩個沒有環(huán)的鏈表如果是相交于某一結點，如上圖所示，這個結點后面都是共有的。所以如果兩個鏈表相交，那么兩個鏈表的尾結點的地址也是一樣的。程序?qū)崿F(xiàn)時分別遍歷兩個單鏈表，直到尾結點。判斷尾結點地址是否相等即可。時間復雜度為 O(L1+L2)。 如何找到第一個相交結點？判斷是否相交的時候，記錄下兩個鏈表的長度，算出長度差 len，接著先讓較長的鏈表遍歷 len 個長度，然后兩個鏈表同時遍歷，判斷是否相等，如果相等，就是第一個相交的結點。
function intersectNode(head1, head2) {
if (head1 && head2) {
// 計算鏈表的長度
let len1 = 0, p = head1;
let len2 = 0, q = head2;
while(p.next) {
len1++;
p = p.next;
}
while(q.next) {
len2++;
q = q.next;
}
if (p === q) {
// p指向短鏈，q指向長鏈
let len = 0;
if (len1 > len2) {
len = len1 - len2;
p = head2;
q = head1;
} else {
len = len2 - len1;
p = head1;
q = head2;
}
while(len > 0) {
len--;
q = q.next;
}
while(p && q && p !== q) {
p = p.next;
q = q.next;
}
return p;
}
}
return null;
}
const Node = function (data) {
this.data = data;
this.next = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const node1 = new Node('1');
const node2 = new Node('2');
const node3 = new Node('3');
const nodeD4 = new Node('D4');
const nodeE5 = new Node('E5');
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD4;
node1.next = node2;
node2.next = node3;
node3.next = nodeD4;
nodeD4.next = nodeE5;
console.log(intersectNode(nodeA, node1));
回文鏈表
請判斷一個鏈表是否為回文鏈表。
思路分析：
從頭遍歷鏈表，同時正向和反向拼接每個鏈表的數(shù)據(jù)，最后比對正向和反向得到的字符串是否相等。如果相等則是回文鏈表；否則不是。
const Node = function (data) {
this.data = data;
this.next = null;
}
const node1 = new Node('A');
const node2 = new Node('B');
const node3 = new Node('C');
const node4 = new Node('C');
const node5 = new Node('B');
const node6 = new Node('A');
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
const isPalindrome = head => {
let a = '', b = '';
while(head !== null) {
a = a + head.data;
b = head.data + b;
head = head.next;
}
return a === b;
}
console.log(isPalindrome(node1));
用途
原型鏈 作用域鏈
樹
樹是一種數(shù)據(jù)結構，它是由 n(n>=1)個有限節(jié)點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
分類
無序樹：樹中任意節(jié)點的子結點之間沒有順序關系，這種樹稱為無序樹,也稱為自由樹。 有序樹：樹中任意節(jié)點的子結點之間有順序關系，這種樹稱為有序樹。 二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹。 滿二叉樹：葉節(jié)點除外的所有節(jié)點均含有兩個子樹的樹被稱為滿二叉樹。 完全二叉樹：除最后一層外，所有層都是滿節(jié)點，且最后一層缺右邊連續(xù)節(jié)點的二叉樹稱為完全二叉樹（堆就是一個完全二叉樹）。 哈夫曼樹（最優(yōu)二叉樹）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。
實現(xiàn)
// 二叉樹的實現(xiàn)
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const nodeD = new Node('D');
const nodeE = new Node('E');
const nodeF = new Node('F');
const nodeG = new Node('G');
nodeA.left = nodeB;
nodeA.right = nodeC;
nodeB.left = nodeD;
nodeB.right = nodeE;
nodeC.left = nodeF;
nodeC.right = nodeG;
我們?nèi)粘９ぷ髦薪佑|到最多的是多叉樹。
遍歷
深度優(yōu)先遍歷
先序遍歷
先序遍歷（又稱先根遍歷）為 ABDECFG（根-左-右）。
中序遍歷
中序遍歷（又稱中根遍歷）為 DBEAFCG（左-根-右）（僅二叉樹有中序遍歷）。
后序遍歷
后序遍歷（又稱后根遍歷）為 DEBFGCA（左-右-根）。
廣度優(yōu)先遍歷
層序遍歷
層序遍歷為 ABCDEFG。
用途
樹的扁平化（展示 OCR 識別結果） 扁平化數(shù)組轉換成樹（標簽樹）
圖
圖（Graph）結構是一種非線性的數(shù)據(jù)結構，圖在實際生活中有很多例子，比如交通運輸網(wǎng)，地鐵網(wǎng)絡，等等都可以抽象成圖結構。圖結構比樹結構復雜的非線性結構。
圖是由若干個頂點和邊組成。
分類
無向圖
如果一個圖結構中，所有的邊都沒有方向性，那么這種圖便稱為無向圖。
有向圖
一個圖結構中，邊是有方向性的，那么這種圖就稱為有向圖。
加權圖
如果給邊加上一個值表示權重，這種圖就是加權圖。
連通圖
如果圖中任意兩個節(jié)點都能找到路徑可以將它們進行連接，則稱該圖為連通圖。
表示
圖有兩種表示方法：鄰接矩陣、鄰接鏈表。不同的場景及算法可能需要不同的圖表示方式，一般情況下當結點數(shù)量非常龐大時，會造成矩陣非常稀疏，空間開銷會較大，此時使用鄰接鏈表的表示方式會占用較少的空間。而如果是稠密矩陣或者需要快速判斷任意兩個結點是否有邊相連等情況，可能鄰接矩陣更合適。
鄰接矩陣
鄰接鏈表
遍歷
深度優(yōu)先遍歷 廣度優(yōu)先遍歷
用途
商品分類選擇
算法
LRU
LRU 是 Least Recently Used 的縮寫，即最近最少使用，是一種常用的頁面置換算法，將最近最久未使用的頁面予以淘汰。
核心的思想就是“如果數(shù)據(jù)最近被訪問，那么將來被訪問的幾率也就更高”。
原理
實現(xiàn)
思路分析：
選擇合適的數(shù)據(jù)結構。
哈希表：O(1) 級別的時間復雜度，適合數(shù)據(jù)查找。但是元素無序，沒辦法判斷元素訪問的先后順序。 數(shù)組：元素的插入和刪除元素都是 O(n)。 單向鏈表：刪除節(jié)點需要訪問前驅(qū)節(jié)點，需要花 O(n)從前遍歷查找。 雙向鏈表：結點有前驅(qū)指針，刪除和移動節(jié)點都是指針的變動，都是 O(1)。
結論：哈希表 + 雙向鏈表。
使用哈希表的目的就是快速訪問到存儲在雙向鏈表中的數(shù)據(jù)，存儲雙向鏈表的 key 和節(jié)點的引用；使用雙向鏈表的目的就是快速進行節(jié)點位置的移動和刪除，存儲 key 和對應的數(shù)據(jù)。
設置虛擬節(jié)點，方便快速的訪問頭尾節(jié)點。初始時沒有添加真實的節(jié)點，所以需要將虛擬節(jié)點的前驅(qū)指針和后繼指針指向自己。
get 方法的實現(xiàn)。
put 方法的實現(xiàn)。
寫入新數(shù)據(jù)，需要先檢查一下當前節(jié)點數(shù)量；如果節(jié)點數(shù)量達到容量的最大值，則需要先刪除鏈表尾部的節(jié)點，然后創(chuàng)建新的節(jié)點，添加到鏈表頭部，并寫入到哈希表。 寫入已存在的數(shù)據(jù)，則更新數(shù)據(jù)值，移動節(jié)點位置到鏈表頭部。
function Node(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // 容量
this.hash = {}; // 哈希表
this.count = 0; // 當前節(jié)點數(shù)量
this.virtualNode = new Node(); // 虛擬結點
// 相互引用
this.virtualNode.next = this.virtualNode;
this.virtualNode.prev = this.virtualNode;
}
get(key) {
const node = this.hash[key];
if (node) {
this.moveToHead(node);
return node.value;
}
}
put(key, value) {
const node = this.hash[key];
if (node) {
node.value = value;
this.moveToHead(node);
} else {
if (this.count === this.capacity) {
this.removeLRUItem();
}
const newNode = new Node(key, value);
this.hash[key] = newNode;
this.addToHead(newNode);
this.count++;
}
}
remove(key) {
const node = this.hash[key];
if (node) {
this.removeFromList(node);
Reflect.deleteProperty(this.hash, key);
this.count--;
}
}
isEmpty() {
return this.count === 0;
}
moveToHead(node) {
this.removeFromList(node);
this.addToHead(node);
}
removeFromList(node) {
const prevNode = node.prev;
const nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
node.prev = null;
node.next = null;
}
addToHead(node) {
const nextNode = this.virtualNode.next;
this.virtualNode.next = node;
nextNode.prev = node;
node.prev = this.virtualNode;
node.next = nextNode;
}
removeLRUItem() {
const tailNode = this.virtualNode.prev;
this.remove(tailNode.key);
}
}
const cache = new LRUCache(5);
console.log(cache.isEmpty());
cache.put('A', 'A');
cache.put('B', 'B');
cache.put('C', 'C');
cache.put('D', 'D');
cache.put('E', 'E');
console.log(cache.get('A'));
cache.put('F', 'F');
console.log(cache.get('B'));
console.log(cache.isEmpty());
cache.remove('E');
cache.remove('F');
cache.remove('A');
cache.remove('C');
cache.remove('D');
console.log(cache.isEmpty());
console.log(cache);
用途
歷史瀏覽記錄。 緩存淘汰策略。
我們來自字節(jié)跳動，是旗下大力教育前端部門，負責字節(jié)跳動教育全線產(chǎn)品前端開發(fā)工作。
我們圍繞產(chǎn)品品質(zhì)提升、開發(fā)效率、創(chuàng)意與前沿技術等方向沉淀與傳播專業(yè)知識及案例，為業(yè)界貢獻經(jīng)驗價值。包括但不限于性能監(jiān)控、組件庫、多端技術、Serverless、可視化搭建、音視頻、人工智能、產(chǎn)品設計與營銷等內(nèi)容。
歡迎感興趣的同學在評論區(qū)或使用內(nèi)推碼內(nèi)推到作者部門拍磚哦 ??
字節(jié)跳動校/社招投遞鏈接: https://job.toutiao.com/s/eGrF9qQ
評論
圖片
表情