• home > webfront > ECMAS > emphasis >

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

    Author:[email protected] Date:

    在回顾java的数据结构后,再来看JavaScript的数据结构,觉得之前讲的还不是非常清楚,然后再看了些相关资料,再来谈下捋下js数据结构和实现原理,发现这个会越陷越深,只有

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

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

    • 7 种原始类型-基本数据类型(按值访问)

      • Null (js中的数据在底层是以二进制存储,如果前三位为0,那么就会判定为object,而null的所有都为0)

      • Undefined

      • 基本包装类型(自动创建的基本包装类型的对象—非Boolean,Number, String内置函数new出来的,对象只存代码的执行瞬间)

        • Number(基于 IEEE 754 标准的双精度 64 位二进制格式的值——数字、±Infinity、NaN)

        • String  

        • Boolean

      • Symbol (ECMAScript 6 新定义,实例是唯一且不可改变的)

      • bigInt(大整数:数字加n,如3n。目前处于第3阶段提案。BigInt 只有函数,没有构造器,没有BigInt实例)

    • 引用类型: 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堆栈示意图

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

    • 顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。

    • 链式存储结构:是把数据元素存放在内存中的任意存储单元里,也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的,也可以是不连续的。链表就是顺序存储结构的典型代表。

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

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

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

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

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

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

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

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

    • 堆是动态分配内存,内存大小不一,也不会自动释放

    • 栈是自动分配相对固定大小的内存空间,并由系统自动释放。栈先进后出(LIFO,last in first out),队列先进先出(FIFO,first in first out)。

    • 数组数据结构是由相同类型的元素(element)的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引(index)可以计算出该元素对应的存储地址。数组寻址容易,插入和删除困难的问题,而链表增删容易,查找困难。栈可以用数组或链表实现(c艹、java等基本功)。

    • 集合表示一组互不相同的元素(不重复的元素)。

    • 字典存储的是[键,值]对,其中键名是用来查询特定元素的。

    计算机数据结构图解


    20190509204136601106478.png

    经典的数据结构大概就那么几种,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结构以节省内存。

    • 可以使用键来推断它们在属性数组中的位置

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

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

    JS Object类图

    在创建一个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);
    }

    到这里,还是去看这边文章从Chrome源码看JS Object的实现

     

    // 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]                            |
    // +---------------+---------------------------------------------+


    参考文章:

    基本数据结构形象解释 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

    数据结构和算法 https://www.cnblogs.com/wsnb/p/5172431.html




    转载本站文章《再谈js对象数据结构底层实现原理-object array map set》,
    请注明出处:https://www.zhoulujun.cn/html/webfront/ECMAScript/js6/2016_0219_7607.html