Entendendo o mapa em JavaScript (a estrutura de dados subestimada)

O mapa do JavaScript é frequentemente ofuscado pelo objeto, mas para muitos casos de uso de valor -chave, é a melhor ferramenta – mais agressiva, mais segura e mais flexível. Este artigo passa pelo que é um mapa, como ele funciona sob o capô (hash, baldes, colisões), por que as operações geralmente são O (1), quando não são e quando escolher o mapa em vez de objeto. O que é um mapa? Em termos simples: o MAP é uma estrutura de dados de valor -chave (uma tabela de hash). Você armazena um valor em uma chave e depois a recupere usando a mesma chave. Ao contrário dos objetos simples, o MAP permite qualquer tipo de chave (strings, números, objetos, funções) e fornece iteração previsível, tamanho interno e métodos adaptados para o comportamento do dicionário. Um exemplo rápido (e um erro comum) // ❌ Erro comum: usando objeto como um mapa, deixe players = {user_1: {name: ‘shubham’, pontuação: 120},}; // Isso será lançado: Players.Set não é uma função players.set (‘user_2’, {name: ‘atharva’, pontuação: 200}); // ✅ correto: use o mapa para armazenamento de chave -value const playersmap = new map (); playersmap.set (‘user_1’, {name: ‘shubham’, pontuação: 120}); playersmap.set (‘user_2’, {name: ‘atharva’, pontuação: 200}); console.log (playersmap.get (‘user_1’)); // {name: ‘shubham’, pontuação: 120} console.log (playersmap.has (‘user_2’)); // True Console.log (Playersmap.size); // 2 Digite a complexidade do tempo da tela cheia do modo de tela cheia – é sempre O (1)? A intuição diz: “Os mapas de hash são O (1), certo?” Geralmente, sim-mas a resposta completa deve incluir os melhores e os piores casos: melhor/médio de caso: o (1) para obter, definir, excluir, excluir o pior caso: o (n) Quando muitas chaves colidem com o mesmo balde moderno dos motores JS usam hash de alta qualidade + redimensionando para manter o caso médio muito próximo de O (1) em prática. Como o mapa funciona internamente? (Hashing, baldes, colisões) Vamos quebrá -lo passo a passo. 1) HASHING A CHAVE quando você faz: Playersmap.Set (‘User_2’, {Nome: ‘Atharva’, Score: 200}); Digite o modo de saída do modo de tela cheia. Exemplo: ‘user_2’ → 738492 (Finque o valor do hash). 2) Encontrando o balde as escolhas de hash que balde (slot em uma matriz interna) para usar: bucketIndex = hash % tablelize digite o modo de tela cheia Sair Modo de tela cheia Exemplo: 738492 % 1000 = 492 → Armazenar no bucket 492 Enter o modo de tela cheia de tela completa. 3) LIDAMENTO DE COLIÇÕES Duas teclas diferentes podem produzir o mesmo índice de balde → A Collision.Common Strategies: Chazing: Armazene várias entradas em uma pequena lista (lista ou matriz vinculada) dentro do balde. Endereço aberto: Se um balde estiver cheio, a sonda para encontrar outro slot vazio. 4) recuperar um valor quando o fizer: playersmap.get (‘user_1’); Digite o modo de tela cheia de saída de tela cheia hash ‘user_1’ novamente. Salte para o balde calculado. Pesquise as entradas do balde para obter uma correspondência de chave exata (===). Retornar o valor armazenado. Tempo médio: o (1) o pior caso: o (n) Se a cadeia de um balde se tornar muito longa, por que as colisões acontecem? Porque mapeamos infinitamente muitas chaves possíveis para um número finito de baldes. Algumas idéias -chave ajudam a razão sobre colisões: 1) fator de carga (α) α = n / m Entre no modo de tela cheia Modo de tela cheia n = Número de entradas m = número de baldes Se α crescer muito grande, o comprimento médio da balde cresce → mais colisões → pesquisas mais lentas. Exemplo: suponha que uma tabela tenha m = 6 baldes e inserimos n = 8 entradas: const playersmap = novo mapa ([
[‘USER_1’, { score: 120 }]Assim,
[‘USER_2’, { score: 210 }]Assim,
[‘USER_3’, { score: 100 }]Assim,
[‘USER_4’, { score: 220 }]Assim,
[‘USER_5’, { score: 140 }]Assim,
[‘USER_6’, { score: 200 }]Assim,
[‘USER_7’, { score: 130 }]Assim,
[‘USER_8’, { score: 180 }],]); Digite o modo de saída do modo de tela cheia aqui α = 8/6 ≈ 1,33. Pelo princípio do pombo, pelo menos um balde deve conter mais de 2 entradas. Para manter o α saudável, os motores redimensionam (rehash) quando um limiar é excedido (geralmente em torno de 0,7-0,8). 2) As colisões de efeito paradoxo de aniversário ocorrem mais cedo do que a intuição espera. Assim como 23 pessoas são suficientes para uma chance de 50% de um aniversário compartilhado (com 365 “baldes”), as colisões nas tabelas de hash também começam a aparecer em N surpreendentemente baixo N em relação a m. Quanto tempo a “Mini List” de um balde pode obter? O pior caso teórico: todas as N Keys aterrissam em um balde → que o comprimento da corrente do balde é n (as pesquisas se degradam para O (n)). Caso esperado: em torno do fator de carga α por balde. Na prática: os motores mantêm α baixo por meio da reformulação. Alguns idiomas (como o hashmap de Java) Trereify Long Chains (por exemplo, além do comprimento 8) em árvores equilibradas para limitar a pesquisa em O (log n). Os motores JS normalmente dependem de redimensionamento e estratégias internas – os detalhes não são expostos -, mas o objetivo é o mesmo: mantenha as pesquisas perto de O (1). Replantação (redimensionamento) – O que, por que, quando? O que é isso? Reconstruindo a mesa com mais baldes e reinserção de todas as entradas existentes. Por que? Reduzir colisões e manter o desempenho próximo (1) à medida que o número de entradas cresce. Quando? Quando o limite do fator de carga é excedido (por exemplo, α> ~ 0,75). Isso é automático no mapa JS – você não o aciona manualmente. Como funciona (alto nível): aloque uma matriz maior (geralmente ~ 2 ×). Recomputar BucketIndex = Hash % NewTablesize para cada chave. Insira cada entrada em seu novo balde. Troque na nova tabela. A reformulação é cara no momento, mas acontece com pouca frequência. Espalhados por muitas operações, as inserções permanecem amortizadas o (1). Mapa vs Objeto – Quando usar qual? Recurso Tipos de chave do objeto de mapa de características qualquer (string, número, objeto, função, etc.) String/símbolo somente a ordem da ordem de inserção garantida para as teclas de string é preservada principalmente nos motores modernos, mas a semântica é mapa de tamanho focada em objetos. Use os operadores/utilitários colisões de protótipos nenhuma (sem teclas de protótipo) é possível (por exemplo, toString, a menos que proteger) o desempenho para inserções/exclusão dinâmica geralmente melhor não otimizada como um mapa de hash json. Chaves sem cordas, ordem de iteração ou tamanho. Use o objeto para modelos de dados estruturados que devem ser serializados para JSON ou ao trabalhar com APIs que esperam objetos simples. As dicas extras e as teclas GOTCHAS são sensíveis à caixa: ‘user_1’ e ‘user_1’ são diferentes. No mapa, as chaves 1 e ‘1’ são diferentes (assuntos do tipo). Você pode usar objetos como chaves: const m = new map (); const user = {id: ‘user_1’}; m.set (usuário, {pontuação: 120}); console.log (m.get (usuário)); // {Score: 120} Digite o modo de saída de tela cheia para a tela cheia para JSON-Serialize um mapa, converta-o: const json = json.stringify (object.FromEntries (playersmap)); Digite o modo de saída do modo de tela cheia TL de tela cheia tl; dr (resumo) O mapa é um armazenamento de chave-chave baseado na mesa de hash com operações Near-O (1). As colisões são inevitáveis (baldes finitos, chaves infinitas), mas mantidas raras por meio de boas hash e reformulação. As pesquisas de piores casos são O (n), mas o desempenho amortizado permanece excelente. Prefira o mapa sobre o objeto para cargas de trabalho do tipo dicionário; Prefira o objeto para dados estruturados do tipo JSON. Feliz mapeamento! ✨

Fonte