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

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

14 голосов
/ 04 октября 2010

Какое большое значение для доступа к массиву 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), но это точно?

Ответы [ 2 ]

13 голосов
/ 05 октября 2010

Синтаксически предполагается, что доступ к свойствам объекта и элементам массива в 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
8 голосов
/ 05 октября 2010

В первую очередь Массивы на самом деле хэши . Всегда .Вот почему x[5] === x["5"]: 

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

Объекты - это хеши, а массивы - просто специальные объекты. Если вы хотите использовать общие хеши, перейдите к объектам.«Ассоциативные массивы» в Javascript - это объекты.Массивы предназначены для численно проиндексированных данных.Массивы имеют свойство length и методы, подобные массиву, такие как push, pop, sort и т. Д., Которые не имеют смысла для использования с хэшами.

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

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

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

  2. Проведите тест для больших n и сделайте свой вывод

Соответствующая часть спецификации языка :

4.3.3 объект

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

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

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

...