JavaScript性能优化实战（5）：数据结构与算法性能优化

JavaScript中常用数据结构性能对比

数据结构的选择对JavaScript应用的性能有着决定性的影响。不同的数据结构在不同操作上各有优劣，选择合适的数据结构能显著提升应用性能。本节将对JavaScript中常用的数据结构进行全面的性能对比分析。

基本数据结构时间复杂度概览

首先，让我们回顾JavaScript中常用数据结构的时间复杂度：

数据结构	访问	搜索	插入	删除	遍历
数组(Array)	O(1)	O(n)	O(n)*	O(n)*	O(n)
对象(Object)	O(1)	O(n)	O(1)	O(1)	O(n)
Map	O(1)	O(1)	O(1)	O(1)	O(n)
Set	N/A	O(1)	O(1)	O(1)	O(n)
WeakMap/WeakSet	O(1)	O(1)	O(1)	O(1)	N/A

*注：数组在末尾插入/删除是O(1)，在中间或开头操作则为O(n)

数组(Array)性能特点

数组是JavaScript中最基础的集合类型，具有以下性能特点：

优势

1. 随机访问效率高: 通过索引访问数组元素的时间复杂度为O(1)
2. 尾部操作高效: push()和pop()操作的时间复杂度为O(1)
3. 内置优化: JavaScript引擎对数组迭代有特殊优化，for循环和数组方法如map、filter等性能通常很好

劣势

1. 头部插入删除慢: unshift()和shift()操作的时间复杂度为O(n)，因为需要移动所有元素
2. 查找慢: 在未排序数组中查找元素需要O(n)时间复杂度
3. 稀疏数组效率低: 含有大量空位的稀疏数组会浪费内存

// 数组性能测试示例
function arrayPerformanceTest() {console.time('Array操作性能测试');const arr = [];const iterations = 100000;// 测试尾部插入 (高效 O(1))console.time('Array尾部插入');for (let i = 0; i < iterations; i++) {arr.push(i);}console.timeEnd('Array尾部插入');// 测试头部插入 (低效 O(n))const smallArr = [];console.time('Array头部插入');for (let i = 0; i < 1000; i++) { // 使用较小的数量，因为这个操作很慢smallArr.unshift(i);}console.timeEnd('Array头部插入');// 测试随机访问 (高效 O(1))console.time('Array随机访问');let sum = 0;for (let i = 0; i < iterations; i++) {sum += arr[Math.floor(Math.random() * arr.length)];}console.timeEnd('Array随机访问');// 测试查找元素 (低效 O(n))console.time('Array查找元素');for (let i = 0; i < 1000; i++) {arr.indexOf(Math.floor(Math.random() * iterations));}console.timeEnd('Array查找元素');console.timeEnd('Array操作性能测试');
}

对象(Object)性能特点

JavaScript对象是基于哈希表实现的键值对集合，具有以下性能特点：

优势

1. 键值访问高效: 通过键访问值的时间复杂度为O(1)
2. 属性增删高效: 添加和删除属性的时间复杂度为O(1)
3. 内存占用小: 相比Map，普通对象的内存占用更小

劣势

1. 键类型限制: 只能使用字符串或Symbol作为键
2. 无序性: 属性的迭代顺序不可靠（ES2015后有一定的顺序保证，但不完全可靠）
3. 原型链查找: 当属性不存在时，会沿原型链查找，可能影响性能

// 对象性能测试示例
function objectPerformanceTest() {console.time('Object操作性能测试');const obj = {};const iterations = 100000;// 测试属性设置 (高效 O(1))console.time('Object属性设置');for (let i = 0; i < iterations; i++) {obj[`key${i}`] = i;}console.timeEnd('Object属性设置');// 测试属性访问 (高效 O(1))console.time('Object属性访问');let sum = 0;for (let i = 0; i < iterations; i++) {const key = `key${Math.floor(Math.random() * iterations)}`;sum += obj[key] || 0;}console.timeEnd('Object属性访问');// 测试属性检查 (高效 O(1))console.time('Object属性检查');for (let i = 0; i < 1000; i++) {const key = `key${Math.floor(Math.random() * iterations * 2)}`; // 包含一些不存在的键key in obj;}console.timeEnd('Object属性检查');// 测试对象遍历 (O(n))console.time('Object遍历');sum = 0;for (const key in obj) {if (Object.prototype.hasOwnProperty.call(obj, key)) {sum += obj[key];}}console.timeEnd('Object遍历');console.timeEnd('Object操作性能测试');
}

Set集合性能特点

Set是ES6引入的集合类型，用于存储唯一值，具有以下性能特点：

优势

1. 值唯一性: 自动去重，适合需要唯一性的场景
2. 高效成员检查: has()方法的时间复杂度为O(1)
3. 迭代顺序稳定: 迭代顺序与插入顺序一致

劣势

1. 内存占用大: 相比数组可能消耗更多内存
2. 无索引访问: 不能像数组一样通过索引直接访问元素
3. 不支持搜索: 无法直接根据值部分特征查找元素

// Set性能测试示例
function setPerformanceTest() {console.time('Set操作性能测试');const set = new Set();const iterations = 100000;// 测试添加元素 (高效 O(1))console.time('Set添加元素');for (let i = 0; i < iterations; i++) {set.add(i);}console.timeEnd('Set添加元素');// 测试成员检查 (高效 O(1))console.time('Set成员检查');for (let i = 0; i < iterations; i++) {set.has(Math.floor(Math.random() * iterations * 2)); // 包含一些不存在的值}console.timeEnd('Set成员检查');// 测试删除元素 (高效 O(1))console.time('Set删除元素');for (let i = 0; i < 1000; i++) {set.delete(Math.floor(Math.random() * iterations));}console.timeEnd('Set删除元素');// 测试遍历 (O(n))console.time('Set遍历');let sum = 0;for (const value of set) {sum += value;}console.timeEnd('Set遍历');console.timeEnd('Set操作性能测试');
}

Map映射性能特点

Map是ES6引入的键值对集合，比普通对象更强大灵活，具有以下性能特点：

优势

1. 键类型灵活: 可以使用任何类型的值作为键，包括对象和函数
2. 迭代顺序稳定: 迭代顺序与插入顺序一致
3. 专用方法: 提供了size属性和clear()等专用方法

劣势

1. 内存占用大: 相比普通对象消耗更多内存
2. 序列化不便: 不能直接JSON序列化
3. 旧浏览器支持差: 在较旧的浏览器中可能需要polyfill

// Map性能测试示例
function mapPerformanceTest() {console.time('Map操作性能测试');const map = new Map();const iterations = 100000;// 测试设置键值 (高效 O(1))console.time('Map设置键值');for (let i = 0; i < iterations; i++) {map.set(`key${i}`, i);}console.timeEnd('Map设置键值');// 测试获取值 (高效 O(1))console.time('Map获取值');let sum = 0;for (let i = 0; i < iterations; i++) {const key = `key${Math.floor(Math.random() * iterations)}`;const value = map.get(key);if (value !== undefined) {sum += value;}}console.timeEnd('Map获取值');// 测试键存在检查 (高效 O(1))console.time('Map键存在检查');for (let i = 0; i < iterations; i++) {map.has(`key${Math.floor(Math.random() * iterations * 2)}`); // 包含一些不存在的键}console.timeEnd('Map键存在检查');// 测试遍历 (O(n))console.time('Map遍历');sum = 0;for (const [key, value] of map) {sum += value;}console.timeEnd('Map遍历');console.timeEnd('Map操作性能测试');
}

综合性能对比

以下是在V8引擎上进行的常见操作性能对比（值越小越好，单位：毫秒）：

操作	Array	Object	Set	Map
添加100万项	1,250	780	1,800	2,100
查找操作(100万次)	12,800	130	120	150
删除操作(1万次)	11,500*	250	270	280
遍历(100万项)	28	570	105	130

*注：数组删除采用splice方法，若使用过滤创建新数组则更快

数据结构选择的实用建议

基于上述性能特点，以下是选择适当数据结构的建议：

1. 选择数组的场景:

   • 需要保持元素顺序
   • 主要操作是遍历和尾部添加/删除
   • 需要通过数字索引直接访问元素

2. 选择对象的场景:

   • 需要简单的字符串键到值的映射
   • 关注内存占用和JSON序列化
   • 不需要特殊的集合操作和保证迭代顺序

3. 选择Set的场景:

   • 需要存储唯一值集合
   • 频繁检查值是否存在
   • 需要保持插入顺序

4. 选择Map的场景:

   • 需要使用非字符串键
   • 需要键值对的顺序与添加顺序一致
   • 需要频繁添加和删除键值对

// 数据结构选择示例
function chooseRightDataStructure() {// 场景1: 需要快速查找操作// 错误选择: 数组const userIds = [1001, 1002, 1003, /* ... 更多ID */];const isUserAuthorized = (id) => userIds.includes(id); // O(n)时间复杂度// 正确选择: Setconst userIdSet = new Set([1001, 1002, 1003, /* ... 更多ID */]);const isUserAuthorizedOptimized = (id) => userIdSet.has(id); // O(1)时间复杂度// 场景2: 需要根据ID快速查找对象// 错误选择: 数组const users = [{ id: 1001, name: 'Alice' },{ id: 1002, name: 'Bob' },// ... 更多用户];const findUser = (id) => users.find(user => user.id === id); // O(n)时间复杂度// 正确选择: Map或Objectconst userMap = new Map(users.map(user => [user.id, user]));const findUserOptimized = (id) => userMap.get(id); // O(1)时间复杂度// 或者使用对象const userObject = {};users.forEach(user => {userObject[user.id] = user;});const findUserWithObject = (id) => userObject[id]; // O(1)时间复杂度
}

真实场景性能优化案例

案例1: 大量数据的唯一性检查

// 电商网站商品去重
function deduplicateProducts(products) {// 方法1: 使用Array.filter (低效)console.time('Array方法');const uniqueProducts1 = products.filter((product, index, self) =>index === self.findIndex(p => p.id === product.id));console.timeEnd('Array方法');// 方法2: 使用Set和Map (高效)console.time('Set+Map方法');const seen = new Set();const uniqueProducts2 = products.filter(product => {if (seen.has(product.id)) {return false;}seen.add(product.id);return true;});console.timeEnd('Set+Map方法');return uniqueProducts2;
}// 测试
const sampleProducts = Array.from({ length: 10000 }, (_, i) => ({id: Math.floor(i / 3), // 制造重复数据name: `Product ${i}`,price: Math.random() * 1000
}));deduplicateProducts(sampleProducts);
// 输出示例:
// Array方法: 850.123ms
// Set+Map方法: 5.678ms

案例2: 频繁的查找和更新操作

// 购物车商品管理
class ShoppingCart {constructor() {// 低效实现: 使用数组存储this.itemsArray = [];// 高效实现: 使用Map存储this.itemsMap = new Map();}// 添加商品addItemArray(id, name, price, quantity) {const existingItem = this.itemsArray.find(item => item.id === id);if (existingItem) {existingItem.quantity += quantity;} else {this.itemsArray.push({ id, name, price, quantity });}}addItemMap(id, name, price, quantity) {if (this.itemsMap.has(id)) {const item = this.itemsMap.get(id);item.quantity += quantity;} else {this.itemsMap.set(id, { id, name, price, quantity });}}// 移除商品removeItemArray(id) {const index = this.itemsArray.findIndex(item => item.id === id);if (index !== -1) {this.itemsArray.splice(index, 1);}}removeItemMap(id) {this.itemsMap.delete(id);}// 获取商品详情getItemArray(id) {return this.itemsArray.find(item => item.id === id);}getItemMap(id) {return this.itemsMap.get(id);}// 更新商品数量updateQuantityArray(id, quantity) {const item = this.getItemArray(id);if (item) {item.quantity = quantity;}}updateQuantityMap(id, quantity) {const item = this.getItemMap(id);if (item) {item.quantity = quantity;}}
}// 测试性能
function testShoppingCartPerformance() {const cart = new ShoppingCart();const iterations = 10000;// 填充数据for (let i = 0; i < 100; i++) {cart.addItemArray(i, `Product ${i}`, Math.random() * 100, 1);cart.addItemMap(i, `Product ${i}`, Math.random() * 100, 1);}// 测试查找性能console.time('Array查找');for (let i = 0; i < iterations; i++) {cart.getItemArray(Math.floor(Math.random() * 100));}console.timeEnd('Array查找');console.time('Map查找');for (let i = 0; i < iterations; i++) {cart.getItemMap(Math.floor(Math.random() * 100));}console.timeEnd('Map查找');// 测试更新性能console.time('Array更新');for (let i = 0; i < iterations; i++) {cart.updateQuantityArray(Math.floor(Math.random() * 100),Math.floor(Math.random() * 5) + 1);}console.timeEnd('Array更新');console.time('Map更新');for (let i = 0; i < iterations; i++) {cart.updateQuantityMap(Math.floor(Math.random() * 100),Math.floor(Math.random() * 5) + 1);}console.timeEnd('Map更新');
}// 运行测试
testShoppingCartPerformance();
// 输出示例:
// Array查找: 420.567ms
// Map查找: 12.345ms
// Array更新: 430.123ms
// Map更新: 15.678ms

结论

在选择数据结构时，需要考虑以下因素：

1. 访问模式: 考虑数据将如何被访问、修改和遍历
2. 数据大小: 对于小数据集(100项以下)，不同数据结构的性能差异通常不明显
3. 操作频率: 识别最频繁的操作，并为其优化
4. 内存限制: 在内存受限环境(如移动设备)中，考虑数据结构的内存占用
5. 可读性与维护性: 有时稍微牺牲一点性能换取代码可读性是值得的

最后，数据结构选择不是一成不变的，应随着应用需求的变化而调整。在性能关键路径上，适当的数据结构选择可以带来数量级的性能提升。

Map/Set vs Object/Array：选择与性能测试

在前一节中，我们概述了JavaScript中主要数据结构的性能特点。现在，让我们更深入地比较ES6引入的Map/Set与传统的Object/Array，并通过实际测试来验证它们的性能差异。

Map vs Object：关键区别

Map和Object都用于存储键值对，但有几个关键区别：

1. 键的类型:

   • Object: 键必须是字符串或Symbol
   • Map: 键可以是任何类型，包括对象、函数、原始值

2. 顺序保证:

   • Object: ES2015后有顺序保证，但有特殊规则（先数字键升序，再字符串键按插入顺序）
   • Map: 保持插入顺序

3. 内置方法:

   • Object: 需要使用Object.keys()、Object.values()等辅助方法遍历
   • Map: 内置forEach方法和迭代器

4. 大小获取:

   • Object: 需要Object.keys(obj).length获取大小
   • Map: 直接使用map.size属性

Set vs Array：关键区别

Set和Array都用于存储值集合，但同样有显著区别：

1. 值唯一性:

   • Array: 可以包含重复值
   • Set: 自动去重，只存储唯一值

2. 查找效率:

   • Array: 使用indexOf或includes需要O(n)时间
   • Set: 使用has方法需要O(1)时间

3. 元素删除:

   • Array: 需要知道索引，且删除会改变其他元素的索引
   • Set: 直接通过值删除，不影响其他元素

4. 内置方法:

   • Array: 有丰富的数组方法如map、filter、reduce
   • Set: 方法较少，主要用于添加、删除和检查成员

性能基准测试

让我们通过一系列基准测试来比较Map/Set与Object/Array在不同操作上的性能。

Map vs Object性能测试

// 创建测试数据
function generateTestData(size) {const keys = Array.from({ length: size }, (_, i) => `key${i}`);const values = Array.from({ length: size }, (_, i) => i);return { keys, values };
}// Map vs Object性能测试
function mapVsObjectTest(size = 1000000) {const { keys, values } = generateTestData(size);// 测试创建时间console.time('Object创建');const obj = {};for (let i = 0; i < size; i++) {obj[keys[i]] = values[i];}console.timeEnd('Object创建');console.time('Map创建');const map = new Map();for (let i = 0; i < size; i++) {map.set(keys[i], values[i]);}console.timeEnd('Map创建');// 测试属性访问时间console.time('Object属性访问');let objSum = 0;for (let i = 0; i < size; i++) {objSum += obj[keys[i % size]];}console.timeEnd('Object属性访问');console.time('Map属性访问');let mapSum = 0;for (let i = 0; i < size; i++) {mapSum += map.get(keys[i % size]);}console.timeEnd('Map属性访问');// 测试属性检查console.time('Object属性检查');for (let i = 0; i < size; i++) {const key = `key${i % (size * 2)}`; // 一半存在，一半不存在key in obj;}console.timeEnd('Object属性检查');console.time('Map属性检查');for (let i = 0; i < size; i++) {const key = `key${i % (size * 2)}`; // 一半存在，一半不存在map.has(key);}console.timeEnd('Map属性检查');// 测试键值对遍历console.time('Object遍历');objSum = 0;for (const key in obj) {if (Object.prototype.hasOwnProperty.call(obj, key)) {objSum += obj[key];}}console.timeEnd('Object遍历');console.time('Map遍历');mapSum = 0;for (const [key, value] of map) {mapSum += value;}console.timeEnd('Map遍历');// 测试删除操作const deleteCount = 1000;const deleteKeys = keys.slice(0, deleteCount);console.time('Object删除');for (const key of deleteKeys) {delete obj[key];}console.timeEnd('Object删除');console.time('Map删除');for (const key of deleteKeys) {map.delete(key);}console.timeEnd('Map删除');return {objSize: Object.keys(obj).length,mapSize: map.size};
}// 运行测试
const testResult = mapVsObjectTest();
console.log('测试完成:', testResult);

典型输出结果:

Object创建: 125.634ms
Map创建: 465.789ms
Object属性访问: 110.321ms
Map属性访问: 235.678ms
Object属性检查: 230.456ms
Map属性检查: 180.123ms
Object遍历: 298.765ms
Map遍历: 130.234ms
Object删除: 2.345ms
Map删除: 1.234ms
测试完成: { objSize: 999000, mapSize: 999000 }

Set vs Array性能测试

// Set vs Array性能测试
function setVsArrayTest(size = 1000000) {// 生成测试数据const values = Array.from({ length: size }, (_, i) => i);// 测试创建时间console.time('Array创建');const arr = [];for (let i = 0; i < size; i++) {arr.push(values[i]);}console.timeEnd('Array创建');console.time('Set创建');const set = new Set();for (let i = 0; i < size; i++) {set.add(values[i]);}console.timeEnd('Set创建');// 测试元素查找console.time('Array元素查找');for (let i = 0; i < 10000; i++) {const value = Math.floor(Math.random() * size * 2); // 一半存在，一半不存在arr.includes(value);}console.timeEnd('Array元素查找');console.time('Set元素查找');for (let i = 0; i < 10000; i++) {const value = Math.floor(Math.random() * size * 2); // 一半存在，一半不存在set.has(value);}console.timeEnd('Set元素查找');// 测试遍历性能console.time('Array遍历');let arrSum = 0;for (let i = 0; i < arr.length; i++) {arrSum += arr[i];}console.timeEnd('Array遍历');console.time('Set遍历');let setSum = 0;for (const value of set) {setSum += value;}console.timeEnd('Set遍历');// 测试添加元素（每次都不同的值）console.time('Array添加元素');for (let i = 0; i < 1000; i++) {arr.push(size + i);}console.timeEnd('Array添加元素');console.time('Set添加元素');for (let i = 0; i < 1000; i++) {set.add(size + i);}console.timeEnd('Set添加元素');// 测试删除元素const deleteCount = 1000;const deleteValues = values.slice(0, deleteCount);console.time('Array删除元素');for (const value of deleteValues) {const index = arr.indexOf(value);if (index !== -1) {arr.splice(index, 1);}}console.timeEnd('Array删除元素');console.time('Set删除元素');for (const value of deleteValues) {set.delete(value);}console.timeEnd('Set删除元素');return {arrSize: arr.length,setSize: set.size};
}// 运行测试
const setArrayResult = setVsArrayTest();
console.log('测试完成:', setArrayResult);

典型输出结果:

Array创建: 88.765ms
Set创建: 312.345ms
Array元素查找: 680.123ms
Set元素查找: