Estrutura de Dados Parte 5 - Tabela de Espalhamento

Tabela de espalhamento

A tabela de espalhamento ou tabela de hash é uma estrutura que consiste em indexar os elementos armazenados de maneira que seja fácil e rápido encontrar qualquer elemento a partir de sua chave.

Essa estrutura não tem a premissa de armazenar os elementos de maneira sequencial e sim de identificar uma categoria para o elemento e armazená-lo de acordo.

É uma estrutura muito usada tanto na computação quanto no dia a dia.

1. Agenda telefônica
2. Corredores de supermercado
3. Organizar livros em uma biblioteca

O primeiro passo é identificar a qual categoria pertence o elemento que queremos armazenar, para isso temos a "função hash". Esta função é responsável por gerar o índice do elemento. Portanto, essa função deve ser escolhida com cuidado pois caso a função seja mal implementada a tabela terá uma performance ruim.

Vamos pegar um exemplo de uma agenda telefônica.

Para armazenar o nome "Geraldo", executamos a função hash que irá produzir o índice "G".

Já o nome "Nayara" irá produzir o índice "N" e o nome "Fábio" irá produzir o índice "F".

Desta maneira sabemos que os elementos serão armazenados da seguinte maneira:

    

Para recuperar o nome "Fábio" usamos novamente o índice "F" e acessamos o elemento diretamente.

Mesmo que a nossa "função hash" seja muito boa, ainda assim estamos sujeitos a colisões, que é quando dois elementos distintos produzem o mesmo índice. O nome "Francisco" também produz o índice "F" e no exemplo acima ocorreria uma colisão com o nome "Fábio".

Nesse caso precisamos combinar mais de uma estrutura para permitir que os dois elementos possam coexistir.

Podemos combinar as estruturas "tabela de espalhamento" e alguma outra estrutura que melhor encaixe no nosso contexto como Pilhas, Filas e Listas, etc.

public class TabelaEspalhamentoApp {
 
 public static void main(String[] args) {
  TabelaEspalhamento tabela = new TabelaEspalhamento();

  tabela.adiciona("Nayara");
  tabela.adiciona("Geraldo");
  tabela.adiciona("Gorge");
  tabela.adiciona("Fabio");

  System.out.println(tabela.contem("Geraldo"));

  tabela.remove("Gorge");
  System.out.println(tabela.contem("Geraldo"));
  System.out.println(tabela.contem("Gorge"));

 }

}

public class TabelaEspalhamento {

 VetorGenerico vetor = new VetorGenerico();

 public void remove(String elemento) {
  int indice = recuperarIndice(elemento);
  Vetor v = (Vetor) vetor.get(indice);
  if (v != null) {
   int posicao = v.indice(elemento);
   if (posicao >= 0) {
    v.remove(posicao);
   }

  }
 }

 public boolean contem(String elemento) {
  int indice = recuperarIndice(elemento);
  Vetor v = (Vetor) vetor.get(indice);
  if (v != null) {
   return v.has(elemento);
  }
  return false;
 }

 public void adiciona(String elemento) {
  int indice = recuperarIndice(elemento);
  Vetor v = (Vetor) vetor.get(indice);
  if (v == null) {
   v = new Vetor();
  }
  v.add(elemento);
  vetor.add(indice, v);
 }

 private int recuperarIndice(String elemento) {
  return elemento.charAt(0) % 75;
 }

}

public class VetorGenerico{

 Object[] elementos = new Object[1000];
 int indice;

 public void add(Object elemento) {
  elementos[indice] = elemento;
  indice++;
 }

 public Object get(int i) {
  return elementos[i];
 }

 public void add(int posicao, Object elemento) {
  for (int i = indice - 1; i >= posicao; i--) {
   elementos[i + 1] = elementos[i];
  }

  elementos[posicao] = elemento;
  indice++;
 }
 
 public void remove(int posicao) {
  elementos[posicao] = null;

  for (int i = posicao; i + 1 < elementos.length; i++) {
   elementos[i] = elementos[i + 1];
  }

  indice--;
 }
}