Eu tenho um modelo com possivelmente milhares de objetos. Eu queria saber qual seria a maneira mais eficiente de armazená-los e recuperar um único objeto, uma vez que eu tenha o seu ID. Os IDs são números longos.

Então, essas são as 2 opções que eu estava pensando. na opção um, é uma matriz simples com um índice incremental. na opção 2, é uma matriz associativa e talvez um objeto, se faz alguma diferença. Minha pergunta é qual deles é mais eficiente, quando eu geralmente preciso recuperar um único objeto, mas às vezes também os percorre e ordena.

Opção um com matriz não associativa:

var a = [{id: 29938, name: 'name1'},
         {id: 32994, name: 'name1'}];
function getObject(id) {
    for (var i=0; i < a.length; i++) {
        if (a[i].id == id) 
            return a[i];
    }
}

Opção dois com matriz associativa:

var a = [];  // maybe {} makes a difference?
a[29938] = {id: 29938, name: 'name1'};
a[32994] = {id: 32994, name: 'name1'};
function getObject(id) {
    return a[id];
}

Atualizar:

OK, acho que o uso de uma matriz na segunda opção está fora de questão. Portanto, a linha de declaração da segunda opção deve ser realmente:var a = {}; e a única questão é: o que tem um desempenho melhor na recuperação de um objeto com um determinado ID: uma matriz ou um objeto em que o ID é a chave.

e também, a resposta será alterada se tiver que classificar a lista várias vezes?

A versão curta: as matrizes são mais rápidas que os objetos. Mas não há solução 100% correta.

Atualização 2017 - Teste e resultados

var a1 = [{id: 29938, name: 'name1'}, {id: 32994, name: 'name1'}];

var a2 = [];
a2[29938] = {id: 29938, name: 'name1'};
a2[32994] = {id: 32994, name: 'name1'};

var o = {};
o['29938'] = {id: 29938, name: 'name1'};
o['32994'] = {id: 32994, name: 'name1'};

for (var f = 0; f < 2000; f++) {
    var newNo = Math.floor(Math.random()*60000+10000);
    if (!o[newNo.toString()]) o[newNo.toString()] = {id: newNo, name: 'test'};
    if (!a2[newNo]) a2[newNo] = {id: newNo, name: 'test' };
    a1.push({id: newNo, name: 'test'});
}

Post original - Explicação

Existem alguns conceitos errados na sua pergunta.

Não há matrizes associativas em Javascript. Somente matrizes e objetos.

Estas são matrizes:

var a1 = [1, 2, 3];
var a2 = ["a", "b", "c"];
var a3 = [];
a3[0] = "a";
a3[1] = "b";
a3[2] = "c";

Também é uma matriz:

var a3 = [];
a3[29938] = "a";
a3[32994] = "b";

É basicamente um array com buracos, porque todo array tem indexação contínua. É mais lento que as matrizes sem furos. Mas iterar manualmente através da matriz é ainda mais lento (principalmente).

Este é um objeto:

var a3 = {};
a3[29938] = "a";
a3[32994] = "b";

Aqui está um teste de desempenho de três possibilidades:

Matriz de pesquisa vs Matriz Holey x Teste de desempenho de objeto

Uma excelente leitura sobre esses tópicos na Smashing Magazine: Escrevendo JavaScript com eficiência de memória rápida

Não é realmente uma questão de desempenho, já que matrizes e objetos funcionam de maneira muito diferente (ou deveriam, pelo menos). As matrizes têm um índice contínuo 0..n, enquanto os objetos mapeiam chaves arbitrárias para valores arbitrários. Se você deseja fornecer chaves específicas, a única opção é um objeto. Se você não se importa com as chaves, é uma matriz.

Se você tentar definir chaves arbitrárias (numéricas) em uma matriz, você realmente terá uma perda de desempenho , pois, comportamentalmente, a matriz preencherá todos os índices intermediários:

> foo = [];
  []
> foo[100] = 'a';
  "a"
> foo
  [undefined, undefined, undefined, ..., "a"]

_{(Observe que a matriz, na verdade, não contém 99 undefinedvalores, mas se comportará dessa maneira, já que você deveria iterar a matriz em algum momento.)}

Os literais para ambas as opções devem deixar muito claro como eles podem ser usados:

var arr = ['foo', 'bar', 'baz'];     // no keys, not even the option for it
var obj = { foo : 'bar', baz : 42 }; // associative by its very nature

Com o ES6, a maneira mais eficiente seria usar um mapa.

var myMap = new Map();

myMap.set(1, 'myVal');
myMap.set(2, { catName: 'Meow', age: 3 });

myMap.get(1);
myMap.get(2);

Você pode usar os recursos do ES6 hoje usando um calço ( https://github.com/es-shims/es6-shim ).

O desempenho varia de acordo com o navegador e o cenário. Mas aqui está um exemplo em que o Mapdesempenho é mais alto: https://jsperf.com/es6-map-vs-object-properties/2

REFERÊNCIA https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

No NodeJS, se você souber ID, o loop pelo array é muito lento comparado a object[ID].

const uniqueString = require('unique-string');
const obj = {};
const arr = [];
var seeking;

//create data
for(var i=0;i<1000000;i++){
  var getUnique = `${uniqueString()}`;
  if(i===888555) seeking = getUnique;
  arr.push(getUnique);
  obj[getUnique] = true;
}

//retrieve item from array
console.time('arrTimer');
for(var x=0;x<arr.length;x++){
  if(arr[x]===seeking){
    console.log('Array result:');
    console.timeEnd('arrTimer');
    break;
  }
}

//retrieve item from object
console.time('objTimer');
var hasKey = !!obj[seeking];
console.log('Object result:');
console.timeEnd('objTimer');

E os resultados:

Array result:
arrTimer: 12.857ms
Object result:
objTimer: 0.051ms

Mesmo se o ID de busca for o primeiro na matriz / objeto:

Array result:
arrTimer: 2.975ms
Object result:
objTimer: 0.068ms

Tentei levar isso para a próxima dimensão, literalmente.

Dada uma matriz bidimensional, na qual os eixos xey são sempre do mesmo comprimento, é mais rápido:

a) procure a célula criando uma matriz bidimensional e procurando o primeiro índice, seguido pelo segundo índice, ou seja:

var arr=[][]    
var cell=[x][y]    

ou

b) crie um objeto com uma representação de string das coordenadas xey, e faça uma única pesquisa nesse objeto, ou seja:

var obj={}    
var cell = obj['x,y']    

Resultado:
verifica-se que é muito mais rápido fazer duas pesquisas de índice numérico nas matrizes do que uma pesquisa de propriedade no objeto.

Resultados aqui:

http://jsperf.com/arr-vs-obj-lookup-2

Depende do uso. Se o caso for objetos de pesquisa é muito mais rápido.

Aqui está um exemplo do Plunker para testar o desempenho de pesquisas de matriz e objeto.

https://plnkr.co/edit/n2expPWVmsdR3zmXvX4C?p=preview

Você verá isso; Procurando 5.000 itens na coleção de matriz de 5.000 comprimentos, ocupe 3000milissegundos

No entanto, procurar 5.000 itens no objeto tem 5.000 propriedades, apenas take 2ou 3milissegundos

Também criar árvore de objetos não faz muita diferença

Eu tive um problema semelhante que estou enfrentando, onde preciso armazenar candlesticks ao vivo de uma fonte de evento limitada a x itens. Eu poderia armazená-los em um objeto em que o carimbo de data e hora de cada vela atuaria como a chave e a própria vela atuaria como o valor. Outra possibilidade era que eu pudesse armazená-lo em uma matriz onde cada item fosse a própria vela. Um problema das velas ativas é que elas continuam enviando atualizações no mesmo registro de data e hora em que a atualização mais recente contém os dados mais recentes; portanto, você atualiza um item existente ou adiciona um novo. Então, aqui está uma boa referência que tenta combinar todas as três possibilidades. As matrizes na solução abaixo são pelo menos 4x mais rápidas, em média. Sinta-se livre para jogar

"use strict";

const EventEmitter = require("events");
let candleEmitter = new EventEmitter();

//Change this to set how fast the setInterval should run
const frequency = 1;

setInterval(() => {
    // Take the current timestamp and round it down to the nearest second
    let time = Math.floor(Date.now() / 1000) * 1000;
    let open = Math.random();
    let high = Math.random();
    let low = Math.random();
    let close = Math.random();
    let baseVolume = Math.random();
    let quoteVolume = Math.random();

    //Clear the console everytime before printing fresh values
    console.clear()

    candleEmitter.emit("candle", {
        symbol: "ABC:DEF",
        time: time,
        open: open,
        high: high,
        low: low,
        close: close,
        baseVolume: baseVolume,
        quoteVolume: quoteVolume
    });



}, frequency)

// Test 1 would involve storing the candle in an object
candleEmitter.on('candle', storeAsObject)

// Test 2 would involve storing the candle in an array
candleEmitter.on('candle', storeAsArray)

//Container for the object version of candles
let objectOhlc = {}

//Container for the array version of candles
let arrayOhlc = {}

//Store a max 30 candles and delete older ones
let limit = 30

function storeAsObject(candle) {

    //measure the start time in nanoseconds
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

    const { symbol, time } = candle;

    // Create the object structure to store the current symbol
    if (typeof objectOhlc[symbol] === 'undefined') objectOhlc[symbol] = {}

    // The timestamp of the latest candle is used as key with the pair to store this symbol
    objectOhlc[symbol][time] = candle;

    // Remove entries if we exceed the limit
    const keys = Object.keys(objectOhlc[symbol]);
    if (keys.length > limit) {
        for (let i = 0; i < (keys.length - limit); i++) {
            delete objectOhlc[symbol][keys[i]];
        }
    }

    //measure the end time in nano seocnds
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]

    console.log("Storing as objects", end - start, Object.keys(objectOhlc[symbol]).length)
}

function storeAsArray(candle) {

    //measure the start time in nanoseconds
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

    const { symbol, time } = candle;
    if (typeof arrayOhlc[symbol] === 'undefined') arrayOhlc[symbol] = []

    //Get the bunch of candles currently stored
    const candles = arrayOhlc[symbol];

    //Get the last candle if available
    const lastCandle = candles[candles.length - 1] || {};

    // Add a new entry for the newly arrived candle if it has a different timestamp from the latest one we storeds
    if (time !== lastCandle.time) {
        candles.push(candle);
    }

    //If our newly arrived candle has the same timestamp as the last stored candle, update the last stored candle
    else {
        candles[candles.length - 1] = candle
    }

    if (candles.length > limit) {
        candles.splice(0, candles.length - limit);
    }

    //measure the end time in nano seocnds
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]


    console.log("Storing as array", end - start, arrayOhlc[symbol].length)
}

Conclusão 10 é o limite aqui

Storing as objects 4183 nanoseconds 10
Storing as array 373 nanoseconds 10

Se você tiver uma matriz classificada, poderá fazer uma pesquisa binária e isso é muito mais rápido que uma pesquisa de objeto, pode ver a minha resposta aqui:
Como pesquisar mais rapidamente em uma matriz classificada usando Javascript