JQiue's notes

数据结构

发布于 2020-11-12

JavaScript 提供了一些数据结构

字符串

使用双引号或单引号创建字符串字面量

const str = "Hello";

const str = 'Hello';

使用 new String() 构造函数创建 String 对象：

const str = new String("Hello");

模板字符串

模板字符串是一种增强的字符串写法，使用`来标记，用来解决字符串拼接麻烦的问题

let name = 'JQiue';
console.log(`I'm ${JQiue}`); // I'm JQiue

并且可以在模板字符串中嵌入表达式，使用${expression}

console.log(`${1 + 2}`); // 2

解决多行字符串的问题，新插入的行都会成为模板字符串的部分

console.log(`
Hello
I'm JQiue
`);

在一个函数后使用模板字符串，就能够用函数解析模板字符串，然后在函数中返回想要返回的东西，这是一个非常高级的功能

function tags(strings, name, age) {
  console.log(strings, name, age); // [ "I'm ", ',', ' this year' ] JQiue 22
}

tags `I'm ${'JQiue'},${22} this year`

字符串常用方法

查找：

  • str.indexOf(str, fromIndex)：返回指定值第一次出现的索引
  • str.lastIndexOf(str)：返回指定值最后一次出现的索引
  • str.chatAt(index)：返回在指定位置的字符
  • str.match(reg)：返回一个字符串匹配正则表达式的结果
  • str.search(reg)：执行正则表达式和 String 对象之间的一个搜索匹配
  • str.includes(str, fromIndex)：是否包含指定参数

截取：

  • str.slice(start, end)：提取某个字符串的一部分，并返回一个新的字符串，且不会改动原字符串
  • str.substring(start， end)：返回一个字符串在开始索引到结束索引之间的一个子集
  • str.trim()：删除字符串两端的空白

替换：

  • str.replace(reg|substr, newSubStr)：返回一个由替换值（replacement）替换部分或所有的模式（pattern）匹配项后的新字符串

转换：

  • str.toLowerCase()：转换为小写
  • str.toUpperCase()：转换为大写
  • str.split(reg|separator)：使用指定的分割符，将字符串分割成数组

其他：

  • str.toString()：返回指定对象的字符串形式
  • str.valueOf()：字符串对象转换为其对应的基本字符串
  • str.concat(str1, str2, ...)：连接字符串
  • str.repeat(conut)：返回一个新字符串，该字符串包含被连接在一起的指定数量的字符串的副本
  • str.toSource()：返回对象的源代码

数组

虽然对象允许储存数据，但对象中的属性是没有顺序的，有很多时候需要一个有序集合的结构，里面的元素是按照顺序排列的，数组（Array）就是这样的结构

创建数组有两种方式：

// 使用构造函数
let arr = new Array();
// 字面量
let arr = [];

通常使用字面量创建，可以在[]添加初始的元素，并通过下标访问对应的元素，从0开始

let names = ['zs', 'ls', 'ww'];

names[0]; // 'zs'
names[1]; // 'ww'

也可以通过下标替换元素

names[2] = 'zz'; // ['zs', 'ls', 'zz']

数组长度是可变的，所以可以新增一个元素

nams[3] = 'zq'; // ['zs', 'ls', 'zz', 'zq']

且可以存储任何类型的元素

let arr = [1, 'zs', {name: 'foo'}, true, [], function() {} ];

length

length不是数组的长度，而是最大索引值加1，会随着数组的修改而自动更新，准确来说它不是数组中元素的个数，比如一个数组的索引值很大，那么它的length也很大

let arr = [1, 2, 3];
arr[10] = 10;
console.log(arr.length); // 11

最妙的是，length还是可写的，如果减少了它，数组就会发生截断现象，且不可逆

let arr = [1, 2, 3, 4, 5];
console.log(arr[2]); // 3 
arr.length = 2;
console.log(arr); // [1, 2]
arr.length = 5;
console.log(arr[2]); // undefined

所以清空数组最好的方式就是arr.length = 0;

空位

允许数组的某个位置是空元素，即两个逗号之间没有任何值，如果对空位进行访问，将会得到undefined

[1, ,2]

空位不会影响length属性的计算，因为 JavaScript 认为该空位虽然没有值，但仍然是有效的

let arr = [1, ,2];
console.log(arr.length); //3

需要注意的是，最后一个元素后面有逗号时，并不能产生空位

let arr = [1, ,2,];
console.log(arr.length); //3

使用delete删除一个元素，也会形成空位

let arr = [1, 2, 3];
delete arr[1];
console.log(arr.length); //3

空位和undefined是不一样的，空位会被forEach方法，for...in、以及Object.keys方法跳过

数组是一种特殊的对象

使用方括号访问元素实际上是来自对象的语法，数组扩展了对象，提供了特殊的方法来处理有序的数据集合以及lenght属性，从本质上来讲，数组就是一个对象

数组真正特殊的就是内部实现，JavaScript 尝试将元素一个接一个的存储在连续的内存区域，还有一些其他的优化，使得数组运行的很快

一定要将数组当作“有序集合”来使用，而不是当作常规对象一样使用，否则针对数组的优化将不会存在

使用typeof []判断数组会返回一个object字符串，为了区分对象和数组应该使用Array.isArray()来进行判断

类似于数组一样的对象

如果一个对象的所有键都是正整数或0，且拥有length属性，那么这个对象就很像数组，在语法上被称为类数组

let obj = {
  0: 'a',
  1: 'b',
  2: 'c',
  length: 3
};

obj[0];  // a
obj[1];  // b
obj[2];  // c
obj.length;  3

obj.push('d'); // error，报错

但是，仅仅只是像而已，因为它并不会拥有数组特有的方法，同时类数组的length不会随着成员变化而变化

遍历

可以使用传统的for循环遍历数组：

let arr = [1, 2, 3];

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

JavaScript 也提供了另一种循环方式：for...of，尽管它和for...in有点像，但是它不能获取当前元素的索引，只是获取元素值

let arr = [1, 2, 3];

for (let item of arr) {
  console.log(item);
}

因为数组也是对象，使用for...in也是可以的，但通常不使用它来遍历数组，因为它会遍历所有的属性，不仅仅只有元素，比如“类数组”

let arr = [1, 2, 3];

for (let item in arr) {
  console.log(item);
}

原型上也提供了几个遍历方法：

  • arr.forEach(callback(item, index, array))：为每个元素运行一个函数
  • arr.map(callback(item, index, array))：将返回值得结果添加到新的数组，并将整个数组返回

从性能来讲，遍历效率最高的依次是：for > forEach > for...of > map > for...in

多维数组

数组中的元素当然也可以是数组，因此可以实现矩阵：

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

使用迭代器进行访问

ES6 为 Array 增加了一个“iterator”属性，通过Symbol.iterator访问，因此可以调用迭代器的方法来进行访问

let arr = [1, 2, 3, 4];

const iterator = arr[Symbol.iterator]();

console.log(iterator.next()); // { value: 1, done: false }
console.log(iterator.next()); // { value: 2, done: false }
console.log(iterator.next()); // { value: 3, done: false }
console.log(iterator.next()); // { value: 4, done: false }

类型数组

由于 JavaScript 数组不是强类型的，这导致它可以存储任意类型的元素，而类型数组则用于单一类型的数据，类型数组是一种新的补充，建立在 ArrayBuffer 的基础上，作用是分配一款连续的内存空间，语法是let arr = new TypeArray(length)，TypeArray可以替换下表中的之一

可用的类型数组数据类型
Int8Array8 位二进制补码整数
Uint8Array8 位无符号整数
Uint8ClampedArray8 位无符号整数
Int16Array16 位二进制补码整数
Uint16Array16 位无符号整数
Int32Array32 位二进制补码整数
Uint32Array32 位无符号整数
Float32Array32 位 IEEE 浮点数
Float64Array64 位 IEEE 浮点
let int16 = new Int16Array(5);
int16[0] = 1;
int16[1] = 2;
int16[2] = 3;
int16[3] = 4;
int16[4] = 5;
console.log(int16);

ArrayBuffer 是最原始的数据，所有对 ArrayBuffer 的操作都需要借助一个视图或者 DataView

常常用来处理一些二进制数据，使用起来和普通数组是一致的

方法

JavaScript 中的数组既可以是队列，也可以是栈

队列方法

  • arr.shift()：数组首端取出一个元素
  • arr.unshift(value)：数组首端添加一个元素，返回新的长度

栈方法

  • arr.pop()：数组末端删除一个元素
  • arr.push(value)：数组末端添加一个元素，返回新的长度

分割

  • arr.splice(start, num, element1, ...)：从 start 开始，删除 num 个元素，并用 element1 以及更多元素替换，返回由删除元素组成的数组，会改变原有数组
  • arr.slice(start, end)，返回从 start 开始到 end（不包含）索引之间的元素数组，不会更改，只是一种浅拷贝
  • str.split(delim)：通过delim分隔符将一个字符串分割成一个数组

::: tip splice 和 slice 还支持反向索引，从 -1 开始 :::

合并

  • arr.concat(arg1, ...)：用于合并来自其他数组和其他的值，并返回一个新的数组，只复制数组中的元素，如果看起来像数组则会被当作整体添加
  • arr.join(glue)：将数组通过glue连接成一个字符串，glue是可选的

转换

  • arr.keys()：返回一个由索引组成的可迭代对象
  • arr.values()：返回一个由元素组成的可迭代对象
  • Array.from(arrayLike)：从一个类数组或可迭代对象中创建一个新的浅拷贝数组

查找

  • arr.indexOf(item, from)：从 from 处从左向右搜索元素，找不到返回 -1
  • arr.lastIndexOf(item, from)：和上面一样，只不过是从右到左
  • arr.includes(item, from)：从 from 处开始搜索 item，找到就返回 true

排序

  • arr.sort(callback(a, b))：对数组进行原位排序，在默认情况下，是将每一个元素看作字符串排序的，如果要按照自己的规则排序，应该提供一个执行比较的排序函数，规则是 a 代表前一项元素，b 代表后一项元素，如果需要交换位置，则返回任意的正数，否则返回负数，比如arr.sort((a, b) => a - b)则是从小到大排序
  • arr.reverse()：反转数组元素的索引顺序，会改变原数组

::: tip sort 方法实现了通用的排序算法 :::

其他方法

  • arr.forEach(callback(item, index, array))：为每个元素运行一个函数
  • arr.map(callback(item, index, array))：将返回值得结果添加到新的数组，并将整个数组返回
  • arr.find(callback(item, index, array))：执行一个函数，如果该元素满足条件，则返回该元素，否则返回undefined
  • arr.findIndex(callback(value, index, array))：返回测试通过的第一个元素的索引，否则返回 -1
  • arr.filter(callback(item, index, array))：执行一个函数，如果返回 true，就将 item 添加到一个数组中并继续迭代，迭代完成后返回数组
  • arr.reduce(callback(previousValue, item, index, array), initial)：和forEach/map不同的是，函数会将返回的结果传给下一个函数的第一个参数 previousValue，如果传入了 initial，则 previousValue 的值会从 initial 开始，返回累计处理的结果
  • arr.some(callback(item, index, array))：当至少有一个元素通过了函数的测试就会返回 true
  • arr.every(callback(item, index, array))：当全部元素通过了函数的测试就会返回 true
  • arr.fill(value, start, end)：从 start 到 end 用重复的 value 填充
  • arr.flat(depath)：按照一个指定的深度递归遍历数组，并将所有的元素合并为一个新的数组
  • Array.isArray(arr)：检查 arr 是否为一个数组

会修改原数组的方法有：splice、sort、reverse、push、pop、shift、unshift

手写一个数组的深克隆拷贝算法

由于 JavaScript 数组的项可能是基本类型也可能是引用类型，所以要判断一下项的类型

function clone(array) {
  let result = [];
  for (let i = 0; i < array.length; i++) {
    // 如果数据项是数组，则递归
    if(Array.is(array[i])) {
      clone(array[i]);
    } else {
      // 数据项不是数组则拷贝
      resutl.push(array[i]);
    }
  }
  return result;
}

Map

map 是一个带键的数据集合，就像object一样，但是它们最大的区别就是，map 允许使用任何类型的键

let map = new Map();
map.set('1', 'str');
map.set(1, 'num');
map.set(true, 'bool');

let user = {}
map.set(user, 'object');

map.get('1'); // 'str'
map.get(1);  // 'num'
map.get(true); // 'bool'
map.get(user); // 'object'

这是 map 方法和属性：

  • new Map(iterable)
  • map.set(key, value)
  • map.get(key)
  • map.has(key)
  • map.delete(key)
  • map.clear()
  • map.keys()
  • map.values()
  • map.entries()
  • map.forEach(callback(value, key, map)))
  • map.size

另外，map.set()调用会返回 map 本身，因此可以链式调用：

map.set().set().set();

当创建一个 map 后，可以传入一个带有键值对的可迭代对象来初始化：

let map = new Map([
  ['1', 'str'],
  [1, 'num'],
  [true, 'bool'],
])

如果想从一个对象来创建 map，只需要通过Object.entries(obj)即可创建，因为该方法会将对象转换为符合 map 格式的键值对

另外，如果想将一个 map 转换为对象，也可以通过Object.fromEntries(map)来创建

Set

Set 是一个没有键的数据集合，它的值是唯一的，即使重复添加，这意味着可以快速的对一个数组去重

let set = new Set();

set.add('foo');
set.add('bar');
set.add('qux');

for (const i of set) {
  console.log(i);
}

它的属性和方法有：

  • new Set(iterable)
  • set.add(value)
  • set.delete(value)
  • set.has(value)
  • set.forEach(callback(value, value, set))
  • set.keys()
  • set.values()
  • set.clear()
  • set.size

forEach 的回调出现了相同的参数，这是为了和 map 兼容，虽然看来有点奇怪，这导致 map 中用于迭代的方法对 set 也有用

弱映射和弱集合

对象的引用被使用时会将其保留在内存中，除非引用指向null

let foo = {};

// 引用为 null 时，{} 会被回收
foo = null

通常，当对象、数组这类数据结构在内存中时，元素都是可以被访问的，如果一个对象被放到数组中，只要这个数组存在，对象就存在，即使没有其他的引用：

let foo = {};
// 数组保存了 foo 引用的对象，即使覆盖了引用，对象也不会被回收
let arr = [foo];
foo = null;

因此，如果将对象作为 map 的键，那么 map 存在，对象也就存在

WeakMap 和 map 的区别就是，必须以对象作为键：

let foo = {};
let weakMap = new weakMap();
weakMap.set(foo, '...');

// foo 引用的对象被回收了
foo = null;

和常规的 map，相比，如果一个对象只作为 WeakMap 的键而存在，那么它就会被回收

WeakMap 不支持迭代以及keys()，values()，entries()方法，因为它无法确定数据项是否存在，导致元素的数量是未知的，它只支持下面的方法：

  • get(key)
  • set(key, value)
  • delete(key)
  • has(key)

WeakMap 的主要应用场景是“额外数据的存储”和“数据的缓存”

WeakSet 的表现和 WeakMap 一致，只能添加对象进去，当失去了其他地方的引用时，元素就会被回收，也不可迭代

WeakMap 和 WeakSet 最明显的局限性就是不能迭代，并且无法获取所有当前内容。那样可能会造成不便，但是并不会阻止 WeakMap/WeakSet 完成其主要工作 — 成为在其它地方管理/存储“额外”的对象数据

总结

  • JavaScript 数组是可变长度的，并且能够存储不同类型的元素，数组的元素可以是数组
  • length是数组的一个属性，返回索引 + 1的数，会随着数组的变换而变化，并且是可写的，一旦写入小于当前length就会发生截断，并且不可逆
  • 数组允许空位存在，即在两个值之间可以有一个不存在的位置，没有任何东西，不会影响length计算，delete删除一个元素就会产生空位，空位会被各种遍历方法跳过
  • 类数组只是看起来像数组的对象，没有数组的方法
  • 最好不要使用for...in遍历数组，而是使用for...of，因为它能够区分数组和类数组
  • 数组可以被转换为一个迭代器对象进行遍历
  • Map 是一个带键的数据集合，允许使用任何类型的键
  • Set 是一个没有键的数据集合，它的值是唯一的，即使重复添加
  • Map 和 Set 都可以被迭代
  • WeakMap 和 map 的区别就是，必须以对象作为键，不支持迭代，一旦对象失去了引用就会被回收，WeakSet 也是如此