JavaScript Map

O que é Map?

Map é uma estrutura de dados key-value (chave-valor) nativa do JavaScript que permite armazenar pares de dados de qualquer tipo como chave ou valor.

const map = new Map();
map.set('nome', 'João');
map.set(1, 'número um');
map.set(true, 'booleano');
map.set({id: 1}, 'objeto como chave');

Estrutura de Dados Interna

Map é implementada como uma Hash Table (Tabela Hash):

┌─────────────────────────────────────────────────────────────┐
│                    HASH TABLE                               │
├─────────────────────────────────────────────────────────────┤
│ Bucket 0: [key1, value1] -> [key4, value4]                 │
│ Bucket 1: [key2, value2]                                   │
│ Bucket 2: [key3, value3] -> [key5, value5]                 │
│ Bucket 3: empty                                            │
│ ...                                                        │
└─────────────────────────────────────────────────────────────┘

Como funciona internamente:

1. Hash Function: Converte a chave em um índice do array, ou seja, digamos que a chave e banana, ele converte essa chave em um numero especifico, usando algorimitos de hasheamento avancados.
2. Collision Handling: Usa chaining (encadeamento) para resolver colisões, isso significa que, as vezes quando uma chave e convertida em um indice, pode ser que esse indice conflite com um outro ja existente, oque o Map faz e em cada indice ao invez de ter apenas um valor, se tem um array, podendo armazenar mais de um valor por indice, a funcao .get do Map lida em encontrar dentro desse array qual o item certo, mas colisoes sao raras pois o algoritimo de Hash e bem avancado.
3. Dynamic Resizing: Redimensiona automaticamente quando necessário.

Big O

O que significa „amortizado“?

Amortizado é um termo técnico usado quando a complexidade de uma operação pode na verdade ter duas complexidades distintas, dependendo de dois cenários diferentes que podem ocorrer.

O que acontece no Map é que o tamanho in-memory (na memória) de um Map quando ele é iniciado é sempre 4, ou seja, 4 slots de memória são reservados para o Map. Nos 3 primeiros elementos que são adicionados ao Map, a operação tem complexidade O(1), mas no momento que o quarto elemento for adicionado, será necessário criar um novo espaço in-memory de tamanho 8, e mover todos os elementos atuais para o novo espaço, em uma função que se assemelharia a essa:

// Processo interno do redimensionamento:
function resize() {
    const oldTable = this.table;           // O(1)
    this.table = new Array(oldTable.length * 2); // O(1)
    this.size = 0;                         // O(1)

    // AQUI está o O(n)!
    for (const bucket of oldTable) {       // O(n)
        for (const [key, value] of bucket) {
            this.set(key, value);          // Rehash cada elemento
        }
    }
}

Apenas neste caso específico, a operação executada será O(n), mas como estes casos só vão acontecer cada vez que o Map tiver que duplicar seu tamanho, é dito que a complexidade foi „amortizada“ para um caso mais realista.

A sequência de redimensionamentos funciona assim:

• Inicialmente será a inserção do elemento número 4 que será O(n) (com n=4)
• Depois esse número vai aumentar exponencialmente: a segunda vez será a inserção do elemento número 8 que será O(n) (com n=8)
• Depois a inserção do elemento 16, depois a 32, depois a 64, depois a 128, e assim por diante

Chegando em um ponto que a operação O(n) ficará tão distante uma da outra que pode ser desconsiderada em casos reais de uso. Por exemplo, se você tem um Map com 1 milhão de elementos, o próximo redimensionamento só acontecerá quando chegar a 2 milhões de elementos – uma distância muito grande entre as operações custosas.

Por isso a complexidade é chamada de „amortizada“: na média, considerando uma sequência longa de operações, o custo das operações caras (redimensionamento) é distribuído entre as operações baratas (inserções normais), resultando em uma complexidade média de O(1) por operação.

Map vs Object vs Array

Exemplos Práticos

1. Criação e Operações Básicas

const map = new Map();

// Adicionar
map.set('nome', 'Maria');
map.set(1, 'primeiro');
map.set(true, 'verdadeiro');

// Buscar
console.log(map.get('nome')); // "Maria"
console.log(map.get(1));      // "primeiro"

// Verificar existência
console.log(map.has('nome')); // true
console.log(map.has('age'));  // false

// Tamanho
console.log(map.size); // 3

// Remover
map.delete('nome');
console.log(map.size); // 2

2. Chaves de Qualquer Tipo

const map = new Map();

// Objetos como chaves
const obj1 = {id: 1};
const obj2 = {id: 2};

map.set(obj1, 'primeiro objeto');
map.set(obj2, 'segundo objeto');

console.log(map.get(obj1)); // "primeiro objeto"
console.log(map.get({id: 1})); // undefined (diferente objeto!)

3. Iteração

const map = new Map([
    ['a', 1],
    ['b', 2],
    ['c', 3]
]);

// Iterar chaves
for (const key of map.keys()) {
    console.log(key); // 'a', 'b', 'c'
}

// Iterar valores
for (const value of map.values()) {
    console.log(value); // 1, 2, 3
}

// Iterar pares
for (const [key, value] of map.entries()) {
    console.log(key, value); // 'a' 1, 'b' 2, 'c' 3
}

// forEach
map.forEach((value, key) => {
    console.log(key, value);
});

4. Inicialização com Array

const map = new Map([
    ['key1', 'value1'],
    ['key2', 'value2'],
    ['key3', 'value3']
]);

// Converter Map para Array
const array = Array.from(map);
console.log(array); // [['key1', 'value1'], ['key2', 'value2'], ['key3', 'value3']]

Quando Usar Map?

✅ Use Map quando:

• Precisa de chaves que não são strings
• Precisa saber o tamanho frequentemente
• Precisa iterar em ordem de inserção
• Precisa de performance O(1) garantida
• Chaves são dinâmicas/desconhecidas

❌ Use Object quando:

• Chaves são sempre strings
• Precisa de sintaxe mais simples
• Precisa de serialização JSON
• Tem métodos/propriedades específicas

Exemplo Prático: Contagem de Caracteres

function countChars(str) {
    const map = new Map();

    for (const char of str) {
        if (map.has(char)) {
            map.set(char, map.get(char) + 1);
        } else {
            map.set(char, 1);
        }
    }

    return map;
}

const result = countChars("hello world");
console.log(result);
// Map { 'h' => 1, 'e' => 1, 'l' => 3, 'o' => 2, ' ' => 1, 'w' => 1, 'r' => 1, 'd' => 1 }

Métodos Úteis

const map = new Map();

// Operações básicas
map.set(key, value);  // Adiciona/atualiza
map.get(key);         // Obtém valor
map.has(key);         // Verifica existência
map.delete(key);      // Remove
map.clear();          // Remove todos
map.size;             // Tamanho

// Iteração
map.keys();           // Iterator das chaves
map.values();         // Iterator dos valores
map.entries();        // Iterator dos pares [key, value]
map.forEach(callback); // Itera com callback

Map é a estrutura perfeita para casos que precisam de mapeamento chave-valor com performance O(1) e flexibilidade de tipos!