Em programação, um dicionário (também chamado de mapa ou hashmap) é uma estrutura de dados que armazena dados em pares de chave-valor, onde as chaves são usadas para acessar os valores. É como uma lista onde os elementos são acessados por nomes (chaves) em vez de índices numéricos.
Como funciona internamente
As chaves do dicionário são usadas como índices para localizar o valor associado. Ao invés de percorrer a coleção inteira para encontrar um valor, o dicionário usa a chave para calcular um índice na tabela hash.
Essa chave é passada para uma função hash, que gera um valor numérico (o índice na tabela hash). Para exemplificar, vamos armazenar o valor do quilograma de cada fruta dentro do dicionário.
Tabela hash:
Implementado um dicionário
Em JavaScript, o objeto Map armazena pares chave-valor preservando a ordem de inserção e aceita qualquer tipo como chave. Apesar disso, objetos comuns ainda são amplamente usados para operações básicas (definir, acessar, remover e verificar chaves) por serem mais simples e diretos. Esse é motivo pelo qual são a principal escolha antes do Map. Contudo, iremos utilizar o Map no nosso exemplo:
/**
* The Map object provides a more robust and flexible way to handle dictionaries.
*/
const dictionary = new Map<string, number>();
// Adding key-value pairs
dictionary.set('apple', 7.78);
dictionary.set('banana', 8.99);
dictionary.set('cherry', 17.05);
// Accessing values
console.log(dictionary.get('banana')); // Output: 8.99
// Checking if a key exists
console.log(dictionary.has('apple')); // Output: true
// Deleting a key-value pair
dictionary.delete('banana');
console.log(dictionary); // Output: Map(2) { 'apple' => 7.78, 'cherry' => 17.05 }
// Iterating over the map
dictionary.forEach((value, key) => {
console.log(key, value);
});
// Output:
// apple 7.78
// cherry 17.05
Quais as vantagens de usar um dicionário?
Podemos destacar duas principais vantagens.
1. Rapidez
Buscar, adicionar ou remover um item normalmente leva tempo O(1), sendo praticamente instantâneo, não importa quantos elementos existam.
2. Chaves exclusivas
Cada chave pode apontar para um único valor. Ao tentar inserir a mesma chave novamente, o valor antigo é simplesmente substituído, evitando repetições sem esforço extra.
Quais as desvantagens de usar um dicionário?
Podemos destacar três principais desvantagens.
1. Sem ordem garantida
A função de hash espalha as chaves “ao acaso”, então você não consegue percorrer os elementos em ordem alfabética ou numérica sem antes copiá‑los e ordenar.
2. Maior consumo de memória
Os elementos ficam dispersos na memória, ocupando um espaço maior do que o necessário, reservado para novos itens. Se esse espaço reservado estiver quase cheio, será necessário um redimensionamento, que é um processo custoso.
3. Colisões de chaves
Às vezes duas chaves diferentes produzem o mesmo índice na função hash. Quando isso acontece ocorre uma colisão. Para corrigir isso, geralmente a estrutura precisa de trabalho extra, o que pode degradar o desempenho se ocorrer com frequência.
Uma forma otimizada de lidar com colisões
Para evitar que um item seja sobrescrito numa colisão, há várias alternativas. A mais simples é: se diversas chaves mapeiam para o mesmo espaço, inicie uma lista encadeada neste espaço. No exemplo abaixo, houve uma colisão com o índice da chave “apple” ao tentar inserir a chave “plum” . Então iniciamos uma lista encadeada nesse índice da tabela hash, conservando seus pares chave-valor.
Bônus: Como calcular o fator de carga?
O fator de carga de uma tabela é simples de calcular.
Quanto menor o fator de carga, menores as chances de colisões e melhor o desempenho da estrutura.
Inserir elementos em uma tabela hash quase cheia exige redimensionamento, um processo custoso que envolve recriar a tabela com o dobro do tamanho, muitas vezes, e reinserir todos os itens usando a função hash. Uma boa prática é redimensionar quando o fator de carga ultrapassa 0,7.
Conclusão
O Dicionário (ou Hash Map) é uma estrutura eficiente para inserção, busca e remoção rápidas, sendo ideal para associar chaves a valores. No entanto, seu bom desempenho depende de uma função hash adequada e do controle do fator de carga para evitar colisões e redimensionamentos. Com esses cuidados, é uma ferramenta poderosa e versátil para diversas aplicações.
Top comments (0)