Hashing: Conceitos e Aplicações Práticas
O hashing é essencialmente uma função de mapeamento entre um domínio amplo e um intervalo menor.
Exemplo 1
Dado um conjunto de \(n\) números inteiros positivos, onde cada número está no intervalo \([1,10^6)\), remova duplicatas e ordene os números restantes em ordem crescente.
Solução
Podemos utilizar um array para contar a ocorrência de cada número. Em seguida, percorremos o intervalo de valores e exibimos todos os números cuja contagem seja maior que zero.
Complexidade de tempo: \(O(n)\) Complexidade de espaço: \(O(10^6)\)
Exemplo 2
Agora, dado \(n\) números inteiros positivos com valores no intervalo \([1,10^9)\), remova duplicatas e ordene os números restantes.
Neste caso, o intervalo é tão grande que não é possível usar a abordagem anterior diretamente.
Solução 1
Usar a função unique da STL, que tem complexidade aproximadamente \(O(n)\). No entanto, essa abordagem não é aplicável na maioria dos problemas.
Solução 2 - Algoritmo de Hashing
Implementamos uma função \(H\) que trnasforma um grande número \(x\) em um valor que pode ser armazenado em um array.
Normalmente, a função de hashing \(H(x)\) é definida como \(x \bmod P\), onde \(P\) é um número primo.
Aplicar a função de hashing nos números e, em seguida, usar a contagem de buckets.
Colisões de Hashing
Quando dois números diferentes \(x\) e \(y\) produzem o mesmo valor de hashing, ou seja, \(H(x) = H(y)\), temos uma colisão de hashing.
Resolvendo Colisões de Hashing
Usamos listas encadeadas para lidar com os valores de \(0\) a \(P-1\). Quando inserimos um valor \(x\), colocamos-o na lista correspondente a \(H(x)\).
Antes da inserção, verificamos se o valor já existe na lista. Se não existir, inserimos; caso contrário, ignoramos.
Complexidade de Tempo
\( O(n \cdot \text{comprimento médio da lista}) \approx O(n \cdot \frac{n}{P}) \)
Quando \(P \approx n\), temos \(O(n \cdot \frac{n}{P}) \approx O(n)\), o que é excelente.
Código de Exemplo
#include <bits/stdc++.h>
using namespace std;
const int TAMANHO_TABELA = 999983;
int quantidade_numeros, numero_atual, resposta_unica;
vector<int> tabela[TAMANHO_TABELA + 5];
int funcaoHash(int valor) {
return valor % TAMANHO_TABELA;
}
int inserirValor(int valor) {
int posicao = funcaoHash(valor);
for (int i = 0; i < tabela[posicao].size(); ++i) {
if (tabela[posicao][i] == valor) return 0;
}
tabela[posicao].push_back(valor);
return 1;
}
int main() {
cin >> quantidade_numeros;
for (int i = 1; i <= quantidade_numeros; ++i) {
cin >> numero_atual;
resposta_unica += inserirValor(numero_atual);
}
cout << resposta_unica << endl;
return 0;
}
Problemas Exemplo
- P4305 [JLOI2011] Números Não Repetidos
Neste problema, definimos a função de hashing como \(H(x) = x \bmod P\). É importante considerar números negativos.
Código:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e4 + 5;
const int TAMANHO_TABELA = 999983;
int testes, quantidade_numeros, resposta;
int numeros[MAX_N];
vector<int> tabela[TAMANHO_TABELA + 5];
int funcaoHash(int valor) {
return (valor % TAMANHO_TABELA + TAMANHO_TABELA) % TAMANHO_TABELA;
}
int inserirValor(int valor) {
int posicao = funcaoHash(valor);
for (int i = 0; i < tabela[posicao].size(); ++i) {
if (tabela[posicao][i] == valor) return 0;
}
tabela[posicao].push_back(valor);
return 1;
}
int main() {
cin >> testes;
while (testes--) {
cin >> quantidade_numeros;
resposta = 0;
for (int i = 1; i <= quantidade_numeros; ++i) {
scanf("%d", &numeros[i]);
}
for (int i = 0; i < TAMANHO_TABELA; ++i) {
tabela[i].clear();
}
for (int i = 1; i <= quantidade_numeros; ++i) {
if (inserirValor(numeros[i]) == 1) {
cout << numeros[i] << " ";
}
}
cout << endl;
}
return 0;
}
- P1955 [NOI2015] Análise Automática de Programas
Primeiro, observamos que quando \(x_i = x_j\), podemos usar a estrutura de união-fusão (union-find). Todas as relações com \(e=1\) são unidas, e depois verificamos as relações com \(e=0\) para ver se estão na mesma componente.
No entanto, o intervalo dos dados é \(1 \leq i,j \leq 10^9\), então precisaoms de hashing para reduzir o intervalo antes de aplicar union-find. A função de hashing é \(H(x) = x \bmod P\).
Complexidade de tempo: $O(n \cdot \alpha(n)) \approx O(n)$
Código:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
const int TAMANHO_TABELA = 990887;
int testes, quantidade_operacoes;
int x[MAX_N], y[MAX_N], opcao[MAX_N];
int pai[TAMANHO_TABELA + 5];
int funcaoHash(int valor) {
return valor % TAMANHO_TABELA;
}
int encontrar(int valor) {
if (valor == pai[valor]) return valor;
else return pai[valor] = encontrar(pai[valor]);
}
void unir(int x, int y) {
int raiz_x = encontrar(x), raiz_y = encontrar(y);
if (raiz_x != raiz_y) pai[raiz_x] = raiz_y;
return;
}
int main() {
cin >> testes;
while (testes--) {
cin >> quantidade_operacoes;
for (int i = 0; i < TAMANHO_TABELA; ++i) {
pai[i] = i;
}
for (int i = 1; i <= quantidade_operacoes; ++i) {
cin >> x[i] >> y[i] >> opcao[i];
if (opcao[i] == 1) unir(funcaoHash(x[i]), funcaoHash(y[i]));
}
bool valido = true;
for (int i = 1; i <= quantidade_operacoes; ++i) {
if (opcao[i] == 0) {
if (encontrar(funcaoHash(x[i])) == encontrar(funcaoHash(y[i]))) {
puts("NO");
valido = false;
break;
}
}
}
if (valido) puts("YES");
}
return 0;
}
- SP4354 TWINSNOW - Flocos de Neve
Entrada de exemplo (POJ):
2
1 2 3 4 5 6
4 3 2 1 6 5
Saída de exemplo (POJ):
Twin snowflakes found.
Cada floco de neve é uma sequência de seis números. Definimos o valor de hashing de uma sequência como a soma dos seus números módulo \(P\):
[H(a) = \sum_{i=1}^{6}{a_i} \bmod P]
Ao comparar dois flocos, precisamos verificar tanto na direção horária quanto anti-horária.
Código:
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
const int MAX_N = 1e5 + 5;
const int TAMANHO_TABELA = 99991;
int quantidade_flocos;
int floco[MAX_N][7];
vector<int> tabela[TAMANHO_TABELA + 5];
int funcaoHash(int indice) {
int soma = 0;
for (int i = 1; i <= 6; ++i) {
soma = (soma + floco[indice][i]) % TAMANHO_TABELA;
}
return soma % TAMANHO_TABELA;
}
bool saoIguais(int ind1, int ind2) {
for (int i = 1; i <= 6; ++i) {
for (int j = 1; j <= 6; ++j) {
bool igual = true;
for (int k = 0; k < 6; ++k) {
if (floco[ind1][(i + k) % 6 + 1] != floco[ind2][(j + k) % 6 + 1]) igual = false;
}
if (igual) return true;
igual = true;
for (int k = 0; k < 6; ++k) {
if (floco[ind1][(i + k) % 6 + 1] != floco[ind2][(j - k + 6) % 6 + 1]) igual = false;
}
if (igual) return true;
}
}
return false;
}
int inserirFloco(int indice) {
int valor = funcaoHash(indice);
for (int i = 0; i < tabela[valor].size(); ++i) {
if (saoIguais(tabela[valor][i], indice)) return 1;
}
tabela[valor].push_back(indice);
return 0;
}
int main() {
cin >> quantidade_flocos;
for (int i = 1; i <= quantidade_flocos; ++i) {
for (int j = 1; j <= 6; ++j) {
scanf("%lld", &floco[i][j]);
}
if (inserirFloco(i) == 1) {
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
return 0;
}