JavaScript数组实际上是链表吗？

Question

我是Javascript的新手，注意到你不需要指定一个数组的大小，经常看到人们动态地一个一个元素地创建数组。在其他语言中，这将是一个巨大的性能问题，因为你需要不断重新分配内存来增加数组的大小。

这在Javascript中是否不是一个问题？如果是，那么有没有可用的列表结构？

- nw.

---

在具有可调整大小数组的语言中，每次需要增长时实际分配的内存通常会加倍。因此，在任何语言中都不需要不断重新分配内存。 - Winston Ewert

谢谢大家，这对我来说很有效。我只是想确保我不会犯JavaScript的错误。 - nw.

Answer 1

Javascript数组通常被实现为哈希表（与Javascript对象相同），但有一个额外的特性：它们有一个名为length的属性，该属性的值是最高正整数键值加1。您可以使用字符串、浮点数甚至负数作为键值，但这不太明智。

- Michael Lorton

Answer 2

这很可能取决于您使用的JavaScript引擎。

Internet Explorer使用稀疏数组和密集数组的混合来使其工作。更多细节可以在此处找到：http://blogs.msdn.com/b/jscript/archive/2008/04/08/performance-optimization-of-arrays-part-ii.aspx。

- vcsjones

Answer 3

关于动态语言的特点，它们是动态的。就像 Java 中的 ArrayList 或 Perl、PHP 和 Python 中的数组一样，JavaScript 中的数组将分配一定量的内存，当它变得过大时，语言会自动附加到对象中。它是否像 C++ 甚至 Java 那样高效？不是的（即使是 JS 的最佳实现也不能与 C++ 相提并论），但人们并没有在 JS 中构建 Quake（尚未）。

实际上，更好的方法是将它们视为带有一些专门方法的 HashMaps--毕竟，这是有效的：var a = []; a['cat'] ='meow';。

- cwallenpoole

---

可能取决于您对“有效”的定义。它肯定可以在符合Javascript的每个版本上运行，它是高效和可移植的，以及所有其他好的计算机科学特性。然而，这是一个非常糟糕的计划。 - Michael Lorton

人们已经用 JS 和 webGL 构建了地震模拟器 :P。 - fabspro

阅读你的评论，2023年只是微笑 @fabspro - undefined

@IsmoilShokirov 现在被称为“网络平台”的东西确实发生了很大变化：') - undefined

Answer 4

不是。

JavaScript数组的定义和特性由语言规范确定，具体来说是15.4章节。 Array是根据它提供的操作来定义的，而不是任何特定数据结构的内存布局实现细节。

Array可以基于链表实现吗？ 可以。这可能会使某些操作更快，例如shift和unshift，但是使用链表进行索引访问并不高效。

也有可能在不使用链表的情况下同时实现两者的优点。连续内存数据结构，例如循环队列，既具有从前面高效插入/删除的能力，又具有高效的随机访问。

实际上，大多数解释器通过使用基于可调整大小或可重新分配数组的数据结构来优化稠密数组，类似于C ++的vector或Java的ArrayList。

- Mike Samuel

Answer 5

他们实际上更像使用属性作为索引的自定义对象。 例如：

var a = { "1": 1, "2": 2};
a.length = 2;
for(var i=0;i<a.length;i++)
    console.log(a[i]);

< p >a 会表现得几乎像一个数组，而且你也可以在它上面调用 Array.prototype 中的函数。

- Eliu

---

你不会想念零索引吗？ - Zlatko

我不知道@Eliu想要展示什么。代码永远不会以这种方式工作（也许是意图？？）。字符串键需要被引用为字符串，而不是整数。因此，即使a[1]也不会产生值。列出项目的正确代码应该使用for .. in或使用例如console.log(a[''+(i+1)]);。 - Michiel van der Blonk

@MichielvanderBlonk 这完全不正确。对象只能有字符串和符号作为属性标识符。如果您使用数字访问属性，它将被转换为字符串。@Eliu的代码在修复缺少对象a的0索引后将起作用。我认为他试图表明数组只是具有数字作为其属性键的普通对象。 - Leonardo Raele

@LeonardoRaele 是的，你说得对。我试了一下这段代码，它确实可以工作，但大多数情况下是作为副作用而不是预期效果。我认为这可能会让 OP 更加困惑，尽管从技术上讲是正确的。 考虑以下代码：a.length = 4; for(var i=0;i - Michiel van der Blonk

我不明白你的观点。你所说的“副作用”是什么意思？当然，在你的例子中，对于0和2，它将打印“undefined”，因为这些键在对象中不存在。 - Leonardo Raele

Answer 6

Javascript数组不像C/C++或其他语言那样是真正的数组。因此，它们并不像真正的数组那样高效，但很容易使用，且不会抛出越界异常。

- FishBasketGordo