Fundamentos de Tabelas Hash

Tabelas hash são estruturas de dados primariamente utilizadas para verificar rapidamente a existência de um elemento em uma coleção. O princípio envolve uma função hash que mapeia um dado (como um nome de aluno) a um índice em uma tabela. Consultar esse índice permite determinar de forma ágil se o dado está presente.

Ocorre colisão hash quando diferentes dados são mapeados para o mesmo índice. As abordagens comuns para resolver colisões incluem o método de encadeamento (chaining) e o método de sondagem linear (linear probing).

• Encadeamento: Elementos que colidem são armazenados em uma lista ligada associada ao índice.
• Sondagem Linear: Garante que o tamanho da tabela seja maior que a quantidade de dados inseridos para minimizar colisões e garantir a inserção.

Estruturas hash comuns incluem arrays, conjuntos (sets) e mapas (maps).

Árvores rubro-negras mantêm os elementos ordenados, mas chaves não podem ser modificadas diretamente para preservar a estrutura da árvore; operações de modificação envolvem remoção e inserção.

Para solucionar problemas que exigem a verificação rápida de existência em uma coleção, prefira std::unordered_set devido à sua eficiência O(1). Se a ordenação for um requisito, utilize std::set ou std::multiset.

Mapas (std::map, std::unordered_map) são estruturas chave-valor. Enquanto as chaves têm restrições (únicas, não modificáveis diretamente), os valores são flexíveis. A eficiência de std::unordered_map é ideal para buscas rápidas.

Em resumo, a abordagem de hash é indicada quando a necessidade é verificar rapidamente a presença de um elemento. Ela opera sob o princípio de troca de espaço por tempo, utilizando estruturas auxiliares como arrays, sets ou maps para obter agilidade nas consultas.

Exemplos de Aplicação

1. Anagrama Válido

Para determinar se duas strings são anagramas, podemos usar um array como tabela hash. Assumindo que as strings contenham apenas letras minúsculas do alfabeto inglês, um array de tamanho 26 é suficiente. Cada índice do array corresponderá a uma letra (por exemplo, 'a' mapeia para o índice 0, 'b' para 1, etc.).

Percorrremos a primeira string s, incrementando a contagem no índice correspondente à cada caractere. Em seguida, percorremos a segunda string t, decrementando a contagem para cada caractere. Se, ao final, todos os elementos do array forem zero, as strings são anagramas. Qualquer valor diferente de zero indica uma discrepância na contagem de caracteres.

A complexidade de tempo é O(n), onde n é o comprimento das strings. A complexidade de espaço é O(1), pois o array auxiliar tem tamanho constante.

class Solution {
public:
   bool isAnagram(string s, string t) {
       // Array para contar a frequência de cada caractere ('a' a 'z')
       int char_counts[26] = {0};

       // Incrementa a contagem para caracteres em s
       for (char c : s) {
           char_counts[c - 'a']++;
       }

       // Decrementa a contagem para caracteres em t
       for (char c : t) {
           char_counts[c - 'a']--;
       }

       // Verifica se todas as contagens são zero
       for (int count : char_counts) {
           if (count != 0) {
               return false; // Se alguma contagem for diferente de zero, não são anagramas
           }
       }

       return true; // Todas as contagens são zero, são anagramas
   }
};
 

2. Interseção de Dois Arrays

Este problema requer a identificação de elementos comuns entre dois arrays, com a particularidade de que o resultado deve conter apenas elementos únicos. A limitação de valores pode influenciar a escolha entre usar um array como hash ou uma estrutura mais flexível como std::unordered_set.

Quando os valores não são restritos ou são muito dispersos, std::unordered_set é preferível para evitar desperdício de espaço. A necessidade de remover duplicatas no resultado final reforça a escolha por um conjunto.

O algoritmo consiste em:

1. Popular um std::unordered_set com os elementos do primeiro array (nums1) para permitir consultas rápidas e deduplicação automática.
2. Iterar sobre o segundo array (nums2). Para cada elemento, verificar se ele existe no conjunto criado a partir de nums1.
3. Se um elemento de nums2 for encontrado no conjunto, adicioná-lo a um segundo conjunto (result_set) para garantir a unicidade do resultado.
4. Converter o result_set final em um std::vector para retornar.

#include <vector>
#include <unordered_set>

class Solution {
public:
   std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
       // Conjunto para armazenar os elementos únicos da interseção
       std::unordered_set<int> result_set;
       // Conjunto para armazenar os elementos únicos de nums1 para busca rápida
       std::unordered_set<int> nums1_set(nums1.begin(), nums1.end());

       // Itera sobre os elementos de nums2
       for (int num : nums2) {
           // Se o elemento de nums2 existe em nums1_set
           if (nums1_set.count(num)) { // Usando count() para verificar existência
               result_set.insert(num); // Adiciona ao conjunto de resultados (deduplica automaticamente)
           }
       }

       // Converte o conjunto de resultados para um vetor e retorna
       return std::vector<int>(result_set.begin(), result_set.end());
   }
};
 

3. Número Feliz

A característica chave deste problema é a detecção de ciclos. Se, ao calcular repetidamente a soma dos quadrados dos dígitos de um número, encontramos um valor que já foi visto anteriormente (e esse valor não é 1), significa que entramos em um ciclo e o número não é feliz. Novamente, a verificação de elementos já vistos sugere o uso de uma estrutura hash, como std::unordered_set.

O processo envolve:

1. Manter um conjunto (seen_sums) para registrar as somas intermediárias calculadas.
2. Em um loop, calcular a soma dos quadrados dos dígitos do número atual n.
3. Se a soma for 1, o número é feliz e retornamos true.
4. Se a soma já estiver presente em seen_sums, detectamos um ciclo e retornamos false.
5. Caso contrário, adicionamos a soma a seen_sums, atualizamos n para essa soma e continuamos o loop.

É crucial ter uma função auxiliar (get_digit_square_sum) para calcular a soma dos quadrados dos dígitos.

#include <unordered_set>

class Solution {
private:
   // Função auxiliar para calcular a soma dos quadrados dos dígitos
   int get_digit_square_sum(int n) {
       int sum = 0;
       while (n > 0) {
           int digit = n % 10;
           sum += digit * digit;
           n /= 10;
       }
       return sum;
   }

public:
   bool isHappy(int n) {
       // Conjunto para rastrear as somas já calculadas
       std::unordered_set<int> seen_sums;

       // Loop continua até que o número seja 1 ou um ciclo seja detectado
       while (n != 1 && seen_sums.find(n) == seen_sums.end()) {
           seen_sums.insert(n); // Adiciona a soma atual ao conjunto de vistos
           n = get_digit_square_sum(n); // Calcula a próxima soma
       }

       // Se n for 1, é um número feliz; caso contrário, um ciclo foi encontrado
       return n == 1;
   }
};
 

4. Soma de Dois Números (Two Sum)

Este problema clássico pede para encontrar dois números em um array que somados resultem em um valor alvo. Para resolver eficientemente, precisamos não apenas saber se um número complementar existe, mas também qual o seu índice. Isso exige uma estrutura que armazene pares chave-valor, como std::unordered_map.

O mapa armazenará o número como chave e seu índice como valor. Ao iterar pelo array:

1. Para cada número nums[i], calculamos o complemento necessário: complement = target - nums[i].
2. Verificamos se o complement já existe como chave no mapa.
3. Se o complement to encontrado, significa que encontramos o par. Retornamos o índice do complement (armazenado no mapa) e o índice atual i.
4. Se o complement não for encontrado, inserimos o número atual nums[i] e seu índice i no mapa para futuras consultas.

O uso de auto para o tipo do iterador simplifica a declaração e adapta-se a diferentes tipos de mapas.

#include <vector>
#include <unordered_map>
#include <utility> // Para std::pair

class Solution {
public:
   std::vector<int> twoSum(std::vector<int>& nums, int target) {
       // Mapa para armazenar o número e seu índice
       // Chave: número, Valor: índice
       std::unordered_map<int, int> num_to_index;

       // Itera sobre o array nums
       for (int i = 0; i < nums.size(); ++i) {
           int complement = target - nums[i];

           // Tenta encontrar o complemento no mapa
           auto it = num_to_index.find(complement);

           // Se o complemento foi encontrado no mapa
           if (it != num_to_index.end()) {
               // Retorna os índices do complemento e do número atual
               return {it->second, i};
           }

           // Se o complemento não foi encontrado, insere o número atual e seu índice no mapa
           // Usamos insert para evitar sobrescrever índices se houver duplicatas e
           // garantir que estamos sempre pegando o índice mais antigo, se necessário
           // No entanto, para Two Sum padrão, apenas adicionar o par é suficiente.
            num_to_index[nums[i]] = i; // Forma mais concisa de inserir/atualizar
           // Alternativa com insert: num_to_index.insert({nums[i], i});
       }

       // Se nenhum par for encontrado (o que não deve acontecer se houver solução garantida)
       return {};
   }
};
 

APIs comuns de std::unordered_map incluem:

• operator[]: Acessa ou insere um elemento.
• erase(key): Remove um elemento pela chave.
• size(): Retorna o número de elementos.
• clear(): Remove todos os elementos.
• begin(), end(): Iteradores para percorrer o mapa.