René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"前端进阶算法2：从Chrome  V8源码看JavaScript数组（附赠腾讯面试题）","articleBody":"![](http://resource.muyiy.cn/image/20200401230346.jpg)\r\n\r\n### 简介\r\n\r\n数组、链表、栈、队列都是线性表，它表示的结构都是一段线性的结构，与之对应的就是非线性表，例如树、图、堆等，它表示的结构都非线性。\r\n\r\n本节主要介绍 JavaScript 数组，在开始本章节前，思考一个问题：\r\n\r\n我们知道在 JavaScript 中，可以在数组中保存不同类型值，并且数组可以动态增长，不像其它语言，例如 C，创建的时候要决定数组的大小，如果数组满了，就要重新申请内存空间。这是为什么喃？\r\n\r\n本节从 Chrome v8 源码角度回答这个问题，分为四个方面：\r\n\r\n- 数组基础入门\r\n- JavaScript 中，数组为什么可以保存不同类型？\r\n- JavaScript 中，数组是如何存储的喃？\r\n- JavaScript 中，数组的动态扩容与减容（ `FastElements` ）\r\n\r\n下面进入正题吧！（文末有惊喜）😊\r\n\r\n想要更多更快的学习本系列，可以关注公众号「前端瓶子君」和我的「[Github（点击查看）](https://github.com/sisterAn/JavaScript-Algorithms)」\r\n\r\n### 一、数组（基础）\r\n\r\n一种最基础的数据结构，每种编程语言都有，它编号从 0 开始，代表一组连续的储存结构，用来储存同一种类型的数据。\r\n\r\n```js\r\nlet arr = [1, 2, 3]\r\n```\r\n\r\n它的这种特定的存储结构（连续存储空间存储同一类型数据）决定了：\r\n\r\n**优点**\r\n\r\n- 随机访问：可以通过下标随机访问数组中的任意位置上的数据\r\n\r\n**缺点**\r\n\r\n- 对数据的删除和插入不是很友好\r\n\r\n**查找：** 根据下标随机访问的时间复杂度为 O(1)；\r\n\r\n**插入或删除：** 时间复杂度为 O(n)；\r\n\r\n在 JavaScript 中的数组几乎是万能的，它不光可以作为一个普通的数组使用，可以作为栈或队列使用。\r\n\r\n数组：\r\n\r\n```js\r\nlet array = [1, 2, 3]\r\n```\r\n\r\n栈：\r\n\r\n```js\r\nlet stack = [1, 2, 3]\r\n// 进栈\r\nstack.push(4)\r\n// 出栈\r\nstcak.pop()\r\n```\r\n\r\n队列：\r\n\r\n```js\r\nlet queue = [1, 2, 3]\r\n// 进队\r\nqueue.push(4)\r\n// 出队\r\nqueue.shift()\r\n```\r\n\r\n\r\n\r\n### 二、JavaScript 中，数组可以保存不同类型值\r\n\r\n看一下 Chrome v8 源码：\r\n\r\n```js\r\n// The JSArray describes JavaScript Arrays\r\n//  Such an array can be in one of two modes:\r\n//    - fast, backing storage is a FixedArray and length \u003c= elements.length();\r\n//       Please note: push and pop can be used to grow and shrink the array.\r\n//    - slow, backing storage is a HashTable with numbers as keys.\r\nclass JSArray: public JSObject {\r\n public:\r\n  // [length]: The length property.\r\n  DECL_ACCESSORS(length, Object)\r\n    \r\n  // ...\r\n   \r\n  // Number of element slots to pre-allocate for an empty array.\r\n  static const int kPreallocatedArrayElements = 4;\r\n};\r\n```\r\n\r\n我们可以看到 `JSArray` 是继承自 `JSObject` 的，所以在 JavaScript 中，数组可以是一个特殊的对象，内部也是以 key-value 形式存储数据，所以 JavaScript 中的数组可以存放不同类型的值。\r\n\r\n\r\n\r\n### 三、JavaScript 中，数组的存储\r\n\r\n```js\r\n// The JSArray describes JavaScript Arrays\r\n//  Such an array can be in one of two modes:\r\n//    - fast, backing storage is a FixedArray and length \u003c= elements.length();\r\n//       Please note: push and pop can be used to grow and shrink the array.\r\n//    - slow, backing storage is a HashTable with numbers as keys.\r\nclass JSArray: public JSObject {\r\n public:\r\n  // [length]: The length property.\r\n  DECL_ACCESSORS(length, Object)\r\n    \r\n  // ...\r\n   \r\n  // Number of element slots to pre-allocate for an empty array.\r\n  static const int kPreallocatedArrayElements = 4;\r\n};\r\n```\r\n `JSArray` 继承于 `JSObject` ，从注释上看，它有两种存储方式：\r\n\r\n- fast：存储结构是 `FixedArray` ，并且数组长度 `\u003c= elements.length()` ，`push` 或 `pop` 时可能会伴随着动态扩容或减容\r\n- slow：存储结构是 `HashTable`（哈希表），并且数组下标作为 `key` \r\n\r\n`fast` 模式下数组在源码里面叫 `FastElements` ，而 `slow` 模式下的叫做 `SlowElements` 。\r\n\r\n#### 1. 快数组（FastElements）\r\n\r\n`FixedArray` 是 V8 实现的一个类似于数组的类，它表示一段连续的内存，可以使用索引直接定位。新创建的空数组默认就是快数组。当数组满（数组的长度达到数组在内存中申请的内存容量最大值）的时候，继续 `push` 时， `JSArray` 会进行动态的扩容，以存储更多的元素。\r\n\r\n#### 2. 慢数组（SlowElements）\r\n\r\n慢数组以哈希表的形式存储在内存空间里，它不需要开辟连续的存储空间，但需要额外维护一个哈希表，与快数组相比，性能相对较差。\r\n\r\n```js\r\n// src/objects/dictionary.h\r\nclass EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Dictionary\r\n    : public HashTable\u003cDerived, Shape\u003e {\r\n  using DerivedHashTable = HashTable\u003cDerived, Shape\u003e;\r\n\r\n public:\r\n  using Key = typename Shape::Key;\r\n  // Returns the value at entry.\r\n  inline Object ValueAt(InternalIndex entry);\r\n  inline Object ValueAt(const Isolate* isolate, InternalIndex entry);\r\n  \r\n  // ...\r\n};\r\n```\r\n\r\n从源码中可以看出，它的内部就是一个 HashTable。\r\n\r\n#### 3. 什么时候会从 fast 转变为 slow 喃？\r\n\r\n从 Chrome V8 源码上看，\r\n\r\n```js\r\n// src/objects/js-objects.h\r\nstatic const uint32_t kMaxGap = 1024;\r\n\r\n// src/objects/dictionary.h\r\n// JSObjects prefer dictionary elements if the dictionary saves this much\r\n// memory compared to a fast elements backing store.\r\nstatic const uint32_t kPreferFastElementsSizeFactor = 3;\r\n\r\n// src/objects/js-objects-inl.h\r\n// If the fast-case backing storage takes up much more memory than a dictionary\r\n// backing storage would, the object should have slow elements.\r\n// static\r\nstatic inline bool ShouldConvertToSlowElements(uint32_t used_elements,\r\n                                               uint32_t new_capacity) {\r\n  uint32_t size_threshold = NumberDictionary::kPreferFastElementsSizeFactor *\r\n                            NumberDictionary::ComputeCapacity(used_elements) *\r\n                            NumberDictionary::kEntrySize;\r\n  // 快数组新容量是扩容后的容量3倍之多时，也会被转成慢数组\r\n  return size_threshold \u003c= new_capacity;\r\n}\r\n\r\nstatic inline bool ShouldConvertToSlowElements(JSObject object,\r\n                                               uint32_t capacity,\r\n                                               uint32_t index,\r\n                                               uint32_t* new_capacity) {\r\n  STATIC_ASSERT(JSObject::kMaxUncheckedOldFastElementsLength \u003c=\r\n                JSObject::kMaxUncheckedFastElementsLength);\r\n  if (index \u003c capacity) {\r\n    *new_capacity = capacity;\r\n    return false;\r\n  }\r\n  // 当加入的索引值（例如例3中的2000）比当前容量capacity 大于等于 1024时，\r\n  // 返回true，转为慢数组\r\n  if (index - capacity \u003e= JSObject::kMaxGap) return true;\r\n  *new_capacity = JSObject::NewElementsCapacity(index + 1);\r\n  DCHECK_LT(index, *new_capacity);\r\n  // TODO(ulan): Check if it works with young large objects.\r\n  if (*new_capacity \u003c= JSObject::kMaxUncheckedOldFastElementsLength ||\r\n      (*new_capacity \u003c= JSObject::kMaxUncheckedFastElementsLength \u0026\u0026\r\n       ObjectInYoungGeneration(object))) {\r\n    return false;\r\n  }\r\n  return ShouldConvertToSlowElements(object.GetFastElementsUsage(),\r\n                                     *new_capacity);\r\n}\r\n```\r\n\r\n所以，当处于以下情况时，快数组会被转变为慢数组：\r\n\r\n- 当加入的索引值 index 比当前容量 capacity 差值大于等于 1024 时（index - capacity \u003e= 1024）\r\n- 快数组新容量是扩容后的容量 3 倍之多时\r\n\r\n例如：向快数组里增加一个大索引同类型值\r\n\r\n```js\r\nvar arr = [1, 2, 3]\r\narr[2000] = 10;\r\n```\r\n\r\n当往 `arr` 增加一个 `2000` 的索引时，`arr` 被转成慢数组。节省了大量的内存空间（从索引为 2 到索引为 2000）。\r\n\r\n#### 4. 什么时候会从 slow 转变为 fast 喃？\r\n\r\n我们已经知道在什么时候会出现由快变慢，那由慢变快就很简单了\r\n\r\n```js\r\nstatic bool ShouldConvertToFastElements(JSObject object,\r\n                                        NumberDictionary dictionary,\r\n                                        uint32_t index,\r\n                                        uint32_t* new_capacity) {\r\n  // If properties with non-standard attributes or accessors were added, we\r\n  // cannot go back to fast elements.\r\n  if (dictionary.requires_slow_elements()) return false;\r\n  // Adding a property with this index will require slow elements.\r\n  if (index \u003e= static_cast\u003cuint32_t\u003e(Smi::kMaxValue)) return false;\r\n  if (object.IsJSArray()) {\r\n    Object length = JSArray::cast(object).length();\r\n    if (!length.IsSmi()) return false;\r\n    *new_capacity = static_cast\u003cuint32_t\u003e(Smi::ToInt(length));\r\n  } else if (object.IsJSArgumentsObject()) {\r\n    return false;\r\n  } else {\r\n    *new_capacity = dictionary.max_number_key() + 1;\r\n  }\r\n  *new_capacity = Max(index + 1, *new_capacity);\r\n  uint32_t dictionary_size = static_cast\u003cuint32_t\u003e(dictionary.Capacity()) *\r\n                             NumberDictionary::kEntrySize;\r\n  // Turn fast if the dictionary only saves 50% space.\r\n  return 2 * dictionary_size \u003e= *new_capacity;\r\n}\r\n```\r\n\r\n当慢数组的元素可存放在快数组中且长度在 smi 之间且仅节省了50%的空间，则会转变为快数组\r\n\r\n### 四、JavaScript 中，数组的动态扩容与减容（FastElements）\r\n\r\n默认空数组初始化大小为 `4` :\r\n\r\n```js\r\n// Number of element slots to pre-allocate for an empty array.\r\nstatic const int kPreallocatedArrayElements = 4;\r\n```\r\n\r\n在 JavaScript 中，当数组执行 `push` 操作时，一旦发现数组内存不足，将进行扩容。\r\n\r\n在 Chrome 源码中， `push` 的操作是用汇编实现的，在 c++ 里嵌入的汇编，以提高执行效率，并且在汇编的基础上用 c++ 封装了一层，在编译执行的时候，会将这些 c++ 代码转成汇编代码。\r\n\r\n计算新容量的函数：\r\n\r\n```js\r\n// js-objects.h\r\nstatic const uint32_t kMinAddedElementsCapacity = 16;\r\n\r\n// code-stub-assembler.cc\r\nNode* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity,\r\n                                                      ParameterMode mode) {\r\n  CSA_SLOW_ASSERT(this, MatchesParameterMode(old_capacity, mode));\r\n  Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode);\r\n  Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode);\r\n  Node* padding =\r\n      IntPtrOrSmiConstant(JSObject::kMinAddedElementsCapacity, mode);\r\n  return IntPtrOrSmiAdd(new_capacity, padding, mode);\r\n}\r\n```\r\n\r\n所以扩容后新容量计公式为：\r\n\r\n\u003e new_capacity = old_capacity /2 + old_capacity + 16\r\n\r\n即老的容量的 1.5 倍加上 16 。初始化为 4 个，当 `push` 第 5 个的时候，容量将会变成：\r\n\r\n\u003e new_capacity = 4 / 2 + 4 + 16 = 22\r\n\r\n接着申请一块这么大的内存，把老的数据拷过去，把新元素放在当前 length 位置，然后将数组的 length + 1，并返回 length。\r\n\r\n所以，扩容可以分为以下几步：\r\n\r\n- `push` 操作时，发现数组内存不足\r\n- 申请 new_capacity = old_capacity /2 + old_capacity + 16 那么长度的内存空间\r\n- 将数组拷贝到新内存中\r\n- 把新元素放在当前 length 位置\r\n- 数组的 length + 1\r\n- 返回 length\r\n\r\n整个过程，用户是无感知的，不像 C，需用用户手动申请内存空间。\r\n\r\n当数组执行 `pop` 操作时，会判断 `pop` 后数组的容量，是否需要进行减容。\r\n\r\n不同于数组的 `push` 使用汇编实现的， `pop` 使用 c++ 实现的。\r\n\r\n判断是否进行减容：\r\n\r\n```js\r\nif (2 * length \u003c= capacity) {\r\n  // If more than half the elements won't be used, trim the array.\r\n  isolate-\u003eheap()-\u003eRightTrimFixedArray(*backing_store, capacity - length);\r\n} else {\r\n  // Otherwise, fill the unused tail with holes.\r\n  BackingStore::cast(*backing_store)-\u003eFillWithHoles(length, old_length);\r\n}\r\n```\r\n\r\n所以，当数组 `pop` 后，如果数组容量大于等于 length 的 2 倍，则进行容量调整，使用 `RightTrimFixedArray` 函数，计算出需要释放的空间大小，做好标记，等待 GC 回收；如果数组容量小于 length 的 2 倍，则用 holes 对象填充。\r\n\r\n所以，减容可以分为以下几步：\r\n\r\n- `pop` 操作时，获取数组 `length`\r\n- 获取 `length - 1` 上的元素（要删除的元素）\r\n- 数组 `length - 1`\r\n- 判断数组的总容量是否大于等于 length - 1 的 2 倍\r\n- 是的话，使用 `RightTrimFixedArray` 函数，计算出需要释放的空间大小，并做好标记，等待 `GC` 回收\r\n- 不是的话，用 `holes` 对象填充\r\n- 返回要删除的元素\r\n\r\n\r\n\r\n### 五、解答开篇问题\r\n\r\nJavaScript 中， `JSArray` 继承自 `JSObject` ，或者说它就是一个特殊的对象，内部是以 key-value 形式存储数据，所以 JavaScript 中的数组可以存放不同类型的值。它有两种存储方式，快数组与慢数组，初始化空数组时，使用快数组，快数组使用连续的内存空间，当数组长度达到最大时，`JSArray` 会进行动态的扩容，以存储更多的元素，相对慢数组，性能要好得多。当数组中 `hole` 太多时，会转变成慢数组，即以哈希表的方式（ key-value 的形式）存储数据，以节省内存空间。\r\n\r\n\r\n\r\n### 六、最后附赠一道前端面试题（腾讯）：数组扁平化、去重、排序\r\n\r\n关于 `Array` 的属性、方法这里不再做介绍，详看 [MDN Array](https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array) 。\r\n\r\n面试题：\r\n\r\n\r\n\r\n\u003e  已知如下数组：var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];\r\n\u003e\r\n\u003e  编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组\r\n\r\n\r\n\r\n答案：\r\n\r\n```js\r\nvar arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]\r\n// 扁平化\r\nlet flatArr = arr.flat(4)\r\n// 去重\r\nlet disArr = Array.from(new Set(flatArr))\r\n// 排序\r\nlet result = disArr.sort(function(a, b) {\r\n    return a-b\r\n})\r\nconsole.log(result)\r\n// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]\r\n```\r\n\r\n关于 Set 请查阅 [Set、WeakSet、Map及WeakMap](https://github.com/LuNaHaiJiao/blog/issues/24)\r\n\r\n参考链接：\r\n\r\n[探究JS V8引擎下的“数组”底层实现](https://juejin.im/post/5d80919b51882538036fc87d)\r\n\r\n[从Chrome源码看JS Array的实现](https://zhuanlan.zhihu.com/p/26388217)\r\n\r\n### 七、认识更多的前端道友，一起进阶前端开发\r\n\r\n前端算法集训营第一期免费开营啦🎉🎉🎉，免费哟！\r\n\r\n在这里，你可以和志同道合的前端朋友们（600+）一起进阶前端算法，从0到1构建完整的数据结构与算法体系。\r\n\r\n在这里，瓶子君不仅介绍算法，还将算法与前端各个领域进行结合，包括浏览器、HTTP、V8、React、Vue源码等。\r\n\r\n在这里，你可以每天学习一道大厂算法题（阿里、腾讯、百度、字节等等）或 leetcode，瓶子君都会在第二天解答哟！\r\n\r\n更多福利等你解锁🔓🔓🔓！\r\n\r\n在公众号「前端瓶子君」内回复「算法」即可加入。你的关注就是对瓶子君最大的支持😄😄😄\r\n","author":{"url":"https://github.com/sisterAn","@type":"Person","name":"sisterAn"},"datePublished":"2020-04-02T02:11:13.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":9},"url":"https://github.com/2/JavaScript-Algorithms/issues/2"}