Estágio 01 · 01-04
LockedEstrutura de dados é como você organiza dados na memória pra otimizar as operações que você vai fazer mais. Escolher errado significa código N vezes mais lento do que o necessário, ou usando N vezes mais memória, ou ambos.
Exemplos onde desconhecimento custa caro:
Array.includes() num array de 100k items pra verificar duplicatas, O(n) por verificação, O(n²) total. Com Set, vira O(1) e O(n).sort() ordenando 1M items (O(n log n)) quando um min-heap de tamanho 10 resolve em O(n log 10).Array.shift() pra implementar fila e a aplicação fica lenta, shift é O(n) (desloca todos elementos). Use linked list (deque) ou índice circular.E quando você for estudar Postgres (02-09), B-Trees são índice. Quando estudar Redis (02-11), Skip Lists são sorted sets. Quando estudar Kafka (04-02), particionamento usa hashing consistente. Estruturas de dados estão em todo lugar do stack moderno.
Big-O mede crescimento assintótico. O(n) significa "tempo cresce proporcional a n quando n é grande".
Hierarquia comum:
O(1), constante (hash lookup)O(log n), logarítmico (busca binária, B-Tree)O(n), linearO(n log n), quase linear (sorting comparativo)O(n²), quadrático (nested loops)O(2ⁿ), O(n!), exponencial (sem solução pra n grande)Big-O esconde:
Amortizado vs pior caso: dynamic array push é O(1) amortizado (média), mas O(n) no pior caso (quando precisa realocar). Hash table insert é O(1) amortizado, O(n) no rehash.
Layout: sequência contígua de células do mesmo tipo na memória.
| Operação | Complexidade |
|---|---|
| Acesso por índice | O(1) |
| Append (com capacidade) | O(1) amortizado |
| Append (cheio, realoca) | O(n), copia todos |
| Insert no meio | O(n), desloca |
| Delete no meio | O(n), desloca |
| Busca linear | O(n) |
| Busca binária (ordenado) | O(log n) |
Em JS: Array é heterogêneo (pode misturar tipos), com otimizações do V8 quando consistente. TypedArray (Float64Array, Uint8Array, etc) é homogêneo, contíguo, próximo a array C.
Cache locality: array é o rei disso. Iteração linear ativa prefetcher.
Capacity vs length: dynamic array (vector em C++) tem capacidade interna ≥ length. Cresce dobrando (geometric growth) pra manter append O(1) amortizado.
Layout: nós alocados separadamente, ligados por ponteiros.
[1|*]→[2|*]→[3|*]→[4|null]
| Operação | Complexidade |
|---|---|
| Acesso por índice | O(n) |
| Insert no início | O(1) |
| Insert no fim (com tail) | O(1) |
| Insert/delete no meio (com ref) | O(1) |
| Busca | O(n) |
Cache locality: horrível. Cada next é potencialmente cache miss. Em prática, linked list pode ser 10-50x mais lento que array contíguo pra iteração, mesmo Big-O igual.
Quando usar: raramente. Casos legítimos:
Doubly linked list: nó tem prev e next. Permite insert/delete em O(1) com ref bidirecional. Usado em LRU caches.
Idéia: computar um hash da chave que mapeia para um slot no array interno.
hash("foo") % 8 = 3 → slot 3 = [("foo", value)]
Colisões acontecem (dois keys hashearem pro mesmo slot). Resolução:
Load factor (α): elementos / slots. Acima de ~0.7, performance degrada → rehash (cresce a tabela, redistribui).
Complexidade média: O(1) insert/lookup/delete. Pior caso: O(n) se hash function ruim (todos no mesmo slot) ou ataque DoS por colisão deliberada.
Em JS:
Object é hash-like, mas com behaviors especiais (prototype chain, string keys only).Map é hash table proper. Aceita qualquer key (incluindo objects). Use Map quando key é dinâmica.Set é hash set.No V8: Object com shape estável vira hidden class (otimizado, virtually struct). Adicionar/remover propriedades em runtime quebra otimização.
Estrutura hierárquica: nó com filhos.
Terminologia:
Cada nó tem left (menor) e right (maior).
| Operação | Médio | Pior caso |
|---|---|---|
| Insert | O(log n) | O(n) (degenera em lista) |
| Search | O(log n) | O(n) |
Pior caso: insert em ordem (1, 2, 3, 4, 5...) cria lista. Por isso usamos BSTs balanceadas.
BST auto-balanceada. Cada insert/delete pode disparar rotação pra manter |height(left) - height(right)| ≤ 1. Garante O(log n) pior caso. Strict balance → mais rotações que outros.
BST balanceada com regras de cor (cada nó é vermelho ou preto). Menos estrita que AVL, menos rotações em escrita, ligeiramente mais profunda. Usada em: Linux kernel CFS scheduler, Java TreeMap, C++ std::map.
Generalização de BST: cada nó tem muitos filhos (centenas). Otimizada pra storage em disco/cache: cada nó cabe numa page (4-8 KB). Reduz altura → reduz número de I/Os.
[10 | 20 | 30]
/ | | \
[...] [11..19] [21..29] [31..]
Operações: insert/search/delete em O(log n), mas com base muito alta (ex: B-Tree de ordem 100 com 1M elementos tem altura ~3, só 3 page reads).
B+ Tree (variação): só leaves armazenam dados; internos só keys de roteamento. Leaves linkadas em lista pra range scans.
Usadas em: Postgres índices (B-Tree), MySQL InnoDB, file systems (ext4, NTFS, ZFS), key-value stores.
Tree onde cada nó representa um caractere. Caminhos = strings. Bom pra autocomplete, dicionários.
root
/ | \
a b c
| | |
p a a
| | |
e r r ...
Binary heap: árvore quase-completa com heap property:
Implementação: array. Para nó no índice i:
2i+12i+2(i-1)/2| Operação | Complexidade |
|---|---|
| Peek (top) | O(1) |
| Insert (push) | O(log n) |
| Extract (pop) | O(log n) |
| Build from array | O(n) |
Uso clássico: Dijkstra (priority by distância), top-K, scheduling (run queue do CFS interno).
Conjunto de nós (vértices) e arestas. Pode ser dirigido ou não, ponderado ou não.
Representações:
vertices: { A: [B, C], B: [D], ... }. Espaço O(V + E). Bom pra grafos esparsos.[(A,B), (B,C), ...]. Compacta, ruim pra queries.Algoritmos clássicos vivem aqui (BFS, DFS, Dijkstra, A*), ver 01-05.
Em produção web: grafos sociais (Facebook, LinkedIn), grafo de routing (Google Maps, sistema de logística!), grafo de dependências (npm), grafo de conhecimento (Google).
PFCOUNT.Trade-off de fan-out: B-Tree com page de 8KB e key 16 bytes tem fan-out ~500. Árvore com 1B keys precisa só ~4 níveis (log_500(10^9) ≈ 3.4). Cada lookup = 4 page reads. Por isso indices crescem devagar em altura.
Estruturas funcionais onde "modificar" cria nova versão sem destruir antiga. Estrutura compartilha sub-árvores via path copying.
Quando importam:
Custo: alocação de novo nodes a cada mutation. GC pressure. Em hot paths, mutável vence.
Algoritmos cache-aware conhecem tamanho da cache; cache-oblivious são ótimos sob qualquer hierarchy de cache (L1, L2, L3, DRAM).
Conexão com 01-14 (CPU microarch): cache miss custa 100-300 ciclos. Layout matters.
Probabilística. Cada node tem N levels com probabilidade p^N (típico p=0.5). Average O(log n) operations.
L4: [1]→[10]
L3: [1]→[5]→[10]→[15]
L2: [1]→[3]→[5]→[7]→[10]→[15]→[20]
L1: [1]→[2]→[3]→[4]→[5]→[6]→[7]→[8]→[10]→...
Search desce levels: começa em L4, avança até overshoot, desce. Insert sorteia level máximo.
Vantagens vs B-Tree: implementação simples (~50 linhas), sem rebalanço explicit, lock-free variants existem. Desvantagens: pior cache locality que B-Tree, overhead per node maior.
Uso: Redis sorted set (ZSET), LevelDB MemTable, Cassandra MemTable, RocksDB MemTable.
Estrutura: trie com fan-out 32, indexed por bits do hash da key.
Result: insert/get/delete O(log32 n) ≈ O(1) (max depth ~6 pra 32B keys).
Implementations:
PersistentHashMap.immutable.HashMap.Map (BEAM internal HAMT).im crate (Rust).Log-Structured Merge Tree é o oposto de B-Tree: write-optimized.
Components:
Levels:
Trade-off:
Used em: RocksDB (default em CockroachDB, TiKV, etcd 3+), Cassandra, ScyllaDB, LevelDB, HBase.
vs B-Tree (Postgres):
m bits, k hash functions, n elements inserted. False positive rate:
FPR ≈ (1 - e^(-kn/m))^k
Optimal k pra m, n: k = (m/n) * ln(2).
Exemplo: 10M elements, FPR target 1%. Necessário m ≈ 9.6 * n = ~96M bits = ~12MB. k ≈ 7.
Counting Bloom Filter: bytes em vez de bits. Permite delete (decrement counter). 4-8x mais espaço.
Cuckoo Filter: alternativa moderna, suporta delete, lower FPR mesma memória, usa cuckoo hashing.
Uso: Cassandra (key existence), CDN (negative cache), Chrome safe browsing, Bitcoin SPV clients (limitado a 2018).
Pra grafo G(V, E):
adj[u] = [v, w, ...]. Memory O(V+E). Iteration por vizinhos O(deg(v)).m[u][v] = 1 se edge. Memory O(V²). Lookup O(1). Bom em grafo denso.indices (vizinhos concat) + indptr (offsets). Memory O(V+E), cache-friendly. Padrão em libs científicas (SciPy sparse, GraphBLAS).Pra grafos dispersos (E << V²): list ou CSR. Pra densos (E ≈ V²): matrix. Pra graph algorithms heavy (PageRank em GPU): CSR + GPU primitives.
Trie (prefix tree): cada node representa caractere; path = prefix.
Variantes:
Memory: trie naive é heavy (1 node per char per word). Compressed e FST mitigam.
Estrutura de equivalence classes.
find(x): representante da classe.union(x, y): une duas classes.Otimizações:
Com ambas: amortized O(α(n)) ≈ O(1) per operation (α = inverse Ackermann).
Uso: Kruskal MST, connected components, image segmentation, percolation.
Pra passar o Portão Conceitual, sem consultar:
Implementar uma LRUCache thread-unsafe em TypeScript do zero.
class LRUCache<K, V> com:
constructor(capacity: number)get(key: K): V | undefined, O(1). Marca como recém-usado.set(key: K, value: V): void, O(1). Se cheio, remove o least-recently-used.has(key: K): boolean, O(1).size: number, getter.clear(): voidSymbol.iterator) percorrendo do mais recente ao menos.Map do JS (que tem ordering garantido), você implementa o ordering.get('foo') quando foo está no meio da lista, quais ponteiros são atualizados.Map interno (e não objeto plain)?set(key, value, ttlMs)).Map, Set, WeakMap, WeakRef, hidden classes.src/dict.c (hash table), src/t_zset.c (skip list), src/quicklist.c, src/intset.c.Encerramento: após 01-04, escolha de estrutura deixa de ser intuição e vira raciocínio. Você nunca mais vai usar Array.shift pra implementar fila.
Destrava
01-04 é prereq dos seguintes módulos: