摘自http://www.codermagefox.com/post/zhkaug
**

从几道面试题说说Js Array

2020-10-20
其实认识我的人都知道,我不太喜欢写这种东西.

但是最近碰到有朋友问了我几道面试题,我进行解答以后发现和他看到的解析文章完全不同.

于是对这几个问题仔细的看了一下,发现网上的文章真的有很多谬误.

不敢说正本清源,但是希望能纠正一下网上谬误的知识吧.

0.题目

其实问题的初始,是这样的几道题:
1.JavaScript里的数组,存储数据在内存中是连续的还是不连续的?
2.面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?
3.为什么JS里的数组可以存储对象?
4.为什么typeof Array是对象?

如果看到这个问题而去网上搜索的话,大概会搜到这样的几篇文章:

CSDN:
https://www.csdn.net/gather_2e/OtDaUgxsOTUzLWJsb2cO0O0O.html
https://blog.csdn.net/donspeng/article/details/83444861

掘金:
https://juejin.im/post/6844903854882947080
https://juejin.im/post/6844904047934373896

开源中国:
https://wiki.jikexueyuan.com/project/brief-talk-js/arrays-and-dictionaries.html

其实大部分文章都是类似的文章,就不一一列举.

例举这些东西不是为了鞭尸,只是想说,这个东西真的很多人的认知是错误的.

1.问题提炼

如果你真的看了这些搜索而来的文章,那么你就会对以下的几个问题感到非常困惑:

JavaScript中的对象到底是内存连续的还是不连续的?怎么他们说的不一样?
为什么有人说数组是在内存栈中连续的值,有人说数组是基于HashMap的?怎么说啥的都有?
数组存储数据到底是在堆里还是栈里?怎么也不一样?
为什么有人说数组的定义必须要相同类型啊?数组明明可以存储不同类型的数据啊?

所以这就是为什么我们需要一个良好的信息源与独立思考的能力.

首先我们感谢网上作者们的分享,但是确实是存在一定的谬误.

好的.让我们来解决这四道面试题.但是请记住:
**
面试不是目的,知识才是目的.

2.常规语言里的数组

首先我们来看看数组的定义:
https://en.wikipedia.org/wiki/Array_data_structure
快数组vs慢数组 - 图1
在这里,我们可以看到,它很清晰的写了:
数组很有用，主要是因为可以在运行时计算元素索引。除其他外，此功能允许单个迭代语句任意处理数组的许多元素。因此，数组数据结构的元素必须具有相同的大小，并应使用相同的数据类型。有效索引元组的集合和元素的地址（以及元素的寻址公式）通常在使用数组时固定为，但并不总是固定。

等等,好像有什么地方不太对.

//Array?
const a = [1,2,3]
const b = ['1',2,3]

如果你问一个Java程序员,定义一个这样的结构会导致什么,他肯定一脸懵逼的说:你这个根本不是数组啊,是集合啊.
如果这么定义,在Java里是会直接报错的.

但是,在JavaScript程序员眼中,这就是一个再正常不过的数组.

事情开始变的有些奇怪了:大家对数组的认知好像并不一样?

这也就是为什么网上有很多迷惑文章的原因了:错把JavaScript中数组认成计算机科学中的标准数组.

所以我们首先要搞清楚的是:

JavaScript中的数组其实是一种概念上的数组,它实际上并不是真正意义上的数组(以下所有描述都默认为V8)

3.JavaScript里的数组

3-1 那么,它究竟是什么?

从网上很多迷惑文章里其实可以看到,很多人对数组里实际的内存分配各执一词.

.有说连续的,也有说不连续的.有说是基于Map实现的,有说是基于栈实现的

其实根本原因是因为:
他们说的都对.但是都对的不完全.

3-2 真实的数组

那么,看到这里,我们就可以说说,到底JavaScript里的数组是什么了.
首先,JavaScript中的数组其实分为快数组和慢数组.
**等等,快数组和慢数组?这是什么概念?我怎么好像没有听过?

所以介绍之前,得先介绍一下快属性和慢属性.

首先,众所周知,线性的数据结构读取速度更快(O(1)),因此我们将存储在线性数据结构中的命名属性称之为快属性.

但是很容易想到的是,线性数据结构在频繁插入和删除时,复杂度均为O(n).

为了减少这个部分的开销,V8会将原本存储在线性结构中的数据存储在properties内部维护的一个字典(称为 Properties Dictionary)中.这里为了简化理解,可以理解为存贮在堆中.存贮在堆中的,就是被降级了的慢属性.

那么推广到数组这个数据结构,我们就可以得出一个结论:存贮在线性结构中的数组就是快数组,存储在非线性结构中的就是慢数组.
那么我们就可以得出快数组和慢数组的概念:
快数组:它在内存中是连续的空间，直接通过索引读写值。
慢数组:V8 创建了一个HashTable来记录映射关系，其中索引的整数值即是字典的键.

这也就是为什么可以解释有些人认为数组是连续的,有些人认为不是的了.他们说的都对,但是都不完全对.

3-3 快数组和慢数组的界定

那么问题来了,如何判断一个数组是快数组还是慢数组呢?
本来想在这个地方直接放实现,但是想想看,没啥必要.
想要看具体实现的可以移步https://v8.dev/blog/fast-properties
记住以下几点就行了:
快变慢:
1.如果快数组扩容后的容量是原来的 3 倍以上，意味着它比 HashTable 形式存储占用更大的内存，快数组会转换为慢数组.
2.如果快数组新增的索引与原来最大索引的差值大于 1024，快数组会被转换会慢数组.
3.如果数组中存储的数据类型在一种以上,就会变成慢数组.

慢变快:
当慢数组转换成快数组能节省不少于 50% 的空间时，才会将其转换.

4.重新看看面试题.

现在,我们能够重新回来看看这几道面试题了.
1.JavaScript里的数组,存储数据在内存中是连续的还是不连续的?
答:可以连续也可以不连续,关键在于它是快数组还是慢数组.

100万个成员的数组取第一个和最后一个有性能差距吗?
答:没有性能差距,都是O(1).因为慢数组的本质是HashTable.

3.为什么JS里的数组可以存储对象?
答:因为JS的数组如果存储了对象,它就不再是传统意义上的数组,而是JavaScript中的”慢数组”.而慢数组,是以HashTable的形式存储的,所以可以存储对象.
4.为什么typeof Array是对象?
答:因为Array还真就是对象.它的实现JSArray继承自JSObject，即数组是一个特殊的对象，而 JS 中所有非原始类型都是对象的实例，所以 JS 中数组可以存储多种类型的值.(谬误:从原型链方面去回答)