Introdução

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). Conforme o artigo Importância das tabelas hash, algumas perguntas típicas que se referem a tabelas hash contêm frases como estas:

Procure por elementos dentro de um grande conjunto de dados
Encontre elementos duplicados em um conjunto de dados
Armazene e obtenha rapidamente elementos de um grande conjunto de dados

... e possivelmente existem outras necessidades em que tabeas hash são úteis !

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

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. Isso pode ser melhor entendido quando se observa como a tabela funciona internamente. A figura a seguir mostra de forma simplificada uma possível tabela hash, que possui alguns valores armazenados junto com suas respectivas chaves. Uma consulta, ou busca por um valor, na tabela é feita por meio de sua chave (algumas chaves são mostradas do lado esquerdo da figura). Uma função, chamada de função hash, calcula um número a partir da chave. Esse número é usado para acessar uma posição de um vetor (cada posição corresponde a um bucket, que é um lugar onde se armazena um dado). Obtém-se então o dado procurado no bucket correspondente. A grande vantagem da tabela é que o cálculo da posição pela função hash é muito eficiente (rápida), e assim se localiza o dado muito rapidamente.

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)

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, ainda que usando outra linguagem de programação para ilustrá-la. O video introduz também alguns aspectos de implementação de uma tabela hash (quer dizer, como ela funciona internamente)

A tabela hash da STL

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.

O exemplo a seguir mostra o uso de uma tabela hash para calcular quantas unidades de cada produto foram vendidas. Ele lê um arquivo onde há registros de produtos vendidos, e cada linha possui este formato:

produto quantidade

#include <unordered_map>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main(int argc, char * argv[]) {
  // cria uma tabela hash: a chave é um string (nome do produto), e o valor um int (sua quantidade)
  unordered_map<string,int> totais;

  // abre o arquivo de dados
  ifstream arq(argv[1]);

  if (! arq.is_open()) {
    cout << "Uso: " << argv[0] << " arq_dados" << endl;
    return 0;
  }

  string produto;
  int qtde;

  // lê um par de valores por vez do arquivo
  // esse par é composto pelo nome do produto e de sua quantidade
  while (arq >> produto >> qtde) {
    // se chave (nome do produto) já existe na tabela ...
    if (totais.count(produto) > 0) {
      // ... acessa o valor a ela associado, e a ele soma o número lido do arquivo
      totais[produto] += qtde;
    } else {
      // ... senão armazena acessa o número lido associado a essa chave
      totais[produto] = qtde;
    }
  }

  // itera a tabela
  // para cada par formado por chave e valor ...
  for (auto & par: totais) {
    // mostra a chave (par.first) seguido do valor (par.second)
    cout << par.first << ": " << par.second << endl;
  }
}

Este outro exemplo mostra o uso de um conjunto (unordered_set) para eliminar dados duplicados de uma lista:

#include <unordered_set>
#include <list>
#include <string>

using namespace std;

// unique_clone: elimina dados duplicados da lista "l"
void unique_clone(list<string> & l) {
  // cria um conjunto de string
  unordered_set<string> conj;

  // adiciona cada dado da lista ao conjunto
  // Note que o conjunto contem somente dados únicos, 
  for (auto & x: l) {
    conj.insert(x);
  }

  // limpa a lista
  l.clear();

  // adiciona cada dado do conjunto à lista
  // isso vai fazer com que dados duplicados sejam eliminados
  for (auto & x: conj) {
    l.push_back(x);
  }
}

Adicionando chaves e respectivos valores

Usando operação insert para adicionar chave e valor: esta é uma forma direta de armazenar chaves e valores em uma tabela. A chave e respectivo valor são acrescentados de uma tacada só.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  // Uma tabela com chaves string, e valores float
  // Chave: nome de produto
  // Valor: preço desse produto
  unordered_map<string,float> tab;

  // Insere alguns produtos na tabela. Isso deve ser feito sempre na forma de
  // um par formado por chave e valor. O primeiro parâmetro é a chave, e o segundo
  // é o valor
  tab.insert("banana", 3.19);
  tab.insert("laranja", 2.29);
  tab.insert("tomate", 3.99);
  tab.insert("batata", 2.99);

  // Neste laço, o usuário pode consultar o preço de produtos
  // conhecidos. Para sair do laço, basta teclar somente ENTER
  while (true) {
    string produto;

    cout << "Produto: ";
    getline(cin, produto);
    if (produto.empty()) break; // teclou somente ENTER ... gerou string vazia

    // verifica se este produto (chave) existe na tabela
    if (tab.count(produto) > 0) {
      // caso afirmativo, mostra o respectivo
      cout << "Preço: " << tab[produto] << endl;
    } else {
      cout << produto << " desconhecido" << endl;
    }
  }

}

Usando operador [] para armazenar valor associado a uma chave: a diferença é sutil em relação ao uso de insert. Ao usar o operador [], como em tab["banana"] = 3.19;, acontece o seguinte:

A chave é procurada na tabela. Se ela existir, uma referência ao respectivo valor é retornada. Se a chave não existir, ela é automaticamente inserida na tabela e a ela se associa um valor default (no caso de um tipo numérico, o valor default é 0). Em seguida, também se retorna uma referência ao valor associado à chave.

O novo valor é armazenado, pois a referência ao valor existente possibilita sobrescrevê-lo

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  // Uma tabela com chaves string, e valores float
  // Chave: nome de produto
  // Valor: preço desse produto
  unordered_map<string,float> tab;

  // Insere alguns produtos na tabela. Parece que a tabela funciona como um vetor,
  // cujas posições são acessadas por meio da chave ...
  tab["banana"] = 3.19;
  tab["laranja"] = 2.29;
  tab["tomate"] = 3.99;
  tab["batata"] = 2.99;

  // Neste laço, o usuário pode consultar o preço de produtos
  // conhecidos. Para sair do laço, basta teclar somente ENTER
  while (true) {
    string produto;

    cout << "Produto: ";
    getline(cin, produto);
    if (produto.empty()) break; // teclou somente ENTER ... gerou string vazia

    // verifica se este produto (chave) existe na tabela
    if (tab.count(produto) > 0) {
      // caso afirmativo, mostra o respectivo
      cout << "Preço: " << tab[produto] << endl;
    } else {
      cout << produto << " desconhecido" << endl;
    }
  }

}

Acessando valores

Cada valor na tabela hash está associado a uma chave. Para acessar um valor, portanto, deve-se informar a chave. Existem duas operações quase idênticas para acessar valores:

Usando operador [] para acessar o valor associado a uma chave: esta é uma forma direta de acessar um valor. O detalhe a se observar é que, caso a chave não exista na tabela, ela é automaticamente inserida e a ela se associa um valor default (por exemplo, no caso de um tipo numérico, o valor default é 0). Em qualquer caso, o operador[] retorna como resultado uma referência ao valor associado à chave.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  // Uma tabela com chaves string, e valores float
  // Chave: nome de produto
  // Valor: preço desse produto
  unordered_map<string,float> tab;

  // Insere alguns produtos na tabela. Parece que a tabela funciona como um vetor,
  // cujas posições são acessadas por meio da chave ...
  tab["banana"] = 3.19;
  tab["laranja"] = 2.29;
  tab["tomate"] = 3.99;
  tab["batata"] = 2.99;

  // Neste laço, o usuário pode consultar o preço de produtos
  // conhecidos. Para sair do laço, basta teclar somente ENTER
  while (true) {
    string produto;

    cout << "Produto: ";
    getline(cin, produto);
    if (produto.empty()) break; // teclou somente ENTER ... gerou string vazia

    // verifica se este produto (chave) existe na tabela
    // não se pode usar diretamente o operador[] para verificar se a chave existe,
    // pois ele a adiciona à tabela automaticamente, caso não exista
    // Por isso a verificação é feita com a operação count, que retorna
    // 0 (zero) se a chave não existir
    if (tab.count(produto) > 0) {
      // caso afirmativo, mostra o respectivo
      cout << "Preço: " << tab[produto] << endl;
    } else {
      cout << produto << " desconhecido" << endl;
    }
  }

}

Usando a operação at: a diferença é sutil em relação ao operador[]. Caso a chave não exista na tabela, uma exceção é disparada. Se a chave existir, o acesso com at retorna como resultado uma referência ao valor associado à chave.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  // Uma tabela com chaves string, e valores float
  // Chave: nome de produto
  // Valor: preço desse produto
  unordered_map<string,float> tab;

  // Insere alguns produtos na tabela. Parece que a tabela funciona como um vetor,
  // cujas posições são acessadas por meio da chave ...
  tab["banana"] = 3.19;
  tab["laranja"] = 2.29;
  tab["tomate"] = 3.99;
  tab["batata"] = 2.99;

  // Neste laço, o usuário pode consultar o preço de produtos
  // conhecidos. Para sair do laço, basta teclar somente ENTER
  while (true) {
    string produto;

    cout << "Produto: ";
    getline(cin, produto);
    if (produto.empty()) break; // teclou somente ENTER ... gerou string vazia

    // verifica se este produto (chave) existe na tabela
    // observe como se explora a exceção disparada por at caso
    // a chave não exista
    try {
      // caso afirmativo, mostra o respectivo
      cout << "Preço: " << tab.at(produto) << endl;
    } catch (...) {
      cout << produto << " desconhecido" << endl;
    }
  }

}

Listando chaves e valores

As chaves e respectivos valores contidos em uma tabela podem ser listados por meio de uma iteração. De forma parecida com a iteração da lista, a iteração da tabela possibilita o acesso sequencial aos pares (chave, valor). Cada par é acessado por meio de um valor do tipo pair, que é um tipo predefinido contendo dois atributos chamados de first e second. Ao se iterar a tabela, o atributo first de cada par corresponde à chave, e second corresponde ao valor. Veja o exemplo a seguir.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  // Uma tabela com chaves string, e valores float
  // Chave: nome de produto
  // Valor: preço desse produto
  unordered_map<string,float> tab;

  // Insere alguns produtos na tabela. Parece que a tabela funciona como um vetor,
  // cujas posições são acessadas por meio da chave ...
  tab["banana"] = 3.19;
  tab["laranja"] = 2.29;
  tab["tomate"] = 3.99;
  tab["batata"] = 2.99;

  // Itera a tabela, mostrando cada chave e respectivo valor
  for (auto & par: tab) {
    cout << "Chave=" << par.first << ", e valor=" << par.second;
  }
}

A iteração pode ser explicitada no exemplo a seguir. A única diferença em relação ao anterior é que se usa um iterador.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  // Uma tabela com chaves string, e valores float
  // Chave: nome de produto
  // Valor: preço desse produto
  unordered_map<string,float> tab;

  // Insere alguns produtos na tabela. Parece que a tabela funciona como um vetor,
  // cujas posições são acessadas por meio da chave ...
  tab["banana"] = 3.19;
  tab["laranja"] = 2.29;
  tab["tomate"] = 3.99;
  tab["batata"] = 2.99;

  // Itera a tabela, mostrando cada chave e respectivo valor
  for (auto & it = tab.begin(); it != tab.end(); it++) {
    // faz uma referência ao valor apontado pelo iterador ...
    // isso serve apenas por conveniência
    pair & par = *it;

    cout << "Chave=" << par.first << ", e valor=" << par.second;
  }
}

Atividade

Resolva o exercício sobre contar palavras de um arquivo, porém use uma das estruturas de dados do tipo tabela hash da STL desta vez.
Resolva o exercício sobre filtrar palavras repetidas de um arquivo, porém use uma das estruturas de dados do tipo tabela hash da STL desta vez.
Veja o exercício sobre relacionar números, e resolva-o usando tabela hash. Pode-se resolvê-lo usando lista, mas com tabela é mais simples e eficiente !
Um problema usual é fazer a intersecção de duas listas. Resolva este exercício usando tabela hash.
Outra necessidade usual é identificar o valor que aparece mais vezes em uma determinada sequência de valores. Resolva este exercício, que tem por objetivo mostrar as palavras que mais aparecem em um arquivo.

E este exercício é um pouco maior:

Um mercado mantém contas de seus clientes, para que possam adquirir produtos e pagá-los no final do mês. Cada vez que um cliente faz uma compra, o vendedor registra em um arquivo a data e valor da compra seguidos do nome do cliente. O arquivo com as compras dos clientes fica desta forma:

30/09/2016 20.54 Seu Maneca

3/10/2016 99.11 Dona Bilica

3/10/2016 4.67 Prof. Raimundo

Escreva um programa que calcule o valor a ser pago por um cliente em um determinado mês. Esse programa deve receber pela entrada padrão (teclado) o nome do cliente seguido do mês (nesta ordem), e apresentar na saída padrão o valor total gasto. O arquivo com os registros de compras se chama "cliente.txt".

Arquivo cliente.txt

PRG29003: Introdução a Tabelas Hash

Índice