# JS 数组 ## 简介 数组、链表、栈、队列都是线性表，它表示的结构都是一段线性的结构，与之对应的就是非线性表，例如树、图、堆等，它表示的结构都非线性。 本节主要介绍 JavaScript 数组，在开始本章节前，思考一个问题： 我们知道在 JavaScript 中，可以在数组中保存不同类型值，并且数组可以动态增长，不像其它语言，例如 C，创建的时候要决定数组的大小，如果数组满了，就要重新申请内存空间。这是为什么喃？ 本节从 Chrome v8 源码角度回答这个问题，分为四个方面： * 数组基础入门 * JavaScript 中，数组为什么可以保存不同类型？ * JavaScript 中，数组是如何存储的喃？ * JavaScript 中，数组的动态扩容与减容 ## 数组（基础） 一种最基础的数据结构，每种编程语言都有，它编号从 0 开始，代表一组连续的储存结构，用来储存同一种类型的数据。 ```javascript let arr = [1, 2, 3] ``` 它的这种特定的存储结构（连续存储空间存储同一类型数据）决定了： **优点** * 随机访问：可以通过下标随机访问数组中的任意位置上的数据 **缺点** * 对数据的删除和插入不是很友好 **查找：** 根据下标随机访问的时间复杂度为 O(1)； **插入或删除：** 时间复杂度为 O(n)； 在 JavaScript 中的数组几乎是万能的，它不光可以作为一个普通的数组使用，可以作为栈或队列使用。 数组： ```javascript let array = [1, 2, 3] ``` 栈： ```javascript let stack = [1, 2, 3] // 进栈 stack.push(4) // 出栈 stcak.pop() ``` 队列： ```javascript let queue = [1, 2, 3] // 进队 queue.push(4) // 出队 queue.shift() ``` ## JS 中数组可以保存不同类型 看一下 Chrome v8 源码： ```javascript // The JSArray describes JavaScript Arrays // Such an array can be in one of two modes: // - fast, backing storage is a FixedArray and length <= elements.length(); // Please note: push and pop can be used to grow and shrink the array. // - slow, backing storage is a HashTable with numbers as keys. class JSArray: public JSObject { public: // [length]: The length property. DECL_ACCESSORS(length, Object) // ... // Number of element slots to pre-allocate for an empty array. static const int kPreallocatedArrayElements = 4; }; ``` 我们可以看到 `JSArray` 是继承自 `JSObject` 的，所以在 JavaScript 中，数组可以是一个特殊的对象，内部也是以 key-value 形式存储数据，所以 JavaScript 中的数组可以存放不同类型的值。 ## JS 中数据的存储 ```javascript // The JSArray describes JavaScript Arrays // Such an array can be in one of two modes: // - fast, backing storage is a FixedArray and length <= elements.length(); // Please note: push and pop can be used to grow and shrink the array. // - slow, backing storage is a HashTable with numbers as keys. class JSArray: public JSObject { public: // [length]: The length property. DECL_ACCESSORS(length, Object) // ... // Number of element slots to pre-allocate for an empty array. static const int kPreallocatedArrayElements = 4; }; ``` `JSArray` 继承于 `JSObject` ，从注释上看，它有两种存储方式： * fast：存储结构是 `FixedArray` ，并且数组长度 `<= elements.length()` ，`push` 或 `pop` 时可能会伴随着动态扩容或减容 * slow：存储结构是 `HashTable`（哈希表），并且数组下标作为 `key` `fast` 模式下数组在源码里面叫 `FastElements` ，而 `slow` 模式下的叫做 `SlowElements` 。 ### 快数组 `FixedArray` 是 V8 实现的一个类似于数组的类，它表示一段连续的内存，可以使用索引直接定位。新创建的空数组默认就是快数组。当数组满（数组的长度达到数组在内存中申请的内存容量最大值）的时候，继续 `push` 时， `JSArray` 会进行动态的扩容，以存储更多的元素。 ### 慢数组 慢数组以哈希表的形式存储在内存空间里，它不需要开辟连续的存储空间，但需要额外维护一个哈希表，与快数组相比，性能相对较差。 ```javascript // src/objects/dictionary.h class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Dictionary : public HashTable { using DerivedHashTable = HashTable; public: using Key = typename Shape::Key; // Returns the value at entry. inline Object ValueAt(InternalIndex entry); inline Object ValueAt(const Isolate* isolate, InternalIndex entry); // ... }; ``` 从源码中可以看出，它的内部就是一个 HashTable。 ### **什么时候会从 fast 转变为 slow ？** 当处于以下情况时，快数组会被转变为慢数组： * 当加入的索引值 index 比当前容量 capacity 差值大于等于 1024 时（index - capacity >= 1024） * 快数组新容量是扩容后的容量 3 倍之多时 例如：向快数组里增加一个大索引同类型值 ```javascript var arr = [1, 2, 3] arr[2000] = 10; ``` 当往 `arr` 增加一个 `2000` 的索引时，`arr` 被转成慢数组。节省了大量的内存空间（从索引为 2 到索引为 2000）。 ### **什么时候会从 slow 转变为 fast ？** 当慢数组的元素可存放在快数组中且长度在 smi 之间且仅节省了50%的空间，则会转变为快数组 ## JS 数组动态扩容与减容 ### 扩容 默认空数组初始化大小为 `4` : ```javascript // Number of element slots to pre-allocate for an empty array. static const int kPreallocatedArrayElements = 4; ``` 在 JavaScript 中，当数组执行 `push` 操作时，一旦发现数组内存不足，将进行扩容。 在 Chrome 源码中， `push` 的操作是用汇编实现的，在 c++ 里嵌入的汇编，以提高执行效率，并且在汇编的基础上用 c++ 封装了一层，在编译执行的时候，会将这些 c++ 代码转成汇编代码。 计算新容量的函数： ```javascript // js-objects.h static const uint32_t kMinAddedElementsCapacity = 16; // code-stub-assembler.cc Node* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity, ParameterMode mode) { CSA_SLOW_ASSERT(this, MatchesParameterMode(old_capacity, mode)); Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode); Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode); Node* padding = IntPtrOrSmiConstant(JSObject::kMinAddedElementsCapacity, mode); return IntPtrOrSmiAdd(new_capacity, padding, mode); } ``` 所以扩容后新容量计公式为： > new\_capacity = old\_capacity /2 + old\_capacity + 16 即老的容量的 1.5 倍加上 16 。初始化为 4 个，当 `push` 第 5 个的时候，容量将会变成： > new\_capacity = 4 / 2 + 4 + 16 = 22 接着申请一块这么大的内存，把老的数据拷过去，把新元素放在当前 length 位置，然后将数组的 length + 1，并返回 length。 所以，扩容可以分为以下几步： * `push` 操作时，发现数组内存不足 * 申请 new\_capacity = old\_capacity /2 + old\_capacity + 16 那么长度的内存空间 * 将数组拷贝到新内存中 * 把新元素放在当前 length 位置 * 数组的 length + 1 * 返回 length ### 减容 当数组执行 `pop` 操作时，会判断 `pop` 后数组的容量，是否需要进行减容。 不同于数组的 `push` 使用汇编实现的， `pop` 使用 c++ 实现的。 判断是否进行减容： ```javascript if (2 * length <= capacity) { // If more than half the elements won't be used, trim the array. isolate->heap()->RightTrimFixedArray(*backing_store, capacity - length); } else { // Otherwise, fill the unused tail with holes. BackingStore::cast(*backing_store)->FillWithHoles(length, old_length); } ``` 所以，当数组 `pop` 后，如果数组容量大于等于 length 的 2 倍，则进行容量调整，使用 `RightTrimFixedArray` 函数，计算出需要释放的空间大小，做好标记，等待 GC 回收；如果数组容量小于 length 的 2 倍，则用 holes 对象填充。 所以，减容可以分为以下几步： * `pop` 操作时，获取数组 `length` * 获取 `length - 1` 上的元素（要删除的元素） * 数组 `length - 1` * 判断数组的总容量是否大于等于 length - 1 的 2 倍 * 是的话，使用 `RightTrimFixedArray` 函数，计算出需要释放的空间大小，并做好标记，等待 `GC` 回收 * 不是的话，用 `holes` 对象填充 * 返回要删除的元素 ## 总结 JavaScript 中， `JSArray` 继承自 `JSObject` ，或者说它就是一个特殊的对象，内部是以 key-value 形式存储数据，所以 JavaScript 中的数组可以存放不同类型的值。它有两种存储方式，快数组与慢数组，初始化空数组时，使用快数组，快数组使用连续的内存空间，当数组长度达到最大时，`JSArray` 会进行动态的扩容，以存储更多的元素，相对慢数组，性能要好得多。当数组中 `hole` 太多时，会转变成慢数组，即以哈希表的方式（ key-value 的形式）存储数据，以节省内存空间。 ## 参考 1. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mm.ricky.moe/javascript/v8/v8-js-array.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.