JavaScript 数据结构与算法之美 - 栈内存与堆内存 、浅拷贝与深拷贝

前言想写好前端 先练好内功。

栈内存与堆内存 、浅拷贝与深拷贝 可以说是前端程序员的内功 要知其然 知其所以然。

笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript 旨在入门数据结构与算法和方便以后复习。

栈

定义

后进者先出 先进者后出 简称 后进先出 LIFO 这就是典型的栈结构。新添加的或待删除的元素都保存在栈的末尾 称作栈顶 另一端就叫栈底。在栈里 新元素都靠近栈顶 旧元素都接近栈底。从栈的操作特性来看 是一种 操作受限的线性表 只允许在一端插入和删除数据。不包含任何元素的栈称为空栈。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等 比如函数的调用栈。

堆

定义

堆数据结构是一种树状结构。

它的存取数据的方式 与书架与书非常相似。我们不关心书的放置顺序是怎样的 只需知道书的名字就可以取出我们想要的书了。

好比在 JSON 格式的数据中 我们存储的 key-value 是可以无序的 只要知道 key 就能取出这个 key 对应的 value。

堆与栈比较

堆是动态分配内存 内存大小不一 也不会自动释放。栈是自动分配相对固定大小的内存空间 并由系统自动释放。栈 线性结构 后进先出 便于管理。堆 一个混沌 杂乱无章 方便存储和开辟内存空间。

栈内存与堆内存

JavaScript 中的变量分为基本类型和引用类型。

基本类型是保存在栈内存中的简单数据段 它们的值都有固定的大小 保存在栈空间 通过按值访问 并由系统自动分配和自动释放。

这样带来的好处就是 内存可以及时得到回收 相对于堆来说 更加容易管理内存空间。

JavaScript 中的 Boolean、Null、Undefined、Number、String、Symbol 都是基本类型。

引用类型 如对象、数组、函数等 是保存在堆内存中的对象 值大小不固定 栈内存中存放的该对象的访问地址指向堆内存中的对象 JavaScript 不允许直接访问堆内存中的位置 因此操作对象时 实际操作对象的引用。

JavaScript 中的 Object、Array、Function、RegExp、Date 是引用类型。

结合实例说明

let a1 // 栈内存

let a2 this is string // 栈内存

let a3 null; // 栈内存

let b { x: 10 }; // 变量 b 存在于栈中 { x: 10 } 作为对象存在于堆中

let c [1, 2, 3]; // 变量 c 存在于栈中 [1, 2, 3] 作为对象存在于堆中

当我们要访问堆内存中的引用数据类型时

从栈中获取该对象的地址引用再从堆内存中取得我们需要的数据

基本类型发生复制

let a 20;

let b 

b 30;

console.log(a); // 20

在栈内存中的数据发生复制行为时 系统会自动为新的变量分配一个新值 最后这些变量都是 相互独立 互不影响的。

引用类型发生复制

let a { x: 10, y: 20 }

let b 

console.log(a.x); // 5

引用类型的复制 同样为新的变量 b 分配一个新的值 保存在栈内存中 不同的是 这个值仅仅是引用类型的一个地址指针。他们两个指向同一个值 也就是地址指针相同 在堆内存中访问到的具体对象实际上是同一个。因此改变 b.x 时 a.x 也发生了变化 这就是引用类型的特性。

结合下图理解

总结

| 栈内存 | 堆内存 |

| :------: | :------: |

| 存储基础数据类型 | 存储引用数据类型 |

| 按值访问 | 按引用访问 |

| 存储的值大小固定 | 存储的值大小不定 可动态调整 |

| 由系统自动分配内存空间 | 由代码进行指定分配 |

| 空间小 运行效率高 | 空间大 运行效率相对较低 |

| 先进后出 后进先出 | 无序存储 可根据引用直接获取 |

浅拷贝与深拷贝

上面讲的引用类型的复制就是浅拷贝 复制得到的访问地址都指向同一个内存空间。所以修改了其中一个的值 另外一个也跟着改变了。

深拷贝 复制得到的访问地址指向不同的内存空间 互不相干。所以修改其中一个值 另外一个不会改变。

平时使用数组复制时 我们大多数会使用 这只是浅拷贝 存在很多问题。比如

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

let arr2 arr;

console.log(arr) //[1, 2, 3, 4, 5]

console.log(arr2) //[1, 2, 3, 4, 5]

arr[0] 

console.log(arr) //[6, 2, 3, 4, 5]

console.log(arr2) //[6, 2, 3, 4, 5]

arr2[4] 

console.log(arr) //[6, 2, 3, 4, 7]

console.log(arr2) //[6, 2, 3, 4, 7]

很明显 浅拷贝下 拷贝和被拷贝的数组会相互受到影响。

所以 必须要有一种不受影响的方法 那就是深拷贝。

深拷贝的的复制过程

let a { x: 10, y: 20 }

let b JSON.parse(JSON.stringify(a));

console.log(a.x); // 10

console.log(b.x); // 5

数组

一、for 循环

//for 循环 copy

function copy(arr) {

 let cArr []

 for(let i i arr.length; i ){

 cArr.push(arr[i])

 return cArr;

let arr3 [1,2,3,4];

let arr4 copy(arr3) //[1,2,3,4]

console.log(arr4) //[1,2,3,4]

arr3[0] 

console.log(arr3) //[5,2,3,4]

console.log(arr4) //[1,2,3,4]

二、slice 方法

//slice实现深拷贝

let arr5 [1,2,3,4];

let arr6 arr5.slice(0);

arr5[0] 

console.log(arr5); //[5,2,3,4]

console.log(arr6); //[1,2,3,4]

三、concat 方法

//concat实现深拷贝

let arr7 [1,2,3,4];

let arr8 arr7.concat();

arr7[0] 

console.log(arr7); //[5,2,3,4]

console.log(arr8); //[1,2,3,4]

四、es6 扩展运算

//es6 扩展运算实现深拷贝

let arr9 [1,2,3,4];

let [...arr10] arr9;

arr9[0] 

console.log(arr9) //[5,2,3,4]

console.log(arr10) //[1,2,3,4]

五、JSON.parse 与 JSON.stringify

let arr9 [1,2,3,4];

let arr10 JSON.parse(JSON.stringify(arr9))

arr9[0] 

console.log(arr9) //[5,2,3,4]

console.log(arr10) //[1,2,3,4]

注意 该方法在数据量比较大时 会有性能问题。

对象

一、对象的循环

// 循环 copy 对象

let obj {

 id: 0 ,

 name: king ,

 sex: man 

let obj2 copy2(obj)

function copy2(obj) {

 let cObj {};

 for(var key in obj){

 cObj[key] obj[key]

 return cObj

obj2.name king2 

console.log(obj) // {id: 0 , name: king , sex: man }

console.log(obj2) // {id: 0 , name: king2 , sex: man }

二、JSON.parse 与 JSON.stringify

var obj1 {

 x: 1, 

 y: {

 m: 1

 a:undefined,

 b:function(a,b){

 return a b

 c:Symbol( foo )

var obj2 JSON.parse(JSON.stringify(obj1));

console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}

console.log(obj2) //{x: 1, y: {m: 1}}

obj2.y.m //修改obj2.y.m

console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}

console.log(obj2) //{x: 2, y: {m: 2}}

可实现多维对象的深拷贝。

注意 进行JSON.stringify() 序列化的过程中 undefined、任意的函数以及 symbol 值 在序列化过程中会被忽略 出现在非数组对象的属性值中时 或者被转换成 null 出现在数组中时 。

三、es6 扩展运算

let obj {

 id: 0 ,

 name: king ,

 sex: man 

let {...obj4} obj

obj4.name king4 

console.log(obj) //{id: 0 , name: king , sex: man }

console.log(obj4) //{id: 0 , name: king4 , sex: man }

四、Object.assign()

Object.assign() 只能实现一维对象的深拷贝。

var obj1 {x: 1, y: 2}, obj2 Object.assign({}, obj1);

console.log(obj1) // {x: 1, y: 2}

console.log(obj2) // {x: 1, y: 2}

obj2.x // 修改 obj2.x

console.log(obj1) // {x: 1, y: 2}

console.log(obj2) // {x: 2, y: 2}

var obj1 {

 x: 1, 

 y: {

 m: 1

var obj2 Object.assign({}, obj1);

console.log(obj1) // {x: 1, y: {m: 1}}

console.log(obj2) // {x: 1, y: {m: 1}}

obj2.y.m // 修改 obj2.y.m

console.log(obj1) // {x: 1, y: {m: 2}}

console.log(obj2) // {x: 1, y: {m: 2}}

通用深拷贝方法

简单版

let clone function (v) {

 let o v.constructor Array ? [] : {};

 for(var i in v){

 o[i] typeof v[i] object ? clone(v[i]) : v[i];

 return o;

// 测试

let obj {

 id: 0 ,

 name: king ,

 sex: man 

let obj2 clone(obj)

obj2.name king2 

console.log(obj) // {id: 0 , name: king , sex: man }

console.log(obj2) // {id: 0 , name: king2 , sex: man }

let arr3 [1,2,3,4];

let arr4 clone(arr3) // [1,2,3,4]

arr3[0] 

console.log(arr3) // [5,2,3,4]

console.log(arr4) // [1,2,3,4]

但上面的深拷贝方法遇到循环引用 会陷入一个循环的递归过程 从而导致爆栈 所以要避免。

let obj1 {

 x: 1, 

 y: 2

obj1.z obj1;

let obj2 clone(obj1);

console.log(obj2)

结果如下

总结 深刻理解 javascript 的深浅拷贝 可以灵活的运用数组与对象 并且可以避免很多 bug。