PRG29003: Introdução a Tabelas Hash

Próxima aula

• Tabelas hash na Wikipedia
• 5 Mitos sobre Tabelas Hash
• A importância de tabelas hash (artigo no site Coderbyte]

Uma tabela de dispersão, chamada de tabela hash, é uma forma de armazenar dados para 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. Para acessar um determinado dado, deve-se procurá-lo por meio de sua chave. Desta forma, uma chave funciona 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.

In computing, a hash table (hash map) is a data structure used to implement an associative array, a structure that 
can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, 
from which the desired value can be found.

In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. 
For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database 
indexing, caches, and sets.

Uma definição para tabelas hash na Wikipedia

A estrutura de dados tabela hash: chaves são mapeadas por uma função de espalhamento (função hash) para locais (buckets) em uma tabela onde estão os dados correspondentes (figura obtida na Wikipedia)

Tabela hash é a primeira estrutura de dados associativa que estudaremos. Diferente das estruturas de dados lineares lista, fila e pilha, na tabela hash o local de armazenamento de cada dado depende de seu valor.

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 (se bem que em versões atuais do kernel Linux a cache de tabela de rotas foi removida)

Uma boa apresentação sobre tabela hash, mesmo que usando outra linguagem de programação para ilustrá-la. O video introduz também alguns aspcetos de implementação de uma tabela hash (quer dizer, como ela funciona internamente)

A tabela hash da STL

• Arquivo de projeto CLion com a prglib

A STL possui duas implementações de tabela hash. Seus nomes parecem estranhos, mas significam que os dados armazenados não seguem uma ordem, e tampouco tem relação com a ordem com que são armazenados. O que interessa é que, internamente, o local de armazenamento em memória depende das chaves.

• unordered_map: nesta estrutura, armazenam-se pares de valores. Um deles é a chave e outro é o dado em si. A chave é usada para identificar e localizar o dado armazenado. Apenas um dado por chave pode ser armazenado.
• unordered_set: nesta outra estrutura, o valor armazenado faz o papel de chave. Uma aplicação comum desta estrutura é verificar se um valor já foi usado ou se já está presente.

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 string& chave, const T& algo);
 
  // remove a chave "chave" e o dado a ela associado.
  T remove(const string& chave);
 
  // retorna o dado associado a "chave"
  T& operator[](const string& chave);
  T& obtem(const string& chave);
 
  // retorna uma lista com as chaves existentes na tabela
  shared_ptr<lista<string>> chaves() const;
 
  // retorna uma lista com os dados existentes na tabela
  shared_ptr<lista<T>> valores() const;
 
  // retorna verdadeiro se "chave" existe na tabela
  bool existe(const string& chave) const;
 
  // esvazia a tabela
  void esvazia();
 
  // retorna a quantidade de dados (ou chaves) existentes na tabela
  unsigned int tamanho() const;
 
};

A seguir há um exemplo de uso da tabela hash:

Um primeiro exemplo

#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 buckets 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. // o resultado do método "chaves" é um ponteiro para uma lista<string> auto chaves = tab.chaves(); cout << "Chaves: "; chaves->escrevaSe(cout, ", "); cout << endl; // Obtém uma lista com os valores contidos na tabela // o resultado do método "valores" é um ponteiro para uma lista<long> // (pois a tabela armazena long) 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 long dado = tab.remove("dois"); cout << "Removeu a chave: dois, e o dado que lá havia era: " << dado << 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

1. Contador de ocorrências de palavras em um arquivo
2. Listar palavras diferentes de um arquivo
3. Contador de palavras diferentes em um arquivo
4. Contador de números em intervalos
5. Analisador de acessos de usuários a um sistema
6. Agrupador de palavras