再谈js数据类型与对象数据结构底层实现原理-object array map set
Author：[email protected] Date：
如果有java基础的同学，可以回顾下《再谈Java数据结构—分析底层实现与应用注意事项》：java把内存分两种：一种是栈内存，另一种是堆内存。基本类型(即byte,short,int,long,float,double,boolean,char)在栈区分配空间，所有的对象都在堆(Heap)中分配空间。按照这思路来谈JavaScript。
JavaScript的数据类型
最新的 ECMAScript 标准定义了 8 种数据类型:
7 种原始类型-基本数据类型(按值访问)
Null ，null 值的意义存在于对象引用之中。null 值最初的含义为“没有引用任何对象”(js中的数据在底层是以二进制存储，如果前三位为0，那么就会判定为object，而null的所有都为0)。null 类型的值只有 null 一种情况，并且 null 属于字面量。Java 中也存在 null 这一字面量，但是没有 null 类型，null 只是一种可以被引用的值而已。
Undefined，指未定义的值的类型，null 是一种字面量而 undefined 是一个变量名。要使一个变量的值为 null，就必须将 null 以字面量的形式赋值给该变量。下面总结了会出现 undefined 值的情况：
未初始化的变量的值
不存在的属性的值
在没有传入实参而调用函数时，该函数内相应参数的值
没有 return 语句或是 return 语句中不含表达式的函数的返回值
对 void 运算符求值的结果（常常会通过使用 void 0 来获取一个 undefined 值）
基本包装类型(自动创建的基本包装类型的对象—Boolean,Number, String内置函数new出来的，对象只存代码的执行瞬间）
Number(基于 IEEE 754 标准的双精度 64 位二进制格式的值——数字、±Infinity、NaN），JavaScript 只有一种数值类的数据类型，其内部构造为 64 位的浮点小数，这相当于 Java 中的 double 类型
String ，JavaScript 的字符串型是基本数据类型，Java 中，字符串型和字面量以及运算符一样，属于被特别对待的 Object 类型。
Boolean
Symbol (ECMAScript 6 新定义，实例是唯一且不可改变的)
bigInt(大整数：数字加n，如3n。目前处于第3阶段提案。BigInt 只有函数，没有构造器，没有BigInt实例)
引用类型： Object(包括Object/Array/RegExp/Date/null)
更详细的介绍推荐阅读《细说 JavaScript 七种数据类型》、《JavaScript编程全解：第 3 章 JavaScript的数据类型 》
任何一个JavaScript的标识、常量、变量和参数都只是unfined, null, bool, number, string,symbol，object 和 function类型中的一种，也就typeof返回值表明的类型。
6种基本数据类型的实例被称为“值”，Object 类型的实例被称为“对象”，JavaScript 支持值与对象的隐式变换（ToPrimitive），所以有时可认为两者是完全相同的，而这会导致理解混乱。同时，JavaScript 的变量没有类型之分，所以值和对象之间的区别就变得更为模糊了。
在数据类型方面与 Java 作比较
JavaScript 和 Java 在数据类型方面的差异，不仅仅是两者所采用的术语不同。接下来，我们从两个不同角度来讨论这些差别：其一是从动态数据类型和静态数据类型的角度，其二是从基于类和基于原型的角度。
动态数据类型与静态数据类型
在 JavaScript 中，值和对象具有数据类型，而变量没有数据类型。事实上，JavaScript 中并不存在变量类型的概念。与之相反，在 Java 语言中变量有类型之分。Java 中的变量有其数据类型，它限制了可以对该变量赋值的值或对象引用的类型。因为 JavaScript 的变量不具有数据类型，所以可以对其赋任意类型的值，也可以使其引用任意类型的对象。
像 Java 这样，变量具有数据类型的语言，被称为静态数据类型语言；而像 JavaScript 这样，变量没有类型的语言，则被称为动态数据类型语言
同理，对于 Java 和 JavaScript 中函数的参数和返回值，也存在类似的差别。JavaScript 的函数参数及返回值是不具有数据类型的。也就是说，静态数据类型和动态数据类型之间的差异在函数的类型中也会有所体现
基于类与基于原型
对于 Java 来说，内建类型（int 或 double 之类）之外的都是用户自定义类型。用户自定义类型又可以分为类和接口两种类型。Java 的用户自定义类型的使用方法，从其名称中就可略知一二，即开发者需要书写该类型的定义语句来定义该类型。而对象则作为这些由用户定义的数据类型的实例（实体）存在。这就是 Java 的基本特性。这种编程风格被称为基于类的语言风格。
在 JavaScript 的语言规范中，不存在定义数据类型的语句。不需要使用特别的语句就能定义一个对象的属性或方法，而这样也就决定了该对象的类型。所谓类型也就是行为方式上的共性。由于每个对象都具有共同的行为方式，所以可以使用原型对象。这样的编程风格被称为基于原型的风格。
数据结构分析
从底层实现来看，JavaScript 的对象和 Java 的对象在基本原则上是相同的。两者都是内存中的实体，保持着某种状态，并且是用于编程操作的目标对象。但是，从高层概念来看的话，就会发现两者有着不小的差别。
Java 中的对象可以认为是类的一种实例化结果，而 JavaScript 中并没有类这样的语言构造。JavaScript 中的对象是一个名称与值配对的集合。这种名称与值的配对被称为属性。这样一来，JavaScript 对象可以定义为属性的集合。
表面上看，JavaScript 对象和 Java 的映射（java.util.Map）非常相似。实际上，JavaScript 对象可以用作管理键值对的关联数组 [ 又称映射（Map）或字典（Dictionary）]。JavaScript 对象还有着 Java 映射所没有的两个特点。
JavaScript 对象的属性值可以由函数指定。
JavaScript 具备一种称为原型链的构造。通过这一构造，JavaScript 对象实现了类似于类的继承的能力。
js基本类型数据都是直接按值存储在栈中的(Undefined、Null、不是new出来的布尔、数字和字符串)，每种类型的数据占用的内存空间的大小是确定的，并由系统自动分配和自动释放。这样带来的好处就是，内存可以及时得到回收，相对于堆来说 ，更加容易管理内存空间。java的基本数据类型共有8种，即int,short,long,byte,float,double,boolean,char(注意，并没有String的基本类型 )
js引用类型数据被存储于堆中 (如对象、数组、函数等，它们是通过拷贝和new出来的）。其实，说存储于堆中，也不太准确，因为，引用类型的数据的地址指针是存储于栈中的，当我们想要访问引用类型的值的时候，需要先从栈中获得对象的地址指针，然后，在通过地址指针找到堆中的所需要的数据。这个后讲，首先我们要搞清楚
数据在内存中的存储结构，也就是物理结构，分为两种：顺序存储结构和链式存储结构。
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。
链式存储结构：是把数据元素存放在内存中的任意存储单元里，也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的，也可以是不连续的。链表就是顺序存储结构的典型代表。
和顺序存储结构不同的是，链式存储结构的数据元素之间是通过指针来连接的，我们可以通使用指针来找到某个数据元素的位置，然后对这个数据元素进行一些操作。
数组和队列都可以实现栈和链表。
打个比方说一下顺序存储结构和链式存储结构的区别：
比如去银行取钱，顺序存储结构就相当于，所有的客户按照先来后到的顺序有序的的坐在大厅的椅子上（注意：是有顺序的坐着哦）。
而链式存储结构相当于，所有的客户只要一到银行，大堂经理就给他们每人一个号码，然后他们可以随便坐在哪个椅子上（随便坐，不需要按照什么顺序坐），只需要等待工作人员广播叫号即可。
而每个客户手里的号码就相当于指针，当前的指针指向下一个存储空间，这样，所有不连续的空间就可以被有顺序的按照线性连接在一起了。
什么是堆（heap）、栈（stack）
各种语言在处理堆栈的原理上都大同小异。
堆是动态分配内存，内存大小不一，也不会自动释放
栈是自动分配相对固定大小的内存空间，并由系统自动释放。栈先进后出(LIFO，last in first out），队列先进先出(FIFO，first in first out)。
数组数据结构是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。数组寻址容易，插入和删除困难的问题，而链表增删容易，查找困难。栈可以用数组或链表实现(c艹、java等基本功)。
集合表示一组互不相同的元素（不重复的元素）。
字典存储的是[键，值]对，其中键名是用来查询特定元素的。
经典的数据结构大概就那么几种，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的实现》
在创建一个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
延伸阅读：
- Javascript模块化编程
- Chrome开发工具Memory页面渲染内存占用分析
- js原型链之大话西游—简单粗暴地理解JavaScript原型链
- 从java发微javascript语法里的一些难点问题-js变量,栈区,作用域
- 图说js中的this——深入理解javascript中this指针
- 再谈javascriptjs原型与原型链及继承相关问题
- ECMAScript进化史(2):Web2.0时代的JavaScript1.5到ES5
- 深度克隆从C#/C/Java漫谈到JavaScript真复制
- 再唠叨JS模块化加载之CommonJS、AMD、CMD、ES6
- 从λ演算到函数式编程聊闭包(2)：彻底理解JavaScript闭包规则
- ECMAScript进化史(1):话说Web脚本语言王者JavaScript的加冕历史