Qual estrutura de dados para qual problema

A maioria dos materiais de estrutura de dados é organizada pela estrutura: aqui está a árvore, aqui está o heap, aqui estão as operações.

Isso é útil para estudar e inútil para decidir. Na prática, você tem um problema, não uma estrutura. Este artigo inverte a ordem.

"Preciso achar por chave exata, muito rápido"#

Hash table. Tempo constante para inserir, buscar e remover.

O custo: nenhuma ordem. Você perde faixa, ordenação, menor, maior, anterior e próximo.

E dois detalhes que aparecem em produção: quando a tabela enche, ela dobra e recalcula tudo, o que explica aquele pico esporádico de latência. E a qualidade da função de hash importa: hash ruim concentra colisões e degrada para tempo linear.

"Preciso de faixa, ordenação ou vizinhos"#

Árvore de busca balanceada. Logarítmico para tudo, e a ordem sai de graça.

AVL é mais rigidamente balanceada, melhor para leitura pesada. Rubro-negra é mais frouxa, com menos rotações na escrita: é o que a maioria das bibliotecas padrão usa.

Skip list é uma alternativa elegante: listas encadeadas em vários níveis, com balanceamento probabilístico. Desempenho parecido com a árvore, implementação bem mais simples, e mais fácil de fazer concorrente. É o que o Redis usa em sorted set.

E, no disco, a resposta é B+tree, pelos motivos do artigo anterior.

"Preciso sempre do menor (ou do maior)"#

Heap / fila de prioridade. Inserir e remover o extremo em tempo logarítmico; olhar o extremo em tempo constante.

Onde aparece: escalonador de tarefas, algoritmo de Dijkstra, "os N maiores" de um fluxo, timers de sistema.

Um detalhe útil: para manter os N maiores de um fluxo gigante, você usa um heap de tamanho N: memória constante, independente do tamanho do fluxo.

"Preciso de autocompletar ou prefixo"#

Trie, a árvore de prefixos. Cada nó é um caractere; caminhos compartilhados economizam espaço e busca por prefixo é natural.

O custo é memória, e é significativo. Variações comprimidas (radix tree, árvore PATRICIA) resolvem parte disso.

Onde aparece: autocompletar, roteamento de IP, dicionário de palavras.

"Preciso saber se já vi isso antes, com pouca memória"#

Bloom filter. Responde "definitivamente não" ou "talvez". Cerca de dez bits por elemento para um por cento de falso positivo.

O padrão mental: filtro barato antes da operação cara. Antes de ir ao disco, antes de chamar a API, antes de consultar o cache remoto.

Onde aparece: LSM-tree, CDN, verificação de URL maliciosa no navegador.

"Preciso contar coisas distintas em escala absurda"#

HyperLogLog. Estima cardinalidade (quantos valores únicos) com erro de cerca de dois por cento usando poucos kilobytes, independentemente de o conjunto ter mil ou um bilhão de elementos.

Contar visitantes únicos de forma exata exige guardar todos os identificadores. HyperLogLog troca precisão por memória, e para métrica de produto essa troca é quase sempre boa.

Count-Min Sketch é o primo: estima a frequência de cada item, também em espaço fixo. Serve para achar os itens mais frequentes de um fluxo: os produtos mais vistos, os IPs mais ativos.

Ambos superestimam e nunca subestimam, o que é uma propriedade útil de saber ao interpretar o número.

"Preciso comparar dois conjuntos grandes e achar a diferença"#

Merkle tree. Uma árvore de hashes, onde cada nó é o hash dos filhos. Comparando as raízes, você sabe se algo mudou. Descendo pelos ramos que divergem, você acha exatamente o quê, sem comparar tudo.

Onde aparece: sincronização entre réplicas em Cassandra e DynamoDB, Git, blockchain, sincronização de arquivos.

"Preciso de relacionamentos"#

Grafo, e a escolha da representação importa mais do que parece.

Lista de adjacência (cada nó guarda seus vizinhos): eficiente em memória para grafos esparsos, que é o caso quase sempre. É a escolha padrão.

Matriz de adjacência: consulta "existe aresta entre A e B" em tempo constante, e ocupa espaço quadrático. Só vale para grafos densos e pequenos.

"Preciso de fila de alta vazão entre threads"#

Ring buffer: um array circular de tamanho fixo. Sem alocação, sem lixo, e amigável ao cache do processador porque a memória é contígua.

Combinado com operações atômicas, permite fila sem lock. É a base do LMAX Disruptor, que processava milhões de mensagens por segundo numa única thread.

1. Hash tablechave exataTempo constante. O custo é perder toda ordem: faixa, ordenação, anterior e próximo.
2. Árvore balanceadafaixa e ordemLogarítmico para tudo, e a ordem sai de graça. No disco, vira B+tree.
3. Heapo extremoO menor ou o maior em tempo constante. Os N maiores de um fluxo cabem num heap de tamanho N.
4. TrieprefixoAutocompletar e roteamento de IP. O custo é memória, e é significativo.
5. Bloom filterjá vi isso?Definitivamente não, ou talvez. Filtro barato antes da operação cara.
6. HyperLogLogquantos únicosCardinalidade com erro de 2% em poucos kilobytes, seja mil ou um bilhão de elementos.
7. Merkle treeo que mudouCompara as raízes, desce só pelos ramos que divergem. É o Git e a sincronização de réplicas.

O que você já usa por baixo#

Vale perceber quanto disso já está no seu dia a dia:

→ O dicionário da sua linguagem é uma hash table.

→ O índice do seu banco é uma B+tree.

→ O sorted set do Redis é uma skip list.

→ O Git é uma árvore de Merkle com hashes de conteúdo.

→ O roteamento de IP é uma trie.

→ O escalonador do sistema operacional usa heap ou árvore.

→ O Cassandra usa LSM-tree com Bloom filter e Merkle tree.

Você não vai implementar quase nenhuma dessas. Mas conhecer os nomes muda a forma como você lê documentação, escolhe ferramenta e explica decisão.

A pergunta que resolve entrevista, e projeto#

Quando alguém pedir para você escolher uma estrutura, a resposta boa não começa pelo nome. Começa por três perguntas:

1. Quais operações são frequentes? Busca por chave, por faixa, inserção, remoção, "o maior"?

2. Cabe em memória, ou vai para o disco? Isso muda completamente o critério.

3. Preciso de resposta exata, ou uma aproximação resolve? Se aproximação resolve, as estruturas probabilísticas mudam a ordem de grandeza do custo.

Respondidas essas três, a estrutura quase se escolhe sozinha. E você demonstra a coisa que realmente importa: que sabe raciocinar sobre a troca, não só recitar o grande O.