LUR缓存实现
以下是 JavaScript 实现 LRU 缓存的详细解析,结合核心原理与代码实现,并标注来源:
一、LRU 缓存核心原理
LRU(Least Recently Used)缓存淘汰策略的核心思想是:当缓存容量满时,优先淘汰最久未使用的数据。其实现需满足以下要求:
- 快速访问:
get
和put
操作需达到 O(1) 时间复杂度。 - 动态调整顺序:访问数据时需将其移动到“最近使用”位置。
class LRUCache {constructor(capacity) {this.cache = new Map();this.capacity = capacity;}get(key) {if (!this.cache.has(key)) return -1;const value = this.cache.get(key);this.cache.delete(key); // 删除后重新插入保证顺序this.cache.set(key, value);return value;}put(key, value) {if (this.cache.has(key)) this.cache.delete(key);this.cache.set(key, value);if (this.cache.size > this.capacity) {// 删除最久未使用的键(Map的迭代顺序保证)this.cache.delete(this.cache.keys().next().value);}}
}
二、JavaScript 实现方案
1. 基于 Map 的实现(推荐)
JavaScript 的 Map
对象天然保持键的插入顺序,迭代时按插入顺序返回键。利用这一特性,可实现简洁的 LRU 缓存。
代码实现:
class LRUCache {constructor(capacity) {this.capacity = capacity;this.cache = new Map();}get(key) {if (!this.cache.has(key)) return -1;// 访问后移动到尾部(最近使用)const value = this.cache.get(key);this.cache.delete(key);this.cache.set(key, value);return value;}put(key, value) {if (this.cache.has(key)) {// 更新值并移动到尾部this.cache.delete(key);} else if (this.cache.size >= this.capacity) {// 缓存满时删除头部(最久未使用)this.cache.delete(this.cache.keys().next().value);}// 插入新键到尾部this.cache.set(key, value);}
}
关键操作解析:
• get
方法:若键存在,删除旧值并重新插入到尾部,表示最近访问过。
• put
方法:若键存在,更新值并调整位置;若不存在,插入新键。若超出容量,删除头部键。
2. 基于双向链表 + Map 的实现
通过自定义双向链表节点和链表类,可更直观地维护节点顺序。
代码实现:
class Node {constructor(key, value) {this.key = key;this.value = value;this.prev = null;this.next = null;}
}class LRUCache {constructor(capacity) {this.capacity = capacity;this.map = new Map();this.head = new Node(0, 0); // 头哨兵this.tail = new Node(0, 0); // 尾哨兵this.head.next = this.tail;this.tail.prev = this.head;}get(key) {if (!this.map.has(key)) return -1;const node = this.map.get(key);this.moveToHead(node);return node.value;}put(key, value) {if (this.map.has(key)) {const node = this.map.get(key);node.value = value;this.moveToHead(node);} else {const newNode = new Node(key, value);this.map.set(key, newNode);this.addToHead(newNode);if (this.map.size > this.capacity) {const lruNode = this.removeTail();this.map.delete(lruNode.key);}}}moveToHead(node) {this.removeNode(node);this.addToHead(node);}removeNode(node) {node.prev.next = node.next;node.next.prev = node.prev;}addToHead(node) {node.next = this.head.next;node.prev = this.head;this.head.next.prev = node;this.head.next = node;}removeTail() {const node = this.tail.prev;this.removeNode(node);return node;}
}
关键操作解析:
• 双向链表:维护节点顺序,addToHead
和 removeNode
操作均为 O(1)。
• get
方法:访问节点后将其移动到头部。
• put
方法:插入新节点到头部,超出容量时删除尾部节点。
三、性能分析
• 时间复杂度:get
和 put
均为 O(1),因 Map 和双向链表的插入/删除操作均为常数时间。
• 空间复杂度:O(capacity),需存储所有缓存项。
四、扩展与优化
- 惰性删除:结合
WeakMap
实现惰性过期,自动清理过期数据。 - 并发控制:在高并发场景中,使用锁机制或线程安全容器(如
synchronized
包)。 - 容量动态调整:根据系统负载动态调整缓存容量。
总结
JavaScript 实现 LRU 缓存的核心在于 Map + 双向链表 的组合,或直接利用 Map
的有序特性。推荐使用第一种方案(基于 Map),代码简洁且性能高效。如需更复杂的缓存策略(如 TTL),可参考 Node.js 的 lru-cache
库。
new关键字实现
以下是 JavaScript 实现 new
操作符的详细解析,结合核心原理与代码实现,并标注来源:
一、new
操作符的核心作用
new
操作符用于创建一个构造函数的实例对象,并完成以下任务:
- 创建新对象:生成一个空对象。
- 绑定原型链:将新对象的原型指向构造函数的
prototype
。 - 绑定
this
:将构造函数内部的this
绑定到新对象。 - 处理返回值:若构造函数返回对象,则返回该对象;否则返回新创建的对象。
二、new
的执行流程
-
创建新对象
const obj = {}; // 或 Object.create(Constructor.prototype)
生成一个空对象,后续通过原型链继承构造函数的方法。
-
设置原型链
obj.__proto__ = Constructor.prototype; // 或 Object.setPrototypeOf(obj, Constructor.prototype)
使新对象可访问构造函数原型上的属性和方法。
-
绑定
this
并执行构造函数const result = Constructor.apply(obj, args);
将构造函数的
this
绑定到新对象,并传入参数执行。 -
返回结果
return result instanceof Object ? result : obj;
若构造函数返回对象,则返回该对象;否则返回新创建的对象。
三、手写 new
操作符的实现
基础版本
function myNew(Constructor, ...args) {const obj = Object.create(Constructor.prototype); // const result = Constructor.apply(obj, args); // return result instanceof Object ? result : obj; //
}
优化版本
增加类型检查与错误处理:
function myNew(Constructor, ...args) {if (typeof Constructor !== 'function') {throw new TypeError('Constructor must be a function');}const obj = Object.create(Constructor.prototype);try {return Constructor.apply(obj, args);} catch (error) {throw error;}
}
四、特殊情况与注意事项
-
构造函数返回值的影响
• 若返回原始值(如数字、字符串),new
会忽略并返回新对象。
• 若返回对象,则直接返回该对象(原型链断裂)。function Test() { return { foo: 'bar' }; } const t = new Test(); // t 是 { foo: 'bar' }, 而非 Test 的实例
-
忘记使用
new
的问题
直接调用构造函数会导致this
指向全局对象(如window
),引发全局变量污染。function Person() { this.name = '张三'; } Person(); // window.name = '张三'
-
箭头函数的限制
箭头函数没有自己的this
,无法作为构造函数使用。const Person = (name) => { this.name = name; }; new Person(); // TypeError: Person is not a constructor
五、实际应用场景
-
创建对象实例
function User(name, role) { this.name = name; this.role = role; } const admin = new User('admin', 'administrator');
-
实现继承
function Animal(name) { this.name = name; } function Dog(name, breed) {Animal.call(this, name); // 调用父类构造函数this.breed = breed; } Dog.prototype = Object.create(Animal.prototype); // 设置原型链
总结
new
操作符通过 创建对象→绑定原型→绑定 this
→处理返回值 四步实现实例化。手写实现时需注意类型检查、错误处理及返回值判断。理解其原理有助于掌握 JavaScript 的面向对象编程,并在面试中应对相关问题。
大数相加
-
字符串逐位相加:将大数转换为字符串,逐位相加并处理进位。这在多个网页中都有提到,比如网页[1]、[6]、[7]、[8]都详细描述了这种方法。特别是网页[7]和[8]提供了具体的代码示例,应该引用这些网页。
-
使用BigInt类型:网页[5]和[4]提到,BigInt可以处理任意精度的整数,但只能用于整数,不能处理小数。需要指出这一点,并引用相关网页。
-
第三方库:网页[1]、[2]、[3]、[4]、[5]都推荐了decimal.js、bignumber.js等库,这些库专门处理高精度计算,适合复杂场景。需要引用这些网页中的例子,比如网页[1]提到的bignumber.js和网页[2]中的decimal.js。
-
转换为整数计算:网页[2]、[3]、[4]提到将小数转换为整数进行计算,适用于固定小数位数的场景。例如,网页[2]中的示例代码展示了这种方法,需要引用网页[2]。
-
处理特殊情况:比如进位处理和结果反转,这在网页[6]、[7]、[8]的代码示例中都有体现,需要指出这些细节并引用对应的网页。
以下是 JavaScript 实现大数相加(精度处理) 的详细解决方案,结合不同场景需求与实现原理:
一、核心问题与解决方案分类
JavaScript 的 Number
类型基于 IEEE 754 双精度浮点数表示,无法精确处理超过 2^53-1 的整数或高精度小数。大数相加的精度问题主要表现为:
• 整数溢出:如 9007199254740992 + 1 = 9007199254740992
(超出安全整数范围)。
• 浮点数精度丢失:如 0.1 + 0.2 = 0.30000000000000004
。
二、主要实现方案
1. 字符串逐位相加(推荐)
原理:将大数转换为字符串,逐位模拟手工加法,处理进位。
代码实现:
function addLargeNumbers(num1, num2) {const a = num1.toString().split('').reverse();const b = num2.toString().split('').reverse();let carry = 0;const maxLength = Math.max(a.length, b.length);const result = [];for (let i = 0; i < maxLength; i++) {const digit1 = parseInt(a[i] || 0, 10);const digit2 = parseInt(b[i] || 0, 10);const sum = digit1 + digit2 + carry;result.push(sum % 10);carry = Math.floor(sum / 10);}if (carry > 0) result.push(carry);return result.reverse().join('');
}
特点:
• 支持任意长度整数相加。
• 时间复杂度 O(n),性能高效。
• 需手动处理进位与结果反转。
2. 使用 BigInt 类型
原理:ES6 引入的 BigInt
可表示任意精度整数,但仅支持整数运算。
代码示例:
const num1 = BigInt("9007199254740992");
const num2 = BigInt("1");
console.log(num1 + num2); // 输出: 9007199254740993n
特点:
• 无需手动处理进位,语法简洁。
• 无法直接与 Number
类型运算,需显式转换。
3. 第三方高精度库
推荐库:
• decimal.js:支持任意精度十进制运算,适合金融场景。
const Decimal = require('decimal.js');
const result = new Decimal('0.1').plus('0.2');
console.log(result.toString()); // 输出: 0.3
• bignumber.js:提供丰富的 API,支持科学计算。
const BigNumber = require('bignumber.js');
const num1 = new BigNumber('9999999999999999999999999999999999999999999999999999999999999');
console.log(num1.plus(1).toString()); // 输出: 10000000000000000000000000000000000000000000000000000000000000
优势:
• 内置四舍五入、指数运算等复杂功能。
• 避免手动实现进位逻辑的复杂性。
4. 转换为整数计算(固定小数位数)
适用场景:需精确控制小数位数(如货币计算)。
实现方法:
function addWithPrecision(num1, num2, precision = 2) {const factor = Math.pow(10, precision);return (Math.round(num1 * factor) + Math.round(num2 * factor)) / factor;
}
console.log(addWithPrecision(0.1, 0.2)); // 输出: 0.3
特点:
• 通过整数运算避免浮点数误差。
• 需提前确定精度,灵活性较低。
三、性能与场景选择
方案 | 适用场景 | 性能 | 代码复杂度 |
---|---|---|---|
字符串逐位相加 | 任意长度整数相加 | 中等 | 高 |
BigInt | 任意长度整数(仅整数运算) | 高 | 低 |
第三方库 | 复杂运算(金融、科学计算) | 中等 | 低 |
转换为整数 | 固定小数位数计算 | 高 | 低 |
推荐选择:
• 简单场景:字符串逐位相加。
• 金融/科学计算:使用 decimal.js
或 bignumber.js
。
• 大整数运算:直接使用 BigInt
。
四、扩展与注意事项
- 处理负数:需在逐位相加前统一符号,并单独处理负号。
- 结果格式化:使用
toFixed()
或库内置方法控制小数位数。 - 性能优化:对超长数字可分段并行计算(如 Web Worker)。
通过以上方案,可灵活应对 JavaScript 中的大数精度问题。如需完整代码示例或库的安装指南,可参考对应网页。
最长递增子序列(Vue3 Diff)
动态规划
以下是 JavaScript 实现最长递增子序列(LIS) 的详细解析,结合动态规划与优化算法,并标注来源:
一、问题描述
给定一个整数数组 nums
,找到其中最长严格递增子序列的长度。子序列无需连续,但必须保持元素顺序。例如:
• 输入 [10,9,2,5,3,7,101,18]
,输出 4
(子序列 [2,3,7,101]
)。
二、动态规划解法(O(n²))
核心思路
- 定义状态:
dp[i]
表示以nums[i]
结尾的最长递增子序列长度。 - 状态转移:遍历数组,若
nums[i] > nums[j]
(j < i
),则更新dp[i] = max(dp[i], dp[j] + 1)
。 - 结果:遍历
dp
数组,取最大值即为 LIS 长度。
代码实现
function lengthOfLIS(nums) {const n = nums.length;if (n === 0) return 0;const dp = new Array(n).fill(1); // 初始化为1,每个元素自身构成子序列let maxLen = 1;for (let i = 1; i < n; i++) {for (let j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLen = Math.max(maxLen, dp[i]);}return maxLen;
}
三、优化解法(O(nlogn))
核心思路
- 维护有序数组:
tails[i]
表示长度为i+1
的所有递增子序列的最小尾部元素。 - 二分查找:遍历数组,通过二分查找找到
tails
中第一个大于等于当前元素的位置,更新或插入元素。
代码实现
function lengthOfLIS(nums) {const tails = [];for (const num of nums) {const pos = binarySearch(tails, num);if (pos === tails.length) {tails.push(num);} else {tails[pos] = num;}}return tails.length;
}function binarySearch(arr, target) {let left = 0, right = arr.length;while (left < right) {const mid = Math.floor((left + right) / 2);if (arr[mid] < target) left = mid + 1;else right = mid;}return left;
}
四、性能对比
算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
---|---|---|---|
动态规划 | O(n²) | O(n) | 小规模数据(n ≤ 1000) |
优化算法(二分) | O(nlogn) | O(n) | 大规模数据(n ≥ 1000) |
五、扩展与注意事项
-
严格递增 vs 非严格递增
• 严格递增:nums[i] > nums[j]
(如示例1)。
• 非严格递增:nums[i] ≥ nums[j]
(需调整条件)。 -
返回子序列本身
• 动态规划可记录路径,但需额外空间。
• 优化算法需逆向重建路径。 -
边界条件处理
• 空数组返回0,单个元素返回1。
总结
• 简单场景:优先使用动态规划(代码简洁,易理解)。
• 高效场景:选择 O(nlogn) 优化算法(处理大规模数据)。
• 理解两种算法的原理差异,可应对不同性能需求。
高并发请求控制
高并发请求控制
大文件分片上传实现(断点续传)
核心流程(网页)
1.文件切片:将文件按固定大小(如5MB)分割
2. 哈希生成:使用SparkMD5等库生成文件唯一标识
3. 分片上传:并发控制上传切片(通常限制5个并发)
4. 断点续传:通过本地存储记录已上传切片
5.服务端合并:所有切片上传完成后触发合并请求
// 文件切片(网页5)
function sliceFile(file, chunkSize = 5 * 1024 * 1024) {const chunks = [];let start = 0;while (start < file.size) {chunks.push(file.slice(start, start + chunkSize));start += chunkSize;}return chunks;
}// 分片上传(网页6)
async function uploadChunks(fileHash, chunks) {const maxConcurrent = 5; // 最大并发数const uploaded = await checkUploadedChunks(fileHash);for (let i = 0; i < chunks.length; i += maxConcurrent) {await Promise.all(chunks.slice(i, i + maxConcurrent).map(async (chunk, index) => {if (!uploaded.includes(i + index)) {const formData = new FormData();formData.append('chunk', chunk);formData.append('hash', `${fileHash}-${i + index}`);await fetch('/upload', { method: 'POST', body: formData });}}));}await mergeChunks(fileHash, file.name);
}
以下是 JavaScript 实现大文件分片上传(断点续传) 的详细解析,结合核心原理与代码实现,并标注来源:
一、核心实现步骤
-
文件切片
将大文件分割成固定大小的块(如 5MB),使用File.slice()
方法实现。function createFileChunks(file, chunkSize = 5 * 1024 * 1024) {const chunks = [];let start = 0;while (start < file.size) {chunks.push(file.slice(start, start + chunkSize));start += chunkSize;}return chunks; }
-
生成文件唯一标识
通过文件名、大小和最后修改时间生成唯一标识(避免 MD5 计算耗时)。function calculateFileHash(file) {return `${file.name}-${file.size}-${file.lastModified}`; }
-
检查已上传切片
通过本地存储(localStorage
)或服务器查询已上传的切片索引,跳过已上传部分。const uploadedChunks = JSON.parse(localStorage.getItem(fileHash)) || [];
-
并发上传切片
使用Promise.all
并发上传未上传的切片,控制并发数(如 5 个)。const maxConcurrent = 5; const uploadQueue = chunks.filter((_, index) => !uploadedChunks.includes(index)).map((chunk, index) => uploadChunk(chunk, index)); await Promise.all(uploadQueue);
-
合并切片与清理进度
所有切片上传完成后,调用服务器合并接口,并清理本地进度记录。await fetch('/merge', {method: 'POST',body: JSON.stringify({ fileHash, filename: file.name }) }); localStorage.removeItem(fileHash);
二、关键技术点
-
文件哈希计算
使用spark-md5
库计算文件全量哈希,实现秒传功能。// 主线程 calculateHash(chunkList).then(hash => {if (serverFileExists(hash)) return; // 秒传 });
-
进度存储
通过localStorage
记录已上传切片索引,支持断点续传。uploadProgress.save(fileHash, uploadedChunks);
-
并发控制
通过队列机制限制同时上传的切片数量,避免浏览器崩溃。let activeUploads = 0; function processQueue() {if (activeUploads < maxConcurrent && uploadQueue.length > 0) {// 上传逻辑} }
-
错误处理与重试
捕获上传失败切片,支持自动重试或手动重传。try {await uploadChunk(chunk); } catch (error) {retryUpload(chunk); }
-
秒传功能
服务器端校验文件哈希,若存在则直接返回成功,避免重复上传。if (serverFileExists(fileHash)) {return { success: true, message: '秒传成功' }; }
三、完整代码示例
<input type="file" id="fileInput" />
<button id="uploadBtn">上传</button>
<progress id="progressBar" value="0" max="100"></progress><script>const fileInput = document.getElementById('fileInput');const progressBar = document.getElementById('progressBar');const axios = require('axios');document.getElementById('uploadBtn').onclick = async () => {const file = fileInput.files[0];const chunkSize = 10 * 1024 * 1024; // 10MBconst chunks = fileToChunks(file, chunkSize);const fileHash = calculateFileHash(file);// 检查已上传切片const uploadedChunks = JSON.parse(localStorage.getItem(fileHash)) || [];// 并发上传未上传切片const promises = chunks.map((chunk, index) => {if (uploadedChunks.includes(index)) return Promise.resolve();return uploadChunk(chunk, index, fileHash);});await Promise.all(promises);// 合并切片await axios.post('/merge', { fileHash, filename: file.name });localStorage.removeItem(fileHash);progressBar.value = 100;};function fileToChunks(file, size) {const chunks = [];for (let start = 0; start < file.size; start += size) {chunks.push(file.slice(start, start + size));}return chunks;}function calculateFileHash(file) {return `${file.name}-${file.size}-${file.lastModified}`;}async function uploadChunk(chunk, index, fileHash) {const formData = new FormData();formData.append('chunk', chunk);formData.append('index', index);formData.append('fileHash', fileHash);try {await axios.post('/upload', formData);localStorage.setItem(fileHash, JSON.stringify([...JSON.parse(localStorage.getItem(fileHash) || '[]'), index]));progressBar.max = chunks.length;progressBar.value++;} catch (error) {console.error(`Chunk ${index} 上传失败`);}}
</script>
四、注意事项
-
切片大小选择
建议 2-10MB,太小增加请求次数,太大增加重试成本。 -
服务器端配合
需提供以下接口:
•/upload
:上传单个切片
•/merge
:合并切片
•/check
:查询已上传切片 -
浏览器兼容性
File.slice()
在 IE10+ 支持,低版本需使用Blob.slice()
。 -
网络中断处理
可结合visibilitychange
事件暂停/恢复上传。
五、性能优化建议
方案 | 效果 | 实现复杂度 |
---|---|---|
分片大小动态调整 | 平衡上传速度与稳定性 | 中 |
上传进度可视化 | 提升用户体验 | 低 |
错误重试机制 | 减少因网络波动导致的失败 | 中 |
压缩切片数据 | 减少传输数据量 | 高 |
通过以上方案,可实现高效、可靠的大文件分片上传。实际开发中需结合具体业务场景选择优化策略,并确保前后端接口的兼容性。
Web Worker
以下是 JavaScript Web Worker 通信机制 的详细解析,结合主线程与 Worker 交互的核心原理与实现方法,并标注来源:
一、Web Worker 核心概念
Web Worker 是浏览器提供的多线程解决方案,允许在后台线程中执行 JavaScript 代码,避免阻塞主线程。其核心特点包括:
- 线程隔离:Worker 线程与主线程完全隔离,无法直接访问 DOM、
window
等全局对象。 - 消息传递:通过
postMessage
和onmessage
实现异步通信,数据通过结构化克隆算法传输。 - 类型分类:
• Dedicated Worker:仅服务于创建它的主线程。
• Shared Worker:跨页面共享,支持多标签页通信。
二、主线程与 Worker 交互流程
1. 创建 Worker 实例
主线程通过 new Worker(url)
创建 Worker,url
指向 Worker 脚本文件(需同源):
const worker = new Worker('worker.js'); //
2. 发送消息(postMessage)
主线程通过 postMessage
发送数据到 Worker,支持复杂数据类型(对象、数组等):
worker.postMessage({ type: 'calculate', data: [1,2,3] }); //
3. 接收消息(onmessage)
Worker 通过 self.onmessage
监听主线程消息,并通过 postMessage
返回结果:
// Worker 线程 (worker.js)
self.onmessage = (event) => {const result = event.data.data.reduce((sum, num) => sum + num, 0);self.postMessage(result); //
};
4. 终止 Worker
任务完成后,主线程调用 terminate()
释放资源:
worker.terminate(); //
三、通信机制关键点
1. 数据传输机制
• 结构化克隆算法:支持大多数数据类型(如对象、数组、Date),但无法处理函数、DOM 节点等。
• Transferable Objects:通过 transfer
参数直接转移数据所有权,避免复制开销(如 ArrayBuffer
):
// 主线程
const buffer = new ArrayBuffer(1024);
worker.postMessage(buffer, [buffer]); //
2. 消息传递特性
• 异步非阻塞:消息处理不会阻塞线程。
• 事件驱动:通过 onmessage
和 onerror
处理消息和异常。
3. 共享数据与跨域限制
• 数据隔离:Worker 与主线程无法共享内存,需通过消息传递交换数据。
• 同源策略:Worker 脚本需与主线程同源,跨域需通过 CORS 或代理。
四、高级应用场景
-
计算密集型任务:如大数据处理、图像加密(示例见网页):
// Worker 线程加密字符串 self.onmessage = (e) => {const encrypted = encrypt(e.data);self.postMessage(encrypted); };
-
跨页面通信:使用
SharedWorker
实现多标签页数据同步(网页):// 主线程 const sharedWorker = new SharedWorker('shared.js'); sharedWorker.port.onmessage = (e) => console.log(e.data);
-
性能优化:
• 合理控制 Worker 数量,避免资源浪费。
• 使用Transferable Objects
减少大数据传输开销。
五、注意事项
-
错误处理:通过
onerror
监听 Worker 异常:worker.onerror = (error) => console.error('Worker error:', error); //
-
调试技巧:
• 浏览器开发者工具的 Sources 面板查看 Worker 代码。
• 在 Worker 中使用console.log
输出调试信息。 -
适用性评估:
• 仅处理 CPU 密集型任务,避免因线程创建和通信开销影响简单任务。
总结
Web Worker 通过 消息传递机制 实现主线程与 Worker 的高效交互,适用于提升复杂计算的性能和页面响应性。实际开发中需结合任务类型选择 Worker 类型,并注意数据传输优化与错误处理。