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

JavaScript 数据结构与算法之美

前言

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

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

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

定义

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

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

定义

  • 堆数据结构是一种树状结构。
    它的存取数据的方式,与书架与书非常相似。我们不关心书的放置顺序是怎样的,只需知道书的名字就可以取出我们想要的书了。
    好比在 JSON 格式的数据中,我们存储的 key-value 是可以无序的,只要知道 key,就能取出这个 key 对应的 value。

堆与栈比较

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

栈内存与堆内存

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

  • 基本类型是保存在栈内存中的简单数据段,它们的值都有固定的大小,保存在栈空间,通过按值访问,并由系统自动分配和自动释放。
    这样带来的好处就是,内存可以及时得到回收,相对于堆来说,更加容易管理内存空间。
    JavaScript 中的 Boolean、Null、Undefined、Number、String、Symbol 都是基本类型。

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

结合实例说明

let a1 = 0; // 栈内存
let a2 = "this is string" // 栈内存
let a3 = null; // 栈内存
let b = { x: 10 }; // 变量 b 存在于栈中,{ x: 10 } 作为对象存在于堆中
let c = [1, 2, 3]; // 变量 c 存在于栈中,[1, 2, 3] 作为对象存在于堆中
栈/堆内存空间

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

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

基本类型发生复制

let a = 20;
let b = a;
b = 30;
console.log(a); // 20
基本类型发生复制过程

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

引用类型发生复制

let a = { x: 10, y: 20 }
let b = a;
b.x = 5;
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] = 6;
console.log(arr) //[6, 2, 3, 4, 5]
console.log(arr2) //[6, 2, 3, 4, 5]
arr2[4] = 7;
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));
b.x = 5;
console.log(a.x); // 10
console.log(b.x); // 5
复制前
复制后
b.x 修改为 5 后

数组

一、for 循环

//for 循环 copy
function copy(arr) {
    let cArr = []
    for(let i = 0; 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] = 5;
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] = 5;
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] = 5;
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] = 5;
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] = 5;
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 = 2; //修改obj2.y.m
console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}
console.log(obj2) //{x: 1, 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 = 2; // 修改 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 = 2; // 修改 obj2.y.m
console.log(obj1) // {x: 1, y: {m: 2}}
console.log(obj2) // {x: 2, 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] = 5;
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。

文章输出计划

JavaScript 数据结构与算法之美 的系列文章,坚持 3 - 7 天左右更新一篇,暂定计划如下表。

标题 链接
时间和空间复杂度 https://github.com/biaochenxuying/blog/issues/29
线性表(数组、链表、栈、队列) https://github.com/biaochenxuying/blog/issues/34
实现一个前端路由,如何实现浏览器的前进与后退 ? https://github.com/biaochenxuying/blog/issues/30
栈内存与堆内存 、浅拷贝与深拷贝 https://github.com/biaochenxuying/blog/issues/35
非线性表(树、堆) 精彩待续
递归 精彩待续
冒泡排序 精彩待续
插入排序 精彩待续
选择排序 精彩待续
归并排序 精彩待续
快速排序 精彩待续
计数排序 精彩待续
基数排序 精彩待续
桶排序 精彩待续
希尔排序 精彩待续
堆排序 精彩待续
十大经典排序汇总 精彩待续

如果有错误或者不严谨的地方,请务必给予指正,十分感谢。

7. 最后

关注我的公众号,第一时间接收最新的精彩博文。

文章可以转载,但须注明作者及出处,需要转载到公众号的,喊我加下白名单就行了。

参考文章:

JavaScript栈内存和堆内存
JavaScript实现浅拷贝与深拷贝的方法分析
浅拷贝与深拷贝(JavaScript)

笔芯
全栈修炼
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,271评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,275评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,151评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,550评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,553评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,559评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,924评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,580评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,826评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,578评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,661评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,363评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,940评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,926评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,156评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,872评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,391评论 2 342