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

1. Escreva um programa que conte quantas palavras diferentes existem em um arquivo. Seu programa deve ignorar maiúsculas e minúsculas
2. 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
3. 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.