Escolhendo uma estrutura de dados

Entre 1023 chaves, uma busca linear por uma chave ausente faz 1023 comparações, a busca binária faz 10, e uma tabela hash com 1023 baldes fez no máximo 6 no laboratório.

Comece pelas perguntas que você vai fazer

Nenhuma estrutura é a melhor em tudo. Cada uma deixa algumas operações baratas tornando outras caras, então o jeito de escolher é listar o que o seu programa vai fazer com mais frequência. O 6.006 do MIT divide as possibilidades em duas interfaces. Uma sequência guarda os itens numa ordem que você decide (primeiro, segundo, terceiro), e você pede os itens pela posição. Um conjunto (set) guarda os itens por chave, e você pergunta se uma chave está lá, ou qual é a menor chave, ou a próxima depois de uma chave dada. Um conjunto sem as perguntas de ordem se chama dicionário.

Algumas situações comuns e a resposta de costume:

• Ler itens pela posição, acrescentar no fim: um array dinâmico (um array de JavaScript).
• Histórico de desfazer, parênteses que combinam, busca em profundidade: uma pilha, que é um array usado só no fim.
• Trabalhos tratados na ordem de chegada, busca em largura: uma fila, com índice head ou buffer circular em vez de shift num array comprido.
• Procurar coisas por nome ou id: uma tabela hash, que em JavaScript quer dizer Map ou Set.
• Manter chaves ordenadas enquanto insere e apaga, pedir a próxima chave: uma árvore binária de busca balanceada.
• Muitas inserções e remoções num ponto que você já tem nas mãos: uma lista encadeada.

A mesma busca em cinco estruturas

O laboratório abaixo guarda as mesmas chaves de cinco jeitos e conta as comparações necessárias para achar uma delas. As chaves são 15, 127 ou 1023 números inteiros aleatórios. O array desordenado usa busca linear. O array ordenado usa busca binária. A árvore balanceada foi construída inserindo primeiro as chaves do meio, então é a mais baixa possível. A outra árvore foi construída com as chaves em ordem crescente, então é uma cadeia. A tabela hash tem tantos baldes quanto chaves e conta 1 para calcular h(k).

Com 15 chaves as diferenças são pequenas: a busca linear precisa de 8 comparações em média e a busca binária de cerca de 3.3. Com 1023 chaves, não. A busca linear tem média de 512 e precisa de 1023 para uma chave ausente, enquanto a busca binária e a árvore balanceada nunca precisam de mais de 10. A árvore em cadeia é tão ruim quanto a busca linear. A tabela hash fica entre 2.3 e 2.5 em média em todos os tamanhos, porque as cadeias dela continuam curtas, e neste laboratório o pior caso dela com 1023 chaves foi 6. É por isso que o Map é a escolha padrão para buscas, e por isso as estruturas ordenadas só compensam quando você também precisa de ordem.

Cada célula destas duas tabelas é a taxa de crescimento do custo para n itens, seguindo as tabelas das notas de aula 2, 4 e 7 do MIT. Tabelas hash e árvores de busca só aparecem na segunda tabela porque trabalham por chave, não por posição. Num array desordenado ou numa lista, inserir uma chave custa n porque é preciso primeiro conferir se ela já não está lá. O array ordenado acha rápido, mas precisa mover valores para abrir espaço para uma chave nova.

Map ou objeto?

Programas em JavaScript muitas vezes usam um objeto comum como dicionário, escrevendo prices["apple"]. O MDN lista motivos para preferir o Map quando as chaves vêm dos dados: um objeto tem um protótipo, então contém chaves padrão que podem colidir com as suas; um Map pode usar qualquer valor como chave, não só strings e símbolos; o tamanho dele é uma propriedade só, map.size; e ele é percorrido na ordem de inserção. Os objetos continuam sendo a escolha natural para registros com um conjunto fixo de campos com nome.