JavaScript数组实际上是链接列表吗？

Question

我是Javascript的新手,并注意到你不需要指定一个数组的大小,并经常看到人们一次动态创建数组元素.这在其他语言中将是一个巨大的性能问题,因为随着它的大小增加,您将不断需要为该阵列重新分配内存.

这不是JavaScript中的问题吗？如果是这样,那么是否有可用的列表结构？

Answer 1

它很可能取决于您使用的JavaScript引擎.

Internet Explorer使用稀疏数组和密集数组的混合来实现这一点.这里解释了一些更为详尽的细节:http://blogs.msdn.com/b/jscript/archive/2008/04/08/performance-optimization-of-arrays-part-ii.aspx.

Answer 2

Javascript数组通常实现为散列图(就像Javascript对象一样),并带有一个附加功能:有一个属性length,它比已用作键的最高正整数高一个.没有什么阻止你也使用字符串,浮点数,甚至是负数作为键.除了好感之外什么也没有.

Answer 3

关于动态语言的事情是,它们是动态的.就像Java中的ArrayList或Perl,PHP和Python中的数组一样,JavaScript中的数组将分配一定量的内存,当它变得太大时,语言会自动附加到对象上.它是否像C++甚至Java一样高效？否(C++甚至可以围绕JS的最佳实现运行),但人们并没有在JS中构建Quake(仅此而已).

实际上,最好将它们视为具有一些专门方法的HashMaps - 毕竟,这是有效的:var a = []; a['cat']='meow';.

Answer 4

没有.

JavaScript数组是什么和不是由语言规范第15.4节确定. Array根据它提供的操作来定义任何特定数据结构的存储器布局的实现细节.

可以Array在链表上实现吗？是.这可能使某些操作变得更快,例如shift和unshift效率,但Array也经常被它是没有效率的用链表的索引访问.

如果没有链接列表,也可以获得两全其美的效果.诸如循环队列之类的连续存储器数据结构具有从前面有效插入/移除和有效随机访问.

在实践中,大多数解释器通过使用基于类似于C++ vector或Java 的可调整大小或可重新分配的数组的数据结构来优化密集阵列ArrayList.