在JavaScript开发中,数组是一种常用的数据结构,但很少有人深入探究其在底层的实现细节。虽然不必了解这些细节也能有效地使用JavaScript,但深入了解可以帮理解可能遇到的性能问题,因此这是一项值得投入时间的研究。具体实现方式取决于使用的JavaScript解释器或虚拟机。本文将以V8 JavaScript引擎(Chrome和Node.js使用)为例进行说明。其他JavaScript引擎,如Mozilla的SpiderMonkey和Microsoft的Chakra,实现方式相似但并不完全相同。
在V8中,如果数组仅包含整数,它将由一个C++整数数组支持。通常,这个支持数组会比当前包含的整数数量大。如果数组包含整数和浮点值的混合,或者仅包含浮点值,它将由一个双精度数组支持。如果数组仅包含对象,或者数字和对象的混合,它将由一个指针数组支持。尽管JavaScript本身没有“整数”或“双精度”的概念——它将它们都视为“数字”,但V8会跟踪并确保如果只在数组中放入整数,数组会更快且更节省内存。
当调用push()
方法时,如果支持数组已满,它将分配一个新的更大的支持数组,复制现有元素,然后添加推送的新值。这类似于Java中的ArrayList
或C++中的vector
的实现。
上述所有内容仅适用于数组是密集的,而不是稀疏的——即,数组中没有间隙。如果做了类似以下操作:
let abc = [1,2,3];
abc[100] = 50;
那么现在就有了一个稀疏数组。如果它不是太稀疏,它仍然会由数组支持,空数组索引被替换为“洞”值。如果查看V8的C++数组源代码(下面链接),会看到对element->is_the_hole(i)
的调用。如果数组非常稀疏,它将不再由内存中的数组支持。相反,它将由字典/哈希表支持,这将使得访问元素和遍历数组需要更长的时间。
如果感兴趣,可以在这里阅读V8的数组实现:。会注意到它经常检查以下常量:
会看到它总是尝试做对它正在操作的数组最快的操作。许多内置函数,如push
、pop
、shift
、unshift
和concat
,会根据数组的密度和包含的元素类型做不同的事情。
还有一些其他需要注意的事情:如果有一个仅包含整数的数组,并且推送了一个浮点数或其他类型的值,它将被“降级”为其余生命周期,即使清除了非整数。另外,请记住,这些实现细节并不保证。一个简单的JavaScript数组对象的实现可以由一个链表支持,它仍然会像现在这样工作。只是会更慢。
实际上,如果获取20年前的Mozilla源代码的早期副本,会发现数组是由普通的JS对象支持的,没有太多优化,只是一些额外的代码来处理特殊情况,如length
属性。