PRG29003: Introdução a Tabelas Hash
Uma tabela hash é uma estrutura de dados feita para armazenar dados indexados. Ela é particularmente eficiente quando a quantidade de dados é muito menor que o espaço de índices, como mostrado na figura abaixo. Por dado indexado entende-se um dado que é associado a uma chave, a qual funciona como um índice para localizá-lo. Posto de outra forma, pode-se entender a tabela hash como um mapeamento entre chaves e dados. No exemplo do analisador, o dado é um log, e a chave pode ser a URL, o usuário, o IP, ou uma combinação deles. Além disso, a quantidade de dados, por maior que seja, é muito menor que todas as combinações de caracteres de URL, ou que a quantidade de possíveis endereços IP, e assim por diante. A ideia por trás da tabela hash é reduzir o espaço de índices, de forma que sua quantidade seja parecida com a dos dados indexados.
O espaço de chaves e a tabela hash (obtido do livro "Algoritmos, 2a. ed.", de T. Cormen et al)
Alguns exemplos de uso de tabelas hash na vida real:
- Cache de inodes em sistemas de arquivos no Linux
- Alguns usos, de acordo com a Wikipedia
- Matriz esparsa (aplicável em Física, Engenharia, e outras áreas)
- Tabela de rotas em roteadores Linux
- 5 Mitos sobre Tabelas Hash
A prglib possui uma implementação de tabela hash, mostrada a seguir:
template <typename T> class thash : public std::unordered_map<std::string,T> {
public:
// cria uma tabela hash com num_linhas linhas
thash(int num_linhas);
thash(const thash &outra); // construtor de copia
// destrutor
virtual ~thash();
// adiciona um dado à tabela. Se já existir na tabela um par contendo a chave
// "chave", o dado desse par deve ser substituído por "algo". Caso contrário,
// um novo par deve ser adicionado à tabela.
void adiciona(const std::string& chave, const T& algo);
// remove a chave "chave" e o dado a ela associado.
T remove(const std::string& chave);
// retorna o dado associado a "chave"
T& operator[](const std::string& chave);
T& obtem(const std::string& chave);
// retorna uma lista com as chaves existentes na tabela
std::shared_ptr<lista<std::string>> chaves() const;
// retorna uma lista com os dados existentes na tabela
std::shared_ptr<lista<T>> valores() const;
// retorna verdadeiro se "chave" existe na tabela
bool existe(const std::string& chave) const;
// esvazia a tabela
void esvazia();
// retorna a quantidade de dados (ou chaves) existentes na tabela
unsigned int tamanho() const;
private:
unsigned int linhas; // a quantidade de linhas da tabela
};
A seguir há um exemplo de uso da tabela hash:
#include <iostream>
#include <prglib.h>
using namespace std;
using prglib::thash;
using prglib::lista;
/*
*
*/
int main(int argc, char** argv) {
// cria uma tabela com 5 linhas
thash<long> tab(5);
// adiciona dados à tabela: primeiro parâmetro é a chave, e segundo é
// o valor a ela associado
tab.adiciona("um", 1);
tab.adiciona("dois", 2);
tab.adiciona("tres",3);
// mostra os valores armazenados
cout << tab["um"] << endl;
cout << tab["dois"] << endl;
cout << tab["tres"] << endl;
// obtém uma lista com as chaves contidas na tabela.
// Notar o uso de std::shared_ptr (smart pointer), que é um ponteiro
// que libera automaticamente a memória apontada quando não mais necessária.
auto chaves = tab.chaves();
cout << "Chaves: ";
chaves->escrevaSe(cout, ", ");
// Obtém uma lista com os valores contidos na tabela
cout << endl;
auto valores = tab.valores();
cout << "Valores: ";
valores->escrevaSe(cout, ", ");
cout << endl;
// Testa se uma determinada chave existe na tabela
if (tab.existe("dois")) cout << "Tabela contém a chave: dois" << endl;
else cout << "Tabela NÃO contém a chave: dois" << endl;
// remove uma chave da tabela e, por consequência, o valor a ela associado
tab.remove("dois");
cout << "Removeu a chave: dois" << endl;
// Testa se a chave removida ainda existe na tabela
if (tab.existe("dois")) cout << "Tabela contém a chave: dois" << endl;
else cout << "Tabela NÃO contém a chave: dois" << endl;
return 0;
}
Atividade
- Escreva um programa que conte quantas palavras diferentes existem em um arquivo. Seu programa deve ignorar maiúsculas e minúsculas
- Escreva um programa que extraia as palavras repetidas de um arquivo. Quer dizer, esse programa deve mostrar como resultado apenas a primeira ocorrência de cada palavra de um arquivo
- Reescreva o limpador de dados redundantes usando uma tabela hash. Compare o tempo de execução desse novo programa com a versão feita inicialmente com listas.