15

可能重复:
Javascript 数组是否稀疏?

我目前正在学习 JavaScript,并且一直在阅读一些简单的介绍和教程。在查看 Array 对象时,我偶然发现了一些细节,这让我觉得很奇怪,来自其他语言,如 C/Java/Scala/...


所以让我们假设我们这样定义一个数组:

var arr = ['foo','bar','qux']

我们现在分配

arr[5] = 'baz'

这导致我们的数组看起来像这样:

arr
>> ["foo", "bar", "qux", undefined, undefined, "baz"]

而且长度符合预期

arr.length
>> 6

JavaScript 已经将我们的数组扩展到所需的长度 - 六 - 并且新项目设置为未定义 - 除了我们实际分配值的那个。

从低层次的角度来看,这在记忆方面是可怕的。通常,数组将是内存中的连续范围 - 使数组更大通常涉及将整个数组复制到足够大小的新内存位置。这是一个非常昂贵的操作。

现在,我确实意识到这可能不是JavaScript 引擎正在做的事情,因为围绕数组进行复制会非常昂贵,并且内存空间会浪费在所有这些“未定义”值上。

谁能告诉我门后到底发生了什么?

  • 数组实际上是某种类型的链表吗?
  • “未定义”的数组项是否真的存在?
  • 使用大部分充满“未定义”的大型数组有多昂贵?
4

5 回答 5

16

在 JavaScript 的第一个版本中,没有数组。它们后来被作为“所有对象之母”的子类引入:Object。你可以通过这样做很容易地测试它:

var foo = [1,2,3,4];
for (var n in foo)
{//check if n is equal (value and type) to itself, coerced to a number
    console.log(n === +(n) ? 'Number' : 'String');
}

这将String一次又一次地记录。在内部,所有数字键都转换为字符串。Length 属性仅获取最高索引,并将其加 1。而已。当你显示你的数组时,对象被迭代,并且对于每个键,相同的规则适用于任何对象:首先扫描实例,然后是原型......所以如果我们稍微改变我们的代码:

var foo = [1,2,3,4];
foo[9] = 5;
for (var n in foo)
{
    if (foo.hasOwnProperty(n))
    {//check if current key is an array property
        console.log(n === +(n) ? 'Number' : 'String');
    }
}

你会注意到数组只有 5 个自己的属性,undefined键 4-8 是未定义的,因为在实例中没有找到对应的值,在任何底层原型中也没有。简而言之:数组并不是真正的数组,而是行为相似的对象。

正如 Tim 所说,您可以拥有一个具有未定义属性的数组实例,该属性确实存在于该对象中:

var foo = [1,2,undefined,3];
console.log(foo[2] === undefined);//true
console.log(foo[99] === undefined);//true

但同样,有一个区别:

console.log((foo.hasOwnProperty('2') && foo[2] === undefined));//true
console.log((foo.hasOwnProperty('99') && foo[99] === undefined));//false

回顾一下,你的三个主要问题:

  • 数组是对象,允许您使用数字实例引用它们的属性

  • 这些undefined值不存在,它们只是 JS 扫描对象和原型并且找不到您要查找的内容时的默认返回值:“对不起,您问我的内容在我的书中未定义。” 就是它所说的。

  • 使用大部分未定义的数组不会影响对象本身的大小,但是访问未定义的键可能会非常非常慢,因为原型也必须被扫描。

更新:

只需引用 Ecma std

15.4 数组对象
数组对象对某一类属性名称给予特殊处理。当且仅当 ToString(ToUint32(P)) 等于 P 并且 ToUint32(P) 不等于 2^32 1 时,属性名称 P(以字符串值的形式)是数组索引。属性名称为数组索引的属性也称为元素。每个 Array 对象都有一个长度属性,其值始终是小于 2^32 的非负整数。length 属性的值在数值上大于名称为数组索引的每个属性的名称;每当创建或更改 Array 对象的属性时,都会根据需要调整其他属性以保持此不变性。具体来说,每当添加名称为数组索引的属性时,都会更改长度属性,如有必要,比该数组索引的数值大一;并且每当更改长度属性时,所有名称为数组索引且值不小于新长度的属性都会被自动删除。此约束仅适用于 Array 对象的自身属性,不受可能从其原型继承的长度或数组索引属性的影响。

如果以下算法返回 true,则称对象 O 是稀疏的:
1. 设 len 为使用参数“length”调用 O 的 [[Get]] 内部方法的结果。
2. 对于0≤i
    a 范围内的每个整数i。令 elem 为使用参数 ToString(i) 调用 O 的 [[GetOwnProperty]] 内部方法的结果。
     湾。如果 elem 未定义,则返回 true。
3. 返回假。

于 2012-09-28T13:05:02.740 回答
4

数组只是对象的有序列表。在 JavaScript 中,一切都是对象,因此数组并不是我们所知道的真正的数组 :)

你可以在这里找到一些内部结构。

对于您对使用大型数组的疑问......好吧,请记住,您在“客户端”进行的计算越少,您的页面就会越快。

于 2012-09-28T12:50:14.187 回答
1

答案:

  1. lengthJavaScript 中的数组与具有魔法属性和额外原型方法(push()等)的对象(即无序的属性集合)相同。
  2. 不,未定义的项目不存在。JavaScript 有一个in运算符来测试是否存在可以用来证明这一点的属性。所以对于下面的数组:var arr = ['foo']; arr[2] = 'bar';2 in arr返回true1 in arr返回false
  3. 稀疏数组不应比密集数组占用更多内存,密集数组的长度是稀疏数组中实际定义的属性数。当您迭代其未定义的属性时,使用稀疏数组只会更加昂贵。
于 2012-09-28T12:59:34.933 回答
0

大多数 javascript 实现将数组实现为某种形式的二叉树或哈希表,以数组索引作为键,因此大量未定义的对象不会占用任何内存。

于 2012-09-28T13:07:35.510 回答
0

有人告诉我,数组分为两部分,[值,指针]。所以 arr[2] 的指针为空。当您添加 5 时,它会将地址从 null 更改为指向数字 3,该数字指向数字 4,该数字指向数字 5,该数字为 null(因此数组结束)。

我不确定这是多么真实,因为我从未真正检查过它。但这似乎是有道理的。

因此,您不能像在 ac 类型数组上那样进行数学运算(即,要达到值 4,只需执行起始内存点 + 4x(内存中的对象数量)),但是您可以通过逐个跟随数组来做到这一点

于 2012-09-28T13:24:06.917 回答