javascript - Javascript 数组是稀疏的吗？

Question

也就是说，如果我使用当前时间作为数组的索引：

array[Date.getTime()] = value;

解释器会实例化从 0 到现在的所有元素吗？不同的浏览器做的不同吗？

我记得AIX内核中曾经有一个错误，它会根据请求创建伪 tty，但如果你这样做了，比如“echo > /dev/pty10000000000”，它会创建 /dev/pty0、/dev/pty1、 ....然后摔死。贸易展很有趣，但我不希望这种情况发生在我的客户身上。

score 75 · Accepted Answer

是的，他们是。它们实际上是内部的哈希表，因此您不仅可以使用大整数，还可以使用字符串、浮点数或其他对象。toString()在添加到哈希之前，所有键都通过转换为字符串。您可以使用一些测试代码来确认这一点：

<script>
  var array = [];
  array[0] = "zero";
  array[new Date().getTime()] = "now";
  array[3.14] = "pi";

  for (var i in array) {
      alert("array["+i+"] = " + array[i] + ", typeof("+i+") == " + typeof(i));
  }
</script>

显示：

array[0] = zero, typeof(0) == string
array[1254503972355] = now, typeof(1254503972355) == string
array[3.14] = pi, typeof(3.14) == string

注意我是如何使用for...in语法的，它只给你实际定义的索引。如果您使用更常见for (var i = 0; i < array.length; ++i)的迭代样式，那么您显然会遇到非标准数组索引的问题。

score 42 · Accepted Answer

JavaScript 数组的具体实现方式因浏览器而异，但它们通常会退回到稀疏实现 - 很可能与用于常规对象的属性访问的相同实现 - 如果使用实际数组效率低下。

您必须询问对特定实现有更多了解的人来回答是什么触发了从密集到稀疏的转变，但是您的示例应该是完全安全的。如果你想得到一个密集的数组，你应该用一个显式的长度参数调用构造函数，并希望你真的得到一个。

有关 olliej 的更详细描述，请参阅此答案。

score 11 · Accepted Answer

您可以通过使用专为此类事情设计的 javascript 语法来避免该问题。你可以把它当作一本字典，但是“for ... in ...”语法会让你把它们都抓起来。

var sparse = {}; // not []
sparse["whatever"] = "something";

score 7 · Accepted Answer

Javascript 对象是稀疏的，数组只是具有自动维护的长度属性（实际上比最大索引大一，而不是定义元素的数量）和一些附加方法的特殊对象。无论哪种方式，您都是安全的；如果您需要它的额外功能，请使用数组，否则使用对象。

score 6 · Accepted Answer

与 JavaScript 一样，答案通常是正确的，“它有点奇怪......”

内存使用没有定义，任何实现都是愚蠢的。理论上，const a = []; a[1000000]=0;可以烧掉几兆内存，就可以了const a = [];。在实践中，甚至微软也避免了这些实现。

Justin Love指出，长度属性是最高的索引集。但它仅在索引为整数时更新。

所以，数组是稀疏的。但是像 reduce()、Math.max() 和“for ... of”这样的内置函数将遍历从 0 到长度的整个可能整数索引范围，访问许多返回“未定义”的函数。但是“for ... in”循环可能会如您所愿，仅访问已定义的键。

这是一个使用 Node.js 的示例：

"use strict";
const print = console.log;

let a = [0, 10];
// a[2] and a[3] skipped
a[4] = 40;
a[5] = undefined;  // which counts towards setting the length
a[31.4] = 'ten pi';  // doesn't count towards setting the length
a['pi'] = 3.14;
print(`a.length= :${a.length}:, a = :${a}:`);
print(`Math.max(...a) = :${Math.max(a)}: because of 'undefined values'`);
for (let v of a) print(`v of a; v=:${v}:`);
for (let i in a) print(`i in a; i=:${i}: a[i]=${a[i]}`);

给予：

a.length= :6:, a = :0,10,,,40,:
Math.max(...a) = :NaN: because of 'undefined values'
v of a; v=:0:
v of a; v=:10:
v of a; v=:undefined:
v of a; v=:undefined:
v of a; v=:40:
v of a; v=:undefined:
i in a; i=:0: a[i]=0
i in a; i=:1: a[i]=10
i in a; i=:4: a[i]=40
i in a; i=:5: a[i]=undefined
i in a; i=:31.4: a[i]=ten pi
i in a; i=:pi: a[i]=3.14

但。还有更多尚未提及数组的极端情况。

score 5 · Accepted Answer

可以使用非标准process.memoryUsage()凭经验确认 NodeJS 的稀疏性（或密集性）。

有时节点足够聪明以保持数组稀疏：

Welcome to Node.js v12.15.0.
Type ".help" for more information.
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 3.07 MB
undefined
> array = []
[]
> array[2**24] = 2**24
16777216
> array
[ <16777216 empty items>, 16777216 ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 2.8 MB
undefined

有时节点会选择使其变得密集（这种行为将来可能会得到优化）：

> otherArray = Array(2**24)
[ <16777216 empty items> ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 130.57 MB
undefined

然后再次稀疏：

> yetAnotherArray = Array(2**32-1)
[ <4294967295 empty items> ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 130.68 MB
undefined

因此，也许使用密集数组来感受原始 AIX 内核错误可能需要强制使用range-alike：

> denseArray = [...Array(2**24).keys()]
[
   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,
  12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
  24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
  36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
  48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
  60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
  72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
  84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
  96, 97, 98, 99,
  ... 16777116 more items
]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`);
The script is using approximately 819.94 MB
undefined

因为为什么不让它倒下呢？

> tooDenseArray = [...Array(2**32-1).keys()]

<--- Last few GCs --->

[60109:0x1028ca000]   171407 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure 
[60109:0x1028ca000]   171420 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure 
[60109:0x1028ca000]   171434 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure 


<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x100931399]
    1: StubFrame [pc: 0x1008ee227]
    2: StubFrame [pc: 0x100996051]
Security context: 0x1043830808a1 <JSObject>
    3: /* anonymous */ [0x1043830b6919] [repl:1] [bytecode=0x1043830b6841 offset=28](this=0x104306fc2261 <JSGlobal Object>)
    4: InternalFrame [pc: 0x1008aefdd]
    5: EntryFrame [pc: 0x1008aedb8]
    6: builtin exit frame: runInThisContext(this=0x104387b8cac1 <ContextifyScript map = 0x1043...

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory

Writing Node.js report to file: report.20200220.220620.60109.0.001.json
Node.js report completed
 1: 0x10007f4b9 node::Abort() [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 2: 0x10007f63d node::OnFatalError(char const*, char const*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 3: 0x100176a27 v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 4: 0x1001769c3 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 5: 0x1002fab75 v8::internal::Heap::FatalProcessOutOfMemory(char const*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 6: 0x1005f3e9b v8::internal::Runtime_FatalProcessOutOfMemoryInvalidArrayLength(int, unsigned long*, v8::internal::Isolate*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 7: 0x100931399 Builtins_CEntry_Return1_DontSaveFPRegs_ArgvOnStack_NoBuiltinExit [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 8: 0x1008ee227 Builtins_IterableToList [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
Abort trap: 6

score 1 · Accepted Answer

他们可以，但并不总是必须如此，当他们不是时，他们可以表现得更好。

以下是关于如何在数组实例中测试索引稀疏性的讨论： https ://benmccormick.org/2018/06/19/code-golf-sparse-arrays/

此代码高尔夫（最少字符）获胜者是：

let isSparse = a => !!a.reduce(x=>x-1,a.length)

基本上遍历索引条目的数组，同时递减长度值并返回!!虚假/真实数值结果的硬化布尔值（如果累加器一直递减到零，则索引已完全填充且不稀疏）。Charles Merriam的上述警告也应该考虑在内，这段代码没有解决它们，但它们适用于哈希字符串条目，当分配arr[var]= (something)var 不是整数的元素时可能会发生这种情况。

关心索引稀疏的原因是它对性能的影响，这可能因脚本引擎而异，这里有一个关于数组创建/.initialization 的精彩讨论：声明 JavaScript 时“Array()”和“[]”有什么区别大批？

该帖子的最新答案有一个链接，该链接指向 V8 如何尝试通过标记数组来优化数组以避免（重新）测试稀疏性等特征：https ://v8.dev/blog/elements-kinds 。博客文章来自 17 年 9 月，材料可能会发生一些变化，但对日常开发影响的细分是有用且清晰的。

javascript - Javascript 数组是稀疏的吗？

7 回答 7

Related

Reference