Usando Hashmaps em JavaScript: Mapeando Chaves para Valores em Estruturas de Dados

O que são Hashmaps?

Hashmaps são uma estrutura de dados que armazena pares chave-valor, onde cada chave é única e mapeia para um valor. A chave é usada para indexar o valor, permitindo recuperação rápida do valor associado. Hashmaps usam uma função hash para calcular um índice para armazenar e recuperar valores. A função hash recebe a chave como entrada e gera um código hash único, que é então usado para determinar o índice onde o valor será armazenado no array ou bucket.

Hashmaps vs Objetos JavaScript

Objetos JavaScript também podem armazenar pares chave-valor, similar aos hashmaps. No entanto, hashmaps oferecem vantagens sobre objetos:

1. Tipos de Chave: Hashmaps permitem que qualquer tipo de dado seja usado como chave, incluindo objetos, arrays e funções. Objetos JavaScript são limitados a usar apenas strings e símbolos como chaves.

   const hashmap = new Map();
   hashmap.set({ name: 'John' }, 25);
   hashmap.set([1, 2, 3], 'array');
   
   const obj = {};
   obj[{ name: 'John' }] = 25; // Inválido: Objetos não podem ser usados como chaves em objetos

2. Manutenção da Ordem: Hashmaps mantêm a ordem de inserção dos elementos, o que significa que a ordem na qual os pares chave-valor são adicionados ao hashmap é preservada. Objetos JavaScript não garantem nenhuma ordem de suas propriedades.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   hashmap.set('c', 3);
   console.log(Array.from(hashmap.keys())); // Saída: ['a', 'b', 'c']
   
   const obj = { a: 1, b: 2, c: 3 };
   console.log(Object.keys(obj)); // Saída: ['a', 'b', 'c'] (Não garantido)

3. Rastreamento de Tamanho: Hashmaps fornecem métodos como size() para obter o número de elementos armazenados no hashmap. Com objetos JavaScript, você precisaria rastrear manualmente o número de propriedades ou usar Object.keys(obj).length para determinar o tamanho.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   console.log(hashmap.size); // Saída: 2
   
   const obj = { a: 1, b: 2 };
   console.log(Object.keys(obj).length); // Saída: 2

Complexidade de Tempo das Operações de Hashmap

Uma das principais vantagens dos hashmaps é sua complexidade de tempo para operações básicas. Hashmaps fornecem complexidade de tempo constante, denotada como O(1), para as seguintes operações:

1. Inserção: Adicionar um novo par chave-valor ao hashmap é uma operação O(1). A função hash é usada para calcular o índice, e o par chave-valor é armazenado nesse índice no array ou bucket.

2. Exclusão: Remover um par chave-valor do hashmap também é uma operação O(1). A função hash é usada para localizar o índice onde o par chave-valor está armazenado, e então ele é removido desse índice.

3. Busca: Recuperar o valor associado a uma chave específica é uma operação O(1). A função hash é usada para calcular o índice com base na chave, e o valor pode ser acessado nesse índice.

const cache = new Map();

function fetchData(key) {
  if (cache.has(key)) {
    return cache.get(key); // Recupera dados do cache (busca O(1))
  } else {
    const data = fetchFromAPI(key); // Busca dados da API
    cache.set(key, data); // Armazena dados no cache (inserção O(1))
    return data;
  }
}

Criando um Hashmap

Para criar um novo hashmap, use o construtor new Map(). Isso cria um hashmap vazio para armazenar pares chave-valor.

const myHashmap = new Map();

Por exemplo, para criar um hashmap para armazenar dados de estudantes:

const studentMap = new Map();

Adicionando Pares Chave-Valor

Para adicionar um novo par chave-valor ao hashmap, use o método set(). Ele recebe dois argumentos: a chave e o valor.

myHashmap.set('name', 'John');
myHashmap.set('age', 25);

No exemplo acima, adicionamos dois pares chave-valor ao myHashmap: 'name' mapeia para 'John' e 'age' mapeia para 25.

Vamos adicionar alguns dados de estudantes ao nosso studentMap:

studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

Obtendo Valores

Para obter o valor de uma chave específica, use o método get(). Ele recebe a chave como argumento e retorna o valor.

const name = myHashmap.get('name');
console.log(name); // Saída: 'John'

Neste exemplo, obtemos o valor para a chave 'name' do myHashmap, que é 'John'.

Para obter os dados de um estudante específico do studentMap:

const student = studentMap.get('2');
console.log(student); // Saída: { name: 'Alice', age: 22, major: 'Mathematics' }

Verificando a Existência de Chave

Para verificar se uma chave existe no hashmap, use o método has(). Ele recebe a chave como argumento e retorna um valor booleano.

const hasAge = myHashmap.has('age');
console.log(hasAge); // Saída: true

Aqui, verificamos se a chave 'age' existe no myHashmap usando o método has(), que retorna true.

Verificando se um estudante com ID '4' existe no studentMap:

const hasStudent = studentMap.has('4');
console.log(hasStudent); // Saída: false

Removendo Pares Chave-Valor

Para remover um par chave-valor do hashmap, use o método delete(). Ele recebe a chave como argumento e remove o par chave-valor do hashmap.

myHashmap.delete('age');
console.log(myHashmap.has('age')); // Saída: false

Neste exemplo, removemos o par chave-valor com a chave 'age' do myHashmap usando o método delete(). Após a remoção, has('age') retorna false.

Removendo um estudante do studentMap:

studentMap.delete('1');
console.log(studentMap.has('1')); // Saída: false

Obtendo o Tamanho do Hashmap

Para obter o número de pares chave-valor no hashmap, use a propriedade size. Ela retorna o tamanho do hashmap.

console.log(myHashmap.size); // Saída: 1

Aqui, acessamos a propriedade size do myHashmap, que retorna 1, indicando que há um par chave-valor no hashmap.

Obtendo o número de estudantes no studentMap:

console.log(studentMap.size); // Saída: 2

Resumo das Operações de Hashmap

Estas são as operações básicas que você pode fazer em um hashmap usando o objeto Map do JavaScript. O objeto Map fornece uma maneira de trabalhar com pares chave-valor e oferece métodos para manipular e acessar os dados no hashmap.

O objeto Map mantém a ordem dos pares chave-valor, o que significa que quando você itera sobre o hashmap usando métodos como forEach() ou o loop for...of, os pares chave-valor serão acessados na ordem em que foram adicionados.

O Método forEach()

O método forEach() é integrado ao objeto Map. Ele permite iterar sobre cada par chave-valor no hashmap. Ele usa uma função callback que é executada para cada par.

A função callback recebe três parâmetros:

1. value: O valor do par atual.
2. key: A chave do par atual.
3. map: O hashmap no qual forEach() foi chamado.

const shoppingCart = new Map();
shoppingCart.set('shirt', 25);
shoppingCart.set('pants', 50);
shoppingCart.set('shoes', 75);

let totalPrice = 0;

shoppingCart.forEach((price) => {
  totalPrice += price;
});

console.log(`Total Price: $${totalPrice}`);

Total Price: $150

O Loop for...of

Você também pode usar um loop for...of para iterar sobre um hashmap. O loop for...of funciona com objetos iteráveis como arrays, strings e maps.

Quando você usa for...of com um hashmap, cada loop retorna um array com o par [key, value].

Visualizando a Iteração de Hashmap

Aqui está um diagrama mostrando como funciona a iteração sobre um hashmap:

O diagrama mostra o hashmap e a iteração sobre cada par chave-valor. Para cada par, processamos com base no que precisamos fazer, como cálculos, comparações ou outras operações.

Tanto forEach() quanto for...of permitem iterar sobre os pares chave-valor de um hashmap em JavaScript. Qual usar depende de suas necessidades específicas. forEach() é bom quando você quer fazer algo para cada par, enquanto for...of é útil quando você precisa tanto das chaves quanto dos valores em cada loop.

Tenha em mente que a ordem de iteração em um hashmap é baseada na ordem em que os pares foram adicionados. O objeto Map do JavaScript mantém essa ordem.

Iterar sobre hashmaps é comum ao trabalhar com pares chave-valor, e JavaScript tem esses métodos para tornar isso mais fácil e rápido. Para mais informações sobre objetos Map e iteração, consulte a MDN Web Docs.

O que são Colisões?

Em um hashmap, colisões acontecem quando duas ou mais chaves geram hash para o mesmo índice. Isso significa que múltiplos pares chave-valor precisam ser armazenados na mesma posição no array ou bucket. Se não forem tratadas adequadamente, colisões podem levar à sobrescrita de dados ou recuperação lenta de valores.

Aqui está um exemplo de uma colisão em um hashmap:

Neste exemplo, tanto as chaves 'John' quanto 'Alice' geram hash para o mesmo índice (Índice 0), causando uma colisão.

Se as colisões não forem corrigidas, esses problemas podem acontecer:

1. Sobrescrita de Dados: Se um novo par chave-valor gera hash para omesmo índice de um par existente, o par existente pode ser sobrescrito, causando perda de dados.

2. Recuperação Lenta: Quando ocorrem colisões, encontrar valores se torna mais lento, pois o hashmap precisa fazer mais etapas para encontrar o valor correto entre os pares colididos.

Para corrigir esses problemas, hashmaps usam técnicas de tratamento de colisão.

Maneiras de Tratar Colisões

Existem duas maneiras principais de tratar colisões em hashmaps:

1. Encadeamento Separado

• Cada índice do array ou bucket do hashmap armazena uma lista encadeada de pares chave-valor.
• Quando uma colisão ocorre, o novo par chave-valor é adicionado à lista encadeada nesse índice.
• Encontrar um valor significa percorrer a lista encadeada no índice com hash para encontrar o par chave-valor desejado.

2. Endereçamento Aberto

• O endereçamento aberto não usa listas encadeadas para tratar colisões. Em vez disso, ele procura o próximo índice livre no array quando uma colisão ocorre.
• Existem diferentes maneiras de encontrar o próximo índice, como sondagem linear, sondagem quadrática e hash duplo.
• Quando uma colisão acontece, o hashmap usa a maneira de sondagem para encontrar o próximo slot vazio no array para armazenar o par chave-valor.

Melhores Práticas para Usar Hashmaps

1. Escolha uma boa função hash que reduza colisões e distribua chaves uniformemente.
2. Pense no número esperado de elementos e no desempenho desejado ao escolher o tamanho inicial do hashmap.
3. Esteja ciente de como as colisões podem afetar a velocidade das operações de hashmap, especialmente com muitas colisões.
4. Use encadeamento separado ou endereçamento aberto com base no que sua aplicação precisa, considerando aspectos como uso de memória e velocidade de recuperação.