首页 > webfront > ECMAS > js > > 正文

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

点击:

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

如果有java基础的同学,可以回顾下《再谈Java数据结构—分析底层实现与应用注意事项》:java把内存分两种:一种是栈内存,另一种是堆内存。基本类型(即byte,short,int,long,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堆栈示意图

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

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

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

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

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

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

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

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

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

什么是堆(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