Mudanças entre as edições de "PRG29003: Introdução a Tabelas Hash"
Linha 1: | Linha 1: | ||
__toc__ | __toc__ | ||
+ | * [http://hughewilliams.com/2012/10/01/five-myths-about-hash-tables/ 5 Mitos sobre Tabelas Hash] | ||
+ | |||
+ | |||
+ | Uma tabela de dispersão, chamada de tabela ''hash'', é uma forma de armazenar dados de forma que possam ser rapidamente localizados. Ao contrário de uma lista encadeada, em que se deve procurar um dado comparando-o com todos os dados a partir do inicio da lista até encontrar o dado desejado, uma tabela ''hash'' possibilita localizar um dado com pouquíssimas comparações (tipicamente UMA). Numa tabela, os dados são armazenados em locais diretamente alcançáveis, de acordo com alguma característica ou informação que se possa extrair deles. Veja estes dois exemplos de coisas da vida real que se assemelham a tabelas ''hash'' ... | ||
− | + | {| border=0 | |
+ | |[[imagem:prg29003-Hash1.jpg|300px]] || [[imagem:prg29003-Hash2.jpg]] | ||
+ | |} | ||
+ | <br>''Algo parecido com tabelas hash reais ...'' | ||
− | + | Cada dado armazenado em uma tabela ''hash'' fica associado a uma chave, que é uma informação única. Isso quer dizer que não podem existir duas chaves iguais em uma tabela. Uma chave funciona assim como um localizador para um determinado dado. Por exemplo, em uma tabela que armazena cadastros de clientes de uma loja, os CPF dos clientes poderiam ser as chaves. | |
− | |||
− | Alguns exemplos de uso de tabelas hash | + | Alguns exemplos de uso de tabelas ''hash'' em softwares: |
* [http://linuxtutorial.info/modules.php?name=MContent&pageid=284 Cache de inodes em sistemas de arquivos no Linux] | * [http://linuxtutorial.info/modules.php?name=MContent&pageid=284 Cache de inodes em sistemas de arquivos no Linux] | ||
* [http://en.wikipedia.org/wiki/Hash_table#Uses Alguns usos, de acordo com a Wikipedia] | * [http://en.wikipedia.org/wiki/Hash_table#Uses Alguns usos, de acordo com a Wikipedia] | ||
* [http://en.wikipedia.org/wiki/Sparse_matrix Matriz esparsa (aplicável em Física, Engenharia, e outras áreas)] | * [http://en.wikipedia.org/wiki/Sparse_matrix Matriz esparsa (aplicável em Física, Engenharia, e outras áreas)] | ||
* [http://vincent.bernat.im/en/blog/2011-ipv4-route-cache-linux.html Tabela de rotas em roteadores Linux] | * [http://vincent.bernat.im/en/blog/2011-ipv4-route-cache-linux.html Tabela de rotas em roteadores Linux] | ||
− | |||
+ | = A tabela ''hash'' da prglib = | ||
A prglib possui uma implementação de tabela hash, mostrada a seguir: | A prglib possui uma implementação de tabela hash, mostrada a seguir: | ||
<syntaxhighlight lang=c> | <syntaxhighlight lang=c> | ||
− | template <typename T> class thash | + | template <typename T> class thash { |
public: | public: | ||
// cria uma tabela hash com num_linhas linhas | // cria uma tabela hash com num_linhas linhas | ||
+ | // OBS: idealmente num_linhas deve ser um número primo ! | ||
thash(int num_linhas); | thash(int num_linhas); | ||
Linha 28: | Linha 35: | ||
// destrutor | // destrutor | ||
− | + | ~thash(); | |
// adiciona um dado à tabela. Se já existir na tabela um par contendo a chave | // adiciona um dado à tabela. Se já existir na tabela um par contendo a chave |
Edição das 15h32min de 26 de março de 2018
Uma tabela de dispersão, chamada de tabela hash, é uma forma de armazenar dados de forma que possam ser rapidamente localizados. Ao contrário de uma lista encadeada, em que se deve procurar um dado comparando-o com todos os dados a partir do inicio da lista até encontrar o dado desejado, uma tabela hash possibilita localizar um dado com pouquíssimas comparações (tipicamente UMA). Numa tabela, os dados são armazenados em locais diretamente alcançáveis, de acordo com alguma característica ou informação que se possa extrair deles. Veja estes dois exemplos de coisas da vida real que se assemelham a tabelas hash ...
Algo parecido com tabelas hash reais ...
Cada dado armazenado em uma tabela hash fica associado a uma chave, que é uma informação única. Isso quer dizer que não podem existir duas chaves iguais em uma tabela. Uma chave funciona assim como um localizador para um determinado dado. Por exemplo, em uma tabela que armazena cadastros de clientes de uma loja, os CPF dos clientes poderiam ser as chaves.
Alguns exemplos de uso de tabelas hash em softwares:
- 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
A tabela hash da prglib
A prglib possui uma implementação de tabela hash, mostrada a seguir:
template <typename T> class thash {
public:
// cria uma tabela hash com num_linhas linhas
// OBS: idealmente num_linhas deve ser um número primo !
thash(int num_linhas);
thash(const thash &outra); // construtor de copia
// destrutor
~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.