Что такое большая буква для массива JavaScript при использовании в качестве хеша?

Question

Какое большое значение для доступа к массиву JavaScript при использовании в качестве хеша?

Например,

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 извлекают свойства объекта за постоянное время.

Вот простой пример, показывающий, как увеличивается время доступа, когда контейнер увеличивается в 1000 раз:

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.93 ГГц 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

Internet Explorer 8.0.7600 с Firebug Lite в Windows 7

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 свойство и Array-подобные методы, такие как push, pop, sort и т. д., что не имеет смысла использовать на хешах.

Что касается большого O для поиска в объектах: это зависит от реализации.

Вероятно, 2 лучшие вещи, которые вы можете сделать, чтобы:

1. Проверьте исходный код некоторых реализаций браузера

2. Сделайте тест для большого n и сделайте свой вывод

---

Связанная часть спецификации языка:

4.3.3 объект

Объект представляет собой набор свойств и имеет один объект-прототип.

8.6.2. Внутренние свойства и методы объекта

Объекты массива имеют несколько иную реализацию внутреннего метода [[DefineOwnProperty]]. Объекты массива предоставляют особую обработку определенному классу имен свойств.