当用作哈希时,JavaScript数组的大O是多少？

Question

当用作哈希时,JavaScript的数组访问的大O是什么？

例如,

var x= [];
for(var i=0; i<100000; i++){
   x[i.toString()+'a'] = 123; // using string to illustrate x[alpha]
}
alert(x['9999a']); // linear search?

人们可以希望JS引擎不会在内部使用线性搜索O(n),但这是肯定的吗？

Answer 1

在语法中,访问JavaScript中的对象属性和数组元素是在恒定时间内完成的:O(1).ECMAScript规范不保证性能特征,但所有现代JavaScript引擎都在恒定时间内检索对象属性.

这是一个简单的示例,显示了当容器大x1000倍时访问时间的增长情况:

var largeObject = {};
var smallObject = {};

var x, i;

for (i = 0; i < 1000000; i++) {
   largeObject['a' + i] = i;
}

for (i = 0; i < 1000; i++) {
   smallObject['b' + i] = i;
}

console.time('10k Accesses from largeObject');
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000000)];
console.timeEnd('10k Accesses from largeObject');

console.time('10k Accesses from smallObject');
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000)];
console.timeEnd('10k Accesses from smallObject');

Firebug,Firefox 3.6.10(Mac OS X 10.6.4 - 2.93Ghz Intel Core 2 Duo)中的结果:

10k Accesses from largeObject: 22ms
10k Accesses from smallObject: 19ms

Chrome Dev Tools 6.0.472中的结果:

10k Accesses from largeObject: 15ms
10k Accesses from smallObject: 15ms

Windows 7上带有Firebug Lite的Internet Explorer 8.0.7600

10k Accesses from largeObject: 250ms
10k Accesses from smallObject: 219ms

Answer 2

首先,阵列实际上是哈希.永远.这就是原因x[5] === x["5"]:

var x = [];
x[5] = 10;
alert( x[5] === x["5"] ); // true

对象是哈希,而数组只是特殊对象.如果你想使用一般哈希去对象.Javascript中的"关联数组"是对象.数组用于数字索引数据.阵列具有length属性和阵列状的方法,如push,pop,sort等,它们是没有意义要在散列使用.

至于在对象中搜索的大O:它依赖于实现.

可能是你可以做的两件最好的事情:

1. 检查一些浏览器实现的源代码

2. 为大n做一些基准并得出结论

语言规范的相关部分:

4.3.3对象

对象是属性的集合,并且具有单个原型对象.

8.6.2对象内部属性和方法

数组对象的[[DefineOwnProperty]]内部方法的实现略有不同.数组对象对特定类的属性名称进行特殊处理.