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--;
 }
}

Estrutura de Dados - Pesquisa - Sequencial ou Linear, Binária e Interpolação

PESQUISA

Nos dias de hoje, o acesso rápido a informação pode ser determinante para o sucesso do aplicativo. Por isso o algoritmo de pesquisa é tão importante quanto a estrutura de armazenamento e o algoritmo de ordenação.

PESQUISA SEQUENCIAL

Vamos falar do mecanismo de pesquisa mais trivial que existe, a Pesquisa Linear ou Sequencial.

Esse algoritmo consiste em percorrer cada um dos elementos da nossa estrutura até encontrar o elemento desejado. Sua eficiência é inversamente proporcional a quantidade de elementos que tivermos que percorrer. Na melhor hipótese o elemento desejado será o primeiro e na pior hipótese o elemento desejado será o último.

Podemos melhorar significativamente o desempenho se os elementos estiverem ordenados. Por isso é tão importante escolher a estrutura certa assim como aplicar algoritmos de ordenação.

Por exemplo, se queremos encontrar um nome específico na nossa agenda telefônica, será muito mais rápido se a agenda estiver organizada por ordem alfabética. Assim podemos pular alguns nome que temos certeza que não irão atender ao critério de pesquisa.

public class PesquisaLinear {

 public static int pesquisar(String arr[], String argumento) {
  
  for (int i = 0; i < arr.length; i++) {
   if (arr[i] == argumento) {
    return i;
   }
  }

  return -1;
 }

 public static void main(String args[]) {
  String arr[] = { "A", "B", "C", "D" };
  System.out.println(pesquisar(arr, "C"));
 }

}

PESQUISA BINÁRIA

A pesquisa binária utiliza da técnica "dividir para conquisar". Consiste em dividir os elementos ao meio, em seguida é verificado se o elemento desejado é maior ou menor que o elemento central. Caso seja maior, então o elemento desejado obrigatoriamente deve estar do lado direito da divisão e caso seja menor então obrigatoriamente deve estar do lado esquerdo. Esse processo de divisão e verificação é repetido até encontrar o elemento.

Repare para que esse algoritmo funcione, os elementos devem estar obrigatoriamente ordenados, caso contrário pode não funcionar.

public class PesquisaBinaria {

 public static int pesquisar(int arr[], int l, int r, int x) {
  if (r >= l) {
   int mid = l + (r - l) / 2;

   if (arr[mid] == x)
    return mid;

   if (arr[mid] > x)
    return pesquisar(arr, l, mid - 1, x);

   return pesquisar(arr, mid + 1, r, x);
  }

  return -1;
 }

 public static void main(String args[]) {
  int arr[] = { 2, 3, 4, 10, 40 };
  int n = arr.length;
  int x = 10;
  int posicao = pesquisar(arr, 0, n - 1, x);
  if (posicao == -1)
   System.out.println("Elemento não encontrado");
  else
   System.out.println("Elemento encontrado na posição " + posicao);
 }
}

PESQUISA POR INTERPOLAÇÃO

Este algoritmo de pesquisa, assim como a busca binária, tem como premissa que os elementos esteja previamente ordenados, além disso o algoritmo é semelhante a busca binária, eles diferem na forma como os elementos são divididos. Enquanto a busca binária está sempre dividindo ao meio, a busca por interpolação divide os elementos com base na fórmula abaixo:

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

public class PesquisaInterpolacao {

 public static int pesquisar(int[] arr, int x) {
  int lo = 0, hi = (arr.length - 1);

  while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {

   if (lo == hi) {
    if (arr[lo] == x)
     return lo;
    return -1;
   }

   int pos = lo + (((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));

   if (arr[pos] == x)
    return pos;

   if (arr[pos] < x)
    lo = pos + 1;

   else
    hi = pos - 1;
  }
  return -1;
 }

 public static void main(String[] args) {
  int x = 18;
  int arr[] = new int[] { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
  int posicao = pesquisar(arr, x);

  if (posicao != -1)
   System.out.println("Elemento encontrado na posição " + posicao);
  else
   System.out.println("Elemento não encontrado.");
 }

}

Estrutura de Dados - Ordenação Parte 2 - Selection, Insertion e Shell sort

Selection sort.

O algoritmo consiste em selecionar o menor (ou maior) elemento fora de ordem colocá-lo em sua posição correta. Para fazer isso, primeiro os elementos devem ser divididos em duas partes: os elementos já ordenados e os elementos que ainda não foram ordenados.

Inicialmente a parte ordenada estará vazia, enquanto a parte não ordenada possuirá todos os elementos.

Após a divisão, o algoritmo irá encontrar o menor elemento do lado não ordenado e colocá-lo no lado ordenado. Esse passo irá se repetir até que o lado não ordenado fique vazio.

Este algoritmo possui duas grandes vantagens, primeiro, é um algoritmo simples de ser implementado e segundo, não há consumo de memória além daquele já alocado para os elementos originais, uma vez que a divisão de lado ordenado e lado não ordenado é feita no próprio vetor que queremos ordenar.

A maior desvantagem é que é um algoritmo que não tem um bom desempenho quando temos uma quantidade de elementos muito grande.

public class SelectionSort {

 public static void ordenar(int arr[]) {
  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
   int min = i;
   for (int j = i + 1; j < n; j++)
    if (arr[j] < arr[min])
     min = j;

   int temp = arr[min];
   arr[min] = arr[i];
   arr[i] = temp;
  }
 }

 public static void main(String args[]) {
  int arr[] = { 64, 25, 12, 22, 11 };

  System.out.println("Antes de ordenar");
  imprimir(arr);

  ordenar(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }

}

Insertion sort

O algoritmos consiste inicialmente em selecionar um pivô e comparar os elementos seguintes, um a um. Se o elemento seguinte for maior que o pivô, esse elemento agora passará a ser o novo pivô. Se o elemento for menor que o pivô, os elementos anteriores ao pivô serão percorridos até ser encontrado o elemento maior que o elemento encontrado anteriormente colocando-o logo antes do elemento maior.

Este algoritmo possui uma vantagem: não há consumo de memória além daquele já alocado para os elementos originais, uma que toda a ordenação ocorre dentro dos próprios elementos.

A maior desvantagem é que é um algoritmo que não tem um bom desempenho quando temos uma quantidade de elementos muito grande, assim como o selection sort.

public class InsertionSort {

 public static void sort(int arr[]) {
  int n = arr.length;
  for (int i = 1; i < n; ++i) {
   int k = arr[i];
   int j = i - 1;

   while (j >= 0 && arr[j] > k) {
    arr[j + 1] = arr[j];
    j = j - 1;
   }
   arr[j + 1] = k;
  }
 }

 public static void main(String args[]) {
  int arr[] = { 12, 11, 13, 5, 6 };
  
  System.out.println("Antes de ordenar");
  imprimir(arr);

  sort(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");

  System.out.println();
 }

}

Shell sort

Este algoritmo consiste em realizar trocas entre os elementos que estão posicionados a uma distância determinada. A distância inicial pode ser definida por d = n /  2 e a cada iteração diminuímos a essa distância, por exemplo, se você tem 10 elementos

iteração 1) d = 10 / 2 = 5;
iteração 2) d =  5 / 2 = 3;
iteração 3) d =  3 / 2 = 2
iteração 4) d =  2 / 2 = 1

Os elementos estarão ordenados quando a distância for menor ou igual a zero.

public class ShellSort {

 public static int ordenar(int arr[]) {
  int n = arr.length;

  for (int gap = n / 2; gap > 0; gap /= 2) {
   for (int i = gap; i < n; i += 1) {
    int temp = arr[i];

    int j;
    for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
     arr[j] = arr[j - gap];

    arr[j] = temp;
   }
  }
  return 0;
 }

 public static void main(String args[]) {
  int arr[] = { 12, 34, 54, 2, 3 };
  
  System.out.println("Antes de ordenar");
  imprimir(arr);

  ordenar(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }
}