JavaScript内置数据结构

JavaScript内置数据结构

• 前言：从算法题说起
• • 解法1：使用Array方法（时间复杂度O(n²)）
  • 解法2：使用Set（时间复杂度O(n)）
  • 解法3：使用Object（时间复杂度O(n)）
• Map vs Object：键值对的现代选择
• • Map
  • • Map的基本使用
    • Map的核心特性
    • • 1. 允许任意类型的键
      • 2. 顺序保持
      • 3. 可以直接获取大小
      • 4. 高效的查找和删除
      • 5. 允许批量清除等操作
  • Object
  • • Object的基本使用
    • • `new` 关键字和 `Object` 构造函数
      • 对象字面量表示法
    • Object的核心特性
    • • 1. 键只能是字符串或Symbol
      • 2. 顺序问题（ES6后字符串键按插入顺序，但仍有特殊情况）
      • 3. 大小需要手动计算
      • 4. 继承的属性和方法
  • 何时选择Map？何时选择Object？
  • • 场景1：键是动态的，且类型多样的：使用Map
    • 场景2：需要频繁增删键值对：使用Map
    • 场景3：JSON数据、配置对象、纯数据存储：使用Object
    • 场景4：需要原型继承、方法共享：使用Object
• Set vs Array：集合操作的艺术
• • Set
  • • Set的基本使用
    • Set的核心特性
    • • 1. 自动去重与大小计算
      • 2. 支持任意类型的值
      • 3. 高效的成员检查
      • 4. 集合运算：并集 & 交集 & 差集
      • 与Array互转
  • Array
  • • Array的基本使用
    • • `new` 关键字和 `Array` 构造函数
      • 数组字面量表示法
    • Array的核心特性
    • • 1. 允许重复和直接计算大小
      • 2. 丰富的数组方法 – 会改变原数组
      • • 填充fill()方法
        • 栈方法 push() 和 pop()
        • 队列方法 shift() 和 unshift()
        • 排序方法 sort() 和 reverse()
        • 强大的splice()
      • 3. 丰富的数组方法 – 不会改变原数组
      • • 数组连接方法concat()
        • 数组截取方法slice()
        • 严格相等查找indexOf()、lastIndexOf() 和 includes()
        • 断言查找find() 和 findIndex()
        • 迭代方法forEach()、map()、filter()、every()、some()
        • 归并方法reduce()
  • 何时选择Set？何时选择Array？
  • • 场景1：需要快速成员检查：使用Set
    • 场景2：需要去重：使用Set
    • 场景3：数学集合运算：使用Set
    • 场景4：有序数据、需要索引访问、丰富数组操作：使用Array
• WeakMap与WeakSet：弱引用的艺术
• • WeakMap：弱引用的键值对
  • • WeakMap的基本特性
    • • 1. 键必须是对象（不能是原始值）
      • 2. 不能计算大小
      • 3. 键是弱引用（不会阻止垃圾回收）
      • 4. 没有遍历方法（不能迭代）
  • WeakSet：弱引用的集合
  • • WeakSet的基本特性
    • • 1. 值必须是对象
      • 2. 弱引用特性（不会阻止垃圾回收）
      • 3. 没有遍历方法（不能迭代）
• 结语

前言：从算法题说起

找出下列数组中重复的元素（假设所有数字最多只出现2次）：

const arr = [1, 2, 3, 4, 5, 1, 2, 3];

解法1：使用Array方法（时间复杂度O(n²)）

function findDuplicatesWithArray(arr) {
return arr.filter((item, index) => arr.indexOf(item) !== index);
}

解法2：使用Set（时间复杂度O(n)）

function findDuplicatesWithSet(arr) {
const seen = new Set();
const duplicates = new Set();

for (const item of arr) {
if (seen.has(item)) {
duplicates.add(item);
} else {
seen.add(item);
}
}
return Array.from(duplicates);
}

解法3：使用Object（时间复杂度O(n)）

function findDuplicatesWithObject(arr) {
const seen = {};
const duplicates = [];

for (const item of arr) {
if (seen[item]) {
duplicates.push(item);
} else {
seen[item] = true;
}
}
return duplicates;
}

上述解法都能解决这一问题，但随着数据量增大，这些方案的性能差异会非常明显。要理解为什么，我们就需要深入了解每种数据结构的特点。

Map vs Object：键值对的现代选择

Map

Map的基本使用

使用 new 关键字和 Map 构造函数，可以创建一个空的 Map 映射：

const map = new Map();

当然，我们也可以在创建的时候，同时初始化实例，只需要给Map 构造函数传入一个可迭代的对象即可：

const map = new Map([{
a: 1
}]);

Map的核心特性

1. 允许任意类型的键

map.set('string', '字符串键');
map.set(123, '数字键');
map.set(true, '布尔键');
map.set({}, '对象键');
map.set([], '数组键');
map.set(() => {}, '函数键');
map.set(null, 'null键');
map.set(undefined, 'undefined键');

2. 顺序保持

map.set('first', 1);
map.set('second', 2);
map.set('third', 3);

for (const [key, value] of map) {
console.log(key, '-', value); // 保持插入顺序
}

3. 可以直接获取大小

console.log('Map大小:', map.size);

4. 高效的查找和删除

console.log('查找key为123:', map.has(123)); // true
console.log('获取key为123的值:', map.get(123)); // '数字键'

map.delete(123);
console.log('删除后查找key为123:', map.has(123)); // false

5. 允许批量清除等操作

map.clear();
console.log('清空后的大小:', map.size); // 0

Object

Object的基本使用

在 JavaScript 中，显式地创建 Object 的实例有两种方式：一种是使用 new 关键字和 Object 构造函数；另一种是使用对象字面量表示法。

new 关键字和 Object 构造函数

const obj = new Object();

对象字面量表示法

const obj = {};

Object的核心特性

1. 键只能是字符串或Symbol

obj.string = '字符串键'; // 键会被转换为字符串
obj[123] = '数字键'; // 数字键会被转换为字符串 '123'
obj[true] = '布尔键'; // 布尔键会被转换为字符串 'true'
obj[{}] = '对象键'; // 对象键会被转换为字符串 '[object Object]'
obj[[]] = '数组键'; // 数组键会被转换为字符串 ''
obj[null] = 'null键'; // null键会被转换为字符串 'null'
obj[undefined] = 'undefined键'; // undefined键会被转换为字符串 'undefined'

2. 顺序问题（ES6后字符串键按插入顺序，但仍有特殊情况）

const obj2 = {};
obj2['2'] = 'two';
obj2['1'] = 'one';
obj2['10'] = 'ten';

console.log('Object遍历顺序:');
for (const key in obj2) {
console.log(key, '-', obj2[key]); // 1 – one, 2 – two, 10 – ten
// 数字字符串键会被排序！
}

3. 大小需要手动计算

console.log('Object键的数量:', Object.keys(obj).length);

4. 继承的属性和方法

console.log('toString' in obj); // true（来自原型链）
console.log(obj.hasOwnProperty('toString')); // false

何时选择Map？何时选择Object？

场景1：键是动态的，且类型多样的：使用Map

class DynamicKeyRegistry {
constructor() {
this.registry = new Map();
}

set(key, value) {
this.registry.set(key, value);
return this;
}

get(key) {
return this.registry.get(key);
}

// 可以存储任何类型的键
registerComponent(component) {
this.registry.set(component, {
mounted: false,
instances: []
});
}
}

场景2：需要频繁增删键值对：使用Map

class Cache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // Map保持插入顺序
}

get(key) {
if (!this.cache.has(key)) return –1;
return this.cache.get(key);
}

set(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// 删除最旧的（Map第一个键）
const oldestKey = this.cache.keys().next().value;
this.cache.delete(oldestKey);
}
this.cache.set(key, value);
}
}

场景3：JSON数据、配置对象、纯数据存储：使用Object

const user = {
name: '张三',
age: 30,
email: 'zhangsan@example.com',
// 可以被JSON.stringify直接序列化
// 可以被解构赋值
// 语法更简洁
};

场景4：需要原型继承、方法共享：使用Object

class Animal {
constructor(name) {
this.name = name;
}

eat() {
console.log(`${this.name} is eating`);
}
}

// 继承和原型链是Object的强项
const dog = new Animal('Dog');
dog.eat();

Set vs Array：集合操作的艺术

Set

Set的基本使用

使用 new 关键字和 Set 构造函数，可以创建一个空的 Set 集合：

const set = new Set();

当然，我们也可以在创建的时候，同时初始化实例，只需要给 Set 构造函数传入一个可迭代的对象即可：

const set = new Set([1, 2, 3]);

Set的核心特性

1. 自动去重与大小计算

set.add(1);
set.add(2);
set.add(3);
set.add(1); // 重复，不会添加
set.add(2); // 重复，不会添加

console.log('Set内容:', set); // Set(3) {1, 2, 3}
console.log('Set大小:', set.size); // 3

2. 支持任意类型的值

set.add('string');
set.add({ name: 'obj' });
set.add([1, 2, 3]);
set.add(null);
set.add(undefined);
set.add(NaN);
set.add(NaN); // NaN在Set中也被视为相同值

3. 高效的成员检查

console.log('是否包含1:', set.has(1)); // true

4. 集合运算：并集 & 交集 & 差集

const setA = new Set([1, 2, 3, 4]);
const setB = new Set([3, 4, 5, 6]);

// 并集
const union = new Set([…setA, …setB]);
console.log('并集:', union); // Set(6) {1, 2, 3, 4, 5, 6}

// 交集
const intersection = new Set([…setA].filter(x => setB.has(x)));
console.log('交集:', intersection); // Set(2) {3, 4}

// 差集（A – B）
const difference = new Set([…setA].filter(x => !setB.has(x)));
console.log('差集(A-B):', difference); // Set(2) {1, 2}

与Array互转

const set = new Set([1, 2, 3, 4]);
const arrFromSet = Array.from(set);

const setFromArr = new Set([1, 2, 2, 3, 3, 4]);

Array

Array的基本使用

在 JavaScript 中，创建 Array 的实例有两种方式：一种是使用 new 关键字和 Array 构造函数；另一种是使用数组字面量表示法。

new 关键字和 Array 构造函数

使用 new 关键字和 Array 构造函数，可以创建一个空的 Array 数组：

const arr = new Array();

当然，我们也可以在创建的时候，同时初始化实例，只需要给 Set 构造函数传入一个可迭代的对象即可：

const arr = new Array(10 , 20, 30);

值得注意的是：当我们使用 new Array(10 , 20, 30); 这种方式创建数组时，数组值为 [10,20,30] ；但当参数只有一个时： new Array(10); 这时候会创建一个长度为10的数组。

数组字面量表示法

const arr = [1, 2, 3];

Array的核心特性

1. 允许重复和直接计算大小

arr.push(1);
arr.push(2);
arr.push(3);
arr.push(1); // 允许重复
arr.push(2); // 允许重复

console.log('Array内容:', arr); // [1, 2, 3, 1, 2]
console.log('Array长度:', arr.length); // 5

2. 丰富的数组方法 – 会改变原数组

填充fill()方法

const arr = new Array(5);
arr.fill(5); // [5, 5, 5, 5, 5]

栈方法 push() 和 pop()

• push() 方法用于数组模拟在栈顶的入栈操作，它接收任意数量的参数，并将它们添加到数组末尾。
• pop() 方法用于数组模拟在栈顶的出栈操作，它不接收任何参数，用于删除数组的最后一项。

const arr = [1, 2, 3, 4, 5];
arr.push(6, 7); // [1, 2, 3, 4, 5, 6, 7]
arr.pop(); // [1, 2, 3, 4, 5, 6]

队列方法 shift() 和 unshift()

• shift() 方法用于数组模式在队列头部出队操作，它不接收任何参数，用于删除数组的第一项。
• unshift() 方法用于数组模拟在队列头部的入队操作，它接收任意数量的参数，并将它们添加到数组头部。

const arr = [1, 2, 3, 4, 5];
arr.unshift()(6, 7); // [6, 7, 1, 2, 3, 4, 5]
arr.shift(); // [7, 1, 2, 3, 4, 5]

排序方法 sort() 和 reverse()

• sort() 方法用于对数组进行升序排序
• reverse() 方法用于对数组进行降序排序

强大的splice()

splice() 方法应该属于数组中最强大的方法了，可以接受 2 个及 2 个以上的参数，通常情况下，第 1 个参数表示要进行操作的开始位置，第 2 个参数表示要删除的元素数量，第 3 个及以后得所有参数，都表示为要新插入的元素。因此，该方法可以根据参数的不同，可以实现删除、插入、替换等操作：

const arr = [1, 2, 3, 4, 5];
arr.splice(1, 2); // 从索引1开始删除2个元素(2， 3)，结果为：[1, 4, 5]
arr.splice(2, 0, 'a', 'b'); // 从索引2开始插入'a'和'b'，结果为：[1, 4, 'a', 'b', 5]
arr.splice(1, 1, 'c'); // 从索引1开始删除2个元素(4, 'a')，再插入'c'，[1, 'c', 'b', 5]

注：以上所有方法均会改变原数组。

3. 丰富的数组方法 – 不会改变原数组

数组连接方法concat()

concat() 方法用于将两个或多个数组相连接，返回一个新的数组：

const arr1 = [1, 2, 3];
const arr2 = [4, 5];
const arr3 = arr1.concat(arr2); //[1, 2, 3, 4, 5]

数组截取方法slice()

slice() 方法可以接收1个或2个参数：当参数只有1个时，slice() 方法会返回从该索引到数组末尾的所有元素；当参数有2个时，slice() 方法会返回从开始索引（第1个参数）到结束索引（第2个参数）之间的所有元素（不包括结束索引的值）：

const arr = [1, 2, 3, 4, 5];
console.log(arr.slice(3)); // [4, 5]
console.log(arr.slice(0, 2)); // [0, 1]

严格相等查找indexOf()、lastIndexOf() 和 includes()

这三个方法都是用于在数组中查找元素的方法，它们都可以接收 1 个或 2 个参数：第 1 个参数表示要查找的元素；第 2 个参数可选，表示要从哪个位置开始找（不填默认从位置 0 ，即全数组查找）。

• indexOf() 和 includes() 都是从数组开头进行查找，而 lastIndexOf() 是从数组末尾开始查找。
• indexOf() 和 lastIndexOf() 会返回要查找的元素在数组中南的索引位置，不存在该元素则返回 -1 ；includes() 则是返回布尔值，表示是否找到匹配项。

const arr = [1, 2, 3, 4, 5, 1];
arr.indexOf(1); // 0
arr.lastIndexOf(1); // 5
arr.includes(1); // true

arr.indexOf(6); // -1
arr.lastIndexOf(6); // -1
arr.includes(6); // false

注：以上三个方法，在进行数组匹配查找时，会使用全等（===）进行比较，也就是两项必须严格相等，因此一般用于简单基本数据类型的数组查找；对象数组通过以上方法无法查找（因为它们在查找比对时，对比的是引用地址）。

断言查找find() 和 findIndex()

• find()：查找并返回数组中第一个满足条件的元素值，如果找不到则返回 undefined。
• findIndex()：查找并返回数组中第一个满足条件的元素值的索引地址，如果找不到则返回 -1 。

const arr = [
{
name: 'zhangsan',
age: 18
},
{
name: 'lisi',
age: 20
}
];

arr.find(item => item.age > 18); // { name: 'lisi', age: 20 }
arr.findIndex(item => item.age > 18); // 1

迭代方法forEach()、map()、filter()、every()、some()

JavaScript 中，为数组定义了 5 个迭代方法：

• forEach()：依次遍历数组中的每一个元素，没有返回值。
• map()：将数组的每个元素按照一定规则转换成新元素，返回一个新数组。
• filter()：按一定规则过滤数组中的所有元素，返回满足规则的元素。
• every()：对数组中的每一个元素都进行函数处理判断，如果数组中每一个元素的判断值都为 true，则这个方法的返回结果是 true；否则返回 false。
• some()：对数组中的每一个元素都进行函数处理判断，只要数组中有一个元素的判断值为 true，则这个方法的返回结果是 true；否则返回 false。

const arr = [1, 2, 3, 4, 5];

const mapRes = arr.map((num) => num * 2); // [2, 4, 6, 8, 10]
const filtered = arr.filter((num) => num % 2 === 0); // [2, 4]
const everyRes = arr.every((num) => num > 0); // true
const someRes = arr.some((num) => num > 4); // true

注：以上方法本质是不会更改原数组中，但如果在方法体内部对原数组进行了更改，也是会对原数组产生影响的，看下面一段代码示例：

const arr = [1, 2, 3, 4, 5];
array.forEach((item, index) => {
arr[index] = item + 1; // 开发中，要避免这种写法
});
console.log(arr); // [2, 3, 4, 5, 6]

归并方法reduce()

reduce() 方法会迭代数组的所有项，并在此基础上构建一个最终的返回值：

const arr = [1, 2, 3, 4, 5];
const sum = arr.reduce((acc, cur) => acc + cur, 0); // 15

何时选择Set？何时选择Array？

场景1：需要快速成员检查：使用Set

class PermissionSystem {
constructor() {
// 用户权限集合（快速查找）
this.userPermissions = new Set();
}

// 添加权限
grantPermission(permission) {
this.userPermissions.add(permission);
}

// 检查权限 – Set O(1) 时间复杂度
hasPermission(permission) {
return this.userPermissions.has(permission);
}

// 批量检查权限 – O(n) 时间复杂度
hasAllPermissions(requiredPermissions) {
return requiredPermissions.every(permission =>
this.userPermissions.has(permission)
);
}
}

场景2：需要去重：使用Set

const duplicateIds = [1, 2, 2, 3, 4, 4, 4, 5, 5, 5, 5];

// 使用 Set 去重（一行代码）
const uniqueIds = […new Set(duplicateIds)]; // [1, 2, 3, 4, 5]

场景3：数学集合运算：使用Set

class SocialNetwork {
constructor() {
this.users = new Map();
}

// 并集：共同好友 + 各自的好友
getUnionOfFriends(userId1, userId2) {
const friends1 = this.users.get(userId1) || new Set();
const friends2 = this.users.get(userId2) || new Set();

// 并集运算
const union = new Set([…friends1, …friends2]);
return […union];
}

// 交集：共同好友
getIntersectionOfFriends(userId1, userId2) {
const friends1 = this.users.get(userId1) || new Set();
const friends2 = this.users.get(userId2) || new Set();

// 交集运算
const intersection = new Set(
[…friends1].filter(friend => friends2.has(friend))
);
return […intersection];
}

// 差集：A有但B没有的好友
getDifferenceOfFriends(userId1, userId2) {
const friends1 = this.users.get(userId1) || new Set();
const friends2 = this.users.get(userId2) || new Set();

// 差集运算
const difference = new Set(
[…friends1].filter(friend => !friends2.has(friend))
);
return […difference];
}
}

场景4：有序数据、需要索引访问、丰富数组操作：使用Array

class ShoppingCart {
constructor() {
this.items = []; // 使用 Array：需要保持顺序、索引访问、各种数组方法
}

// 添加商品到购物车（保持添加顺序）
addItem(product, quantity = 1) {
const existingItemIndex = this.items.findIndex(
item => item.id === product.id
);

if (existingItemIndex !== –1) {
// 更新已有商品数量
this.items[existingItemIndex].quantity += quantity;
} else {
// 添加新商品
this.items.push({
…product,
quantity,
addedAt: new Date() // 记录添加时间
});
}
}

// 按索引移除商品
removeItem(index) {
if (index >= 0 && index < this.items.length) {
return this.items.splice(index, 1)[0];
}
return null;
}

// 按商品ID移除
removeItemById(productId) {
const index = this.items.findIndex(item => item.id === productId);
if (index !== –1) {
return this.removeItem(index);
}
return null;
}

// 筛选：按价格范围
filterByPriceRange(min, max) {
return this.items.filter(item =>
item.price >= min && item.price <= max
);
}

// 分页获取商品
getItemsPaginated(page = 1, pageSize = 5) {
const startIndex = (page – 1) * pageSize;
const endIndex = startIndex + pageSize;
return this.items.slice(startIndex, endIndex);
}
}

WeakMap与WeakSet：弱引用的艺术

WeakMap：弱引用的键值对

WeakMap 是 Map 的“兄弟”类型，其 API 也是 Map 的子集。 WeakMap 中的 “weak” 描述的是JavaScript 垃圾回收机制中对待“弱映射”中键的方式。

const weakMap = new WeakMap();

WeakMap的基本特性

1. 键必须是对象（不能是原始值）

const obj1 = { id: 1 };
const obj2 = { id: 2 };
const obj3 = { id: 3 };

weakMap.set(obj1, 'value1');
weakMap.set(obj2, 'value2');
weakMap.set(obj3, 'value3');

2. 不能计算大小

console.log('设置后weakMap:', weakMap); // <items unknown>
console.log(weakMap.size); // undefined 无法获取size

3. 键是弱引用（不会阻止垃圾回收）

{
let tempObj = { id: 'temp' };
weakMap.set(tempObj, 'temp value');
console.log('临时对象设置后:', weakMap.has(tempObj)); // true
}
// tempObj离开作用域，可以被垃圾回收
// weakMap中的对应条目会自动被移除

4. 没有遍历方法（不能迭代）

for (const [key, value] of weakMap) {} // TypeError
console.log(weakMap.keys()); // TypeError

WeakSet：弱引用的集合

WeakSet 是 Set 的“兄弟”类型，其 API 也是 Set 的子集。 WeakSet 中的 “weak” 描述的是JavaScript 垃圾回收机制中对待“弱集合”中键的方式。

const weakSet = new WeakSet();

WeakSet的基本特性

1. 值必须是对象

const objA = { name: 'A' };
const objB = { name: 'B' };
const objC = { name: 'C' };

weakSet.add(objA);
weakSet.add(objB);
weakSet.add(objC);

2. 弱引用特性（不会阻止垃圾回收）

{
let tempObj = { name: 'temp' };
weakSet.add(tempObj);
console.log('临时对象添加后:', weakSet.has(tempObj)); // true
}
// tempObj离开作用域，可以被垃圾回收

3. 没有遍历方法（不能迭代）

结语

没有"最好"的数据结构，只有"最适合"的数据结构。理解每种结构的特点和适用场景，根据具体需求做出明智选择！对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！