1. 首页
  2. IT资讯

再谈js对象数据结构底层实现原理-object array map set

如果有java基础的同学,可以回顾下《再谈Java数据结构—分析底层实现与应用注意事项》:java把内存分两种:一种是栈内存,另一种是堆内存。基本类型(即int,short,long,byte,float,double,boolean,char)在栈区分配空间,所有的对象都在堆(Heap)中分配空间。按照这思路来谈下JavaScript。

最新的 ECMAScript 标准定义了 7 种数据类型:

  • 6 种原始类型-基本数据类型(按值访问)
    • Null (js中的数据在底层是以二进制存储,如果前三位为0,那么就会判定为object,而null的所有都为0)
    • Undefined
    • 基本包装类型(自动创建的基本包装类型的对象—非Boolean,Number, String内置函数new出来的,对象只存代码的执行瞬间)
      • Number(基于 IEEE 754 标准的双精度 64 位二进制格式的值——数字、±Infinity、NaN)
      • String
      • Boolean
    • Symbol (ECMAScript 6 新定义,实例是唯一且不可改变的)
  • 引用类型: Object(包括Object/Array/RegExp/Date/null)

任何一个JavaScript的标识、常量、变量和参数都只是unfined, null, bool, number, string,symbol,object 和 function类型中的一种,也就typeof返回值表明的类型。——推荐阅读《细说 JavaScript 七种数据类型》

js基本类型数据都是直接按值存储在栈中的(Undefined、Null、不是new出来的布尔、数字和字符串),每种类型的数据占用的内存空间的大小是确定的,并由系统自动分配和自动释放。这样带来的好处就是,内存可以及时得到回收,相对于堆来说 ,更加容易管理内存空间。java的基本数据类型共有8种,即int,short,long,byte,float,double,boolean,char(注意,并没有String的基本类型 )

js引用类型数据被存储于堆中 (如对象、数组、函数等,它们是通过拷贝和new出来的)。其实,说存储于堆中,也不太准确,因为,引用类型的数据的地址指针是存储于栈中的,当我们想要访问引用类型的值的时候,需要先从栈中获得对象的地址指针,然后,在通过地址指针找到堆中的所需要的数据。这个后讲,首先我们要搞清楚

再谈js对象数据结构底层实现原理-object array map set

数据在内存中的存储结构,也就是物理结构,分为两种:顺序存储结构和链式存储结构。

  • 顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。
  • 链式存储结构:是把数据元素存放在内存中的任意存储单元里,也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的,也可以是不连续的。链表就是顺序存储结构的典型代表。

和顺序存储结构不同的是,链式存储结构的数据元素之间是通过指针来连接的,我们可以通使用指针来找到某个数据元素的位置,然后对这个数据元素进行一些操作。

数组和队列都可以实现栈和链表。

打个比方说一下顺序存储结构和链式存储结构的区别:

比如去银行取钱,顺序存储结构就相当于,所有的客户按照先来后到的顺序有序的的坐在大厅的椅子上(注意:是有顺序的坐着哦)。

而链式存储结构相当于,所有的客户只要一到银行,大堂经理就给他们每人一个号码,然后他们可以随便坐在哪个椅子上(随便坐,不需要按照什么顺序坐),只需要等待工作人员广播叫号即可。

而每个客户手里的号码就相当于指针,当前的指针指向下一个存储空间,这样,所有不连续的空间就可以被有顺序的按照线性连接在一起了。

什么是堆(heap)、栈(stack)

各种语言在处理堆栈的原理上都大同小异。

  • 堆是动态分配内存,内存大小不一,也不会自动释放
  • 栈是自动分配相对固定大小的内存空间,并由系统自动释放。栈先进后出(LIFO,last in first out),队列后进先出(FIFO,first in first out)。
  • 数组数据结构是由相同类型的元素(element)的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引(index)可以计算出该元素对应的存储地址。数组寻址容易,插入和删除困难的问题,而链表增删容易,查找困难。栈可以用数组或链表实现(c艹、java等基本功)。
  • 集合表示一组互不相同的元素(不重复的元素)。
  • 字典存储的是[键,值]对,其中键名是用来查询特定元素的。

再谈js对象数据结构底层实现原理-object array map set

再谈js对象数据结构底层实现原理-object array map set

经典的数据结构大概就那么几种,list、stack、queue、linkedList、dictionary、hash、set、tree、graph……

JavaScript数据结构

es5自带的:array、object

es6自带的:set map、weakset weakmap (强引用、弱引用,Set 和 Map 数据结构,)

es未有的:dictionary list linkedlist doublelinkedlist quene hash stack

在JavaScript中不管多么复杂的数据和代码,都可以组织成object形式的对象

js里面的object类型在C/C++/Java等语言是没有这种数据类型(C是“万物之母”,C里面没有的),就得通过某种方式实现,究竟是如何实现其的?这个问题最先看了《从Chrome源码看JS Object的实现》,然后再回顾之前看的《JavaScript 对象属性底层原理》,在根据再谈系列一贯的文风总

对象大多数时候表现为Dictionary:如:{a:'foo',b:'bar'}

  • 存储结构可以是数组也可以是HashMap
  • 具有额外的辅助信息(存储在描述符数组中)——数组索引属性

数组索引属性(元素):

如:数组['foo','bar']有两个数组索引属性:0,值为'foo'; 1,值为'bar'。

  • 存储结构通常为简单的数组结构。但某些情况下也会切换到Hash结构以节省内存。
  • 可以使用键来推断它们在属性数组中的位置

数组索引属性命名属性存储在两个单独的数据结构中:

再谈js对象数据结构底层实现原理-object array map set

V8里面所有的数据类型的根父类都是Object,Object派生HeapObject,提供存储基本功能,往下的JSReceiver用于原型查找,再往下的JSObject就是JS里面的Object,Array/Function/Date等继承于JSObject。左边的FixedArray是实际存储数据的地方。推荐看原文《从Chrome源码看JS Object的实现》

再谈js对象数据结构底层实现原理-object array map set

在创建一个JSObject之前,会先把读到的Object的文本属性序列化成constant_properties,如下的data:

var data = {         name: "yin",         age: 18,         "-school-": "high school"     };

会被序列成:

../../v8/src/runtime/http://runtime-literals.cc 72 constant_properties: 0xdf9ed2aed19: [FixedArray] – length: 6 [0]: 0x1b5ec69833d1 [1]: 0xdf9ed2aec51 [2]: 0xdf9ed2aec71 [3]: 18 [4]: 0xdf9ed2aec91 [5]: 0xdf9ed2aecb1

它是一个FixedArray,FixedArray是V8实现的一个类似于数组的类,它表示一段连续的内存。

那么,这个连续内存,又如何还原成 JSON 结构对象呢?

FixedArray主要用于表示数据的存储位置,在它上面还有一个Map,这个Map用于表示数据的结构。这里的Map并不是哈希的意思,更接近于地图的意义,用来操作FixedArray表示的这段内存,并且可以通过index用descriptors迅速地取出key-value

for (int index = 0; index get(index + 0));   Handle value(constant_properties->get(index + 1));   Handle name = Handle::cast(key);   JSObject::SetOwnPropertyIgnoreAttributes(boilerplate, name, value, NONE); }

再谈js对象数据结构底层实现原理-object array map set

// Most object types in the V8 JavaScript are described in this file. // // Inheritance hierarchy: // - Object //   - Smi          (immediate small integer) //   - HeapObject   (superclass for everything allocated in the heap) //     - JSReceiver  (suitable for property access) //       - JSObject //         - JSArray //         - JSArrayBuffer //         - JSArrayBufferView //           - JSTypedArray //           - JSDataView //         - JSBoundFunction //         - JSCollection //           - JSSet //           - JSMap //         - JSStringIterator //         - JSSetIterator //         - JSMapIterator //         - JSWeakCollection //           - JSWeakMap //           - JSWeakSet //         - JSRegExp //         - JSFunction //         - JSGeneratorObject //         - JSGlobalObject //         - JSGlobalProxy //         - JSValue //           - JSDate //         - JSMessageObject //         - JSModuleNamespace //         - JSV8BreakIterator     // If V8_INTL_SUPPORT enabled. //         - JSCollator            // If V8_INTL_SUPPORT enabled. //         - JSDateTimeFormat      // If V8_INTL_SUPPORT enabled. //         - JSListFormat          // If V8_INTL_SUPPORT enabled. //         - JSLocale              // If V8_INTL_SUPPORT enabled. //         - JSNumberFormat        // If V8_INTL_SUPPORT enabled. //         - JSPluralRules         // If V8_INTL_SUPPORT enabled. //         - JSRelativeTimeFormat  // If V8_INTL_SUPPORT enabled. //         - JSSegmentIterator     // If V8_INTL_SUPPORT enabled. //         - JSSegmenter           // If V8_INTL_SUPPORT enabled. //         - WasmExceptionObject //         - WasmGlobalObject //         - WasmInstanceObject //         - WasmMemoryObject //         - WasmModuleObject //         - WasmTableObject //       - JSProxy //     - FixedArrayBase //       - ByteArray //       - BytecodeArray //       - FixedArray //         - FrameArray //         - HashTable //           - Dictionary //           - StringTable //           - StringSet //           - CompilationCacheTable //           - MapCache //         - OrderedHashTable //           - OrderedHashSet //           - OrderedHashMap //         - FeedbackMetadata //         - TemplateList //         - TransitionArray //         - ScopeInfo //         - ModuleInfo //         - ScriptContextTable //         - ClosureFeedbackCellArray //       - FixedDoubleArray //     - Name //       - String //         - SeqString //           - SeqOneByteString //           - SeqTwoByteString //         - SlicedString //         - ConsString //         - ThinString //         - ExternalString //           - ExternalOneByteString //           - ExternalTwoByteString //         - InternalizedString //           - SeqInternalizedString //             - SeqOneByteInternalizedString //             - SeqTwoByteInternalizedString //           - ConsInternalizedString //           - ExternalInternalizedString //             - ExternalOneByteInternalizedString //             - ExternalTwoByteInternalizedString //       - Symbol //     - Context //       - NativeContext //     - HeapNumber //     - BigInt //     - Cell //     - DescriptorArray //     - PropertyCell //     - PropertyArray //     - Code //     - AbstractCode, a wrapper around Code or BytecodeArray //     - Map //     - Oddball //     - Foreign //     - SmallOrderedHashTable //       - SmallOrderedHashMap //       - SmallOrderedHashSet //     - SharedFunctionInfo //     - Struct //       - AccessorInfo //       - AsmWasmData //       - PromiseReaction //       - PromiseCapability //       - AccessorPair //       - AccessCheckInfo //       - InterceptorInfo //       - CallHandlerInfo //       - EnumCache //       - TemplateInfo //         - FunctionTemplateInfo //         - ObjectTemplateInfo //       - Script //       - DebugInfo //       - BreakPoint //       - BreakPointInfo //       - StackFrameInfo //       - StackTraceFrame //       - SourcePositionTableWithFrameCache //       - CodeCache //       - PrototypeInfo //       - Microtask //         - CallbackTask //         - CallableTask //         - PromiseReactionJobTask //           - PromiseFulfillReactionJobTask //           - PromiseRejectReactionJobTask //         - PromiseResolveThenableJobTask //       - Module //       - ModuleInfoEntry //     - FeedbackCell //     - FeedbackVector //     - PreparseData //     - UncompiledData //       - UncompiledDataWithoutPreparseData //       - UncompiledDataWithPreparseData // // Formats of Object::ptr_: //  Smi:        [31 bit signed int] 0 //  HeapObject: [32 bit direct pointer] (4 byte aligned) | 01

每个 heap object 都有个 map 来记录相关信息。

// All heap objects have a Map that describes their structure. //  A Map contains information about: //  - Size information about the object //  - How to iterate over an object (for garbage collection) // // Map layout: // +---------------+---------------------------------------------+ // |   _ Type _    | _ Description _                             | // +---------------+---------------------------------------------+ // | TaggedPointer | map - Always a pointer to the MetaMap root  | // +---------------+---------------------------------------------+ // | Int           | The first int field                         | //  `---+----------+---------------------------------------------+ //      | Byte     | [instance_size]                             | //      +----------+---------------------------------------------+ //      | Byte     | If Map for a primitive type:                | //      |          |   native context index for constructor fn   | //      |          | If Map for an Object type:                  | //      |          |   inobject properties start offset in words | //      +----------+---------------------------------------------+ //      | Byte     | [used_or_unused_instance_size_in_words]     | //      |          | For JSObject in fast mode this byte encodes | //      |          | the size of the object that includes only   | //      |          | the used property fields or the slack size  | //      |          | in properties backing store.                | //      +----------+---------------------------------------------+ //      | Byte     | [visitor_id]                                | // +----+----------+---------------------------------------------+ // | Int           | The second int field                        | //  `---+----------+---------------------------------------------+ //      | Short    | [instance_type]                             | //      +----------+---------------------------------------------+ //      | Byte     | [bit_field]                                 | //      |          |   - has_non_instance_prototype (bit 0)      | //      |          |   - is_callable (bit 1)                     | //      |          |   - has_named_interceptor (bit 2)           | //      |          |   - has_indexed_interceptor (bit 3)         | //      |          |   - is_undetectable (bit 4)                 | //      |          |   - is_access_check_needed (bit 5)          | //      |          |   - is_constructor (bit 6)                  | //      |          |   - has_prototype_slot (bit 7)              | //      +----------+---------------------------------------------+ //      | Byte     | [bit_field2]                                | //      |          |   - is_extensible (bit 0)                   | //      |          |   - is_prototype_map (bit 1)                | //      |          |   - is_in_retained_map_list (bit 2)         | //      |          |   - elements_kind (bits 3..7)               | // +----+----------+---------------------------------------------+ // | Int           | [bit_field3]                                | // |               |   - enum_length (bit 0..9)                  | // |               |   - number_of_own_descriptors (bit 10..19)  | // |               |   - is_dictionary_map (bit 20)              | // |               |   - owns_descriptors (bit 21)               | // |               |   - has_hidden_prototype (bit 22)           | // |               |   - is_deprecated (bit 23)                  | // |               |   - is_unstable (bit 24)                    | // |               |   - is_migration_target (bit 25)            | // |               |   - is_immutable_proto (bit 26)             | // |               |   - new_target_is_base (bit 27)             | // |               |   - may_have_interesting_symbols (bit 28)   | // |               |   - construction_counter (bit 29..31)       | // |               |                                             | // +*************************************************************+ // | Int           | On systems with 64bit pointer types, there  | // |               | is an unused 32bits after bit_field3        | // +*************************************************************+ // | TaggedPointer | [prototype]                                 | // +---------------+---------------------------------------------+ // | TaggedPointer | [constructor_or_backpointer]                | // +---------------+---------------------------------------------+ // | TaggedPointer | If Map is a prototype map:                  | // |               |   [prototype_info]                          | // |               | Else:                                       | // |               |   [raw_transitions]                         | // +---------------+---------------------------------------------+ // | TaggedPointer | [instance_descriptors]                      | // +*************************************************************+ // ! TaggedPointer ! [layout_descriptors]                        ! // !               ! Field is only present if compile-time flag  ! // !               ! FLAG_unbox_double_fields is enabled         ! // !               ! (basically on 64 bit architectures)         ! // +*************************************************************+ // | TaggedPointer | [dependent_code]                            | // +---------------+---------------------------------------------+

原文链接:zhoulujun.cn/html/webfr

文有不妥之前,请源站留言告知,本人将及时修正,拜谢

参考文章:

基本数据结构形象解释 https://blog.csdn.net/qq_23864697/article/details/79727950

数据结构与算法 – 图的邻接表 (思想以及实现方式)www.cnblogs.com/cmusketeer/p/10331450.html

谁说前端就不需要学习数据结构了?来我们浅谈一下js的数据结构 https://www.jianshu.com/p/5e0e8d183102

JavaScript: new关键字创建对象底层原理 https://www.jianshu.com/p/265144a810b7

数据结构和算法 cnblogs.com/wsnb/p/5172

原文始发于:再谈js对象数据结构底层实现原理-object array map set

主题测试文章,只做测试使用。发布者:酒颂,转转请注明出处:http://www.cxybcw.com/24250.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code