在JavaScript中数组是很容易修改通过添加和删除项目。它有点掩盖一个事实，即大多数语言阵列是固定尺寸的，并且需要复杂的操作来调整。似乎的JavaScript可以很容易地编写业绩不佳的阵列code。这就引出了一个问题：

Arrays in JavaScript are very easy to modify by adding and removing items. It somewhat masks the fact that most languages array's are fixed-size, and require complex operations to resize. It seems that JavaScript makes it easy to write poorly performing array code. This leads to the question:

我可以从JavaScript实现期望的问候阵列的性能表现是什么（在大O时间复杂性方面）？

我认为所有合理的JavaScript实现至少有以下大O的。

I assume that all reasonable JavaScript implementations have at least the following big O's.

访问 - O（1） 在追加 - 为O（n） prepending - 为O（n） 插入 - 为O（n） 删除 - 为O（n） 在交换 - O（1）

JavaScript允许你pre-填充数组到一定规模后，使用新阵列（长度）语法。 （奖金问题：是建立以这种方式Ø数组（1）或O（n））的这更像是一个传统的数组，如果用作pre-大小的数组，可以让O（1）追加。如果循环缓冲区逻辑添加，就可以实现O（1）prepending。如果动态扩展阵列时，O（log n）的将是平均情况下为两个。

JavaScript lets you pre-fill an array to a certain size, using new Array(length) syntax. (Bonus question: Is creating an array in this manner O(1) or O(n)) This is more like a conventional array, and if used as a pre-sized array, can allow O(1) appending. If circular buffer logic is added, you can achieve O(1) prepending. If a dynamically expanding array is used, O(log n) will be the average case for both of those.

我能想到的一些事情比我的假设在这里更好的性能？我不期待任何东西在任何规格概述，但实际上它可能是所有主要实现在后台使用优化的阵列。是否有动态扩展的阵列或一些其它的性能提升算法的工作？

Can I expect better performance for some things than my assumptions here? I don't expect anything is outlined in any specifications, but in practice it could be that all major implementations use optimized arrays behind the scenes. Are there dynamically expanding arrays or some other performance boosting algorithms at work?

P.S。

我不知道这样做的原因是因为我研究了一些排序算法，其中大部分似乎认为追加和删除是O（1）操作说明他们的整体大O的时候。

The reason I'm wondering this is because I'm researching some sorting algorithms, most of which seem to assume appending and deleting are O(1) operations when describing their overall big O.

推荐答案

在与大多数语言，它实现与，以及阵列，阵列中，JavaScript数组是对象，并且值存储在一个哈希表中，就像普通的对象值。因此：

In contrast to most languages, which implement arrays with, well, arrays, in Javascript Arrays are objects, and values are stored in a hashtable, just like regular object values. As such:

访问 - O（1） 在追加 - 摊销O（1）（有时调整哈希表是必需的;通常只插入是必需的） prepending - 通过 O（n）的不印字，因为它需要重新分配所有的指标 插入 - 摊销O（1）如果该值不存在。 O（n）的，如果你想移动现有值（例如，使用拼接）。 删除 - 摊销O（1）取一个值，为O（n），如果你想通过来重新分配指数拼接 在交换 - O（1） Access - O(1) Appending - Amortized O(1) (sometimes resizing the hashtable is required; usually only insertion is required) Prepending - O(n) via unshift, since it requires reassigning all the indexes Insertion - Amortized O(1) if the value does not exist. O(n) if you want to shift existing values (Eg, using splice). Deletion - Amortized O(1) to remove a value, O(n) if you want to reassign indices via splice. Swapping - O(1)

在一般情况下，设置或注销的字典任何按键摊销O（1），和同样的阵列，无论指数是什么。任何需要重编现有值的操作是O（n），只是因为你必须更新所有受影响的值。

In general, setting or unsetting any key in a dict is amortized O(1), and the same goes for arrays, regardless of what the index is. Any operation that requires renumbering existing values is O(n) simply because you have to update all the affected values.