Conheça a verdade - Tabelas Hash(sem colisão)

Olá amigos do Preciso Estudar Sempre, meu nome é João Paulo e minha paixão é estudar. Hoje entraremos, mais uma vez, no grande reino das estruturas de dados. Para que possamos falar sobre esse assunto, é necessário que você, caro leitor, já possua conhecimentos sobre Java e OO.

Caso você precise muito baixar o projeto agora, clique aqui mas, se você aguenta mais um pouquinho, leia o post e baixe o projeto no link que tem lá embaixo, até porque dá uma trabalheira imensa trazer conteúdo de qualidade para vocês.

Voltando .... Imagine a seguinte situação: você possui um array com N elementos e quer procurar um elemento qualquer sendo que, você não sabe aonde ele está.

O que você faz ????

A primeira coisa que vem à nossa cabeça é uma busca sequencial, ou seja, verificar uma posição após a outra. Contudo, o custo de performance dessa busca é equivalente ao tamanho do array.

Nesse momento você pensa: "Ué, mas não existe a tal da busca binária, aquela que corta o array ao meio e elimina a outra metade ?"

Então, realmente existe a busca binária que faz isso tudo aí que você pensou mas, para a busca binária funcionar, ela tem como pré-requisito a ordenação do vetor, ou seja, você terá o custo da ordenação e da pesquisa. O ideal é podemos ter acesso direto ao elemento dentro do array.

É importante citar que nem sempre conhecemos a posição exata de um elemento dentro de um array logo, o acesso direto não é possível. Para tal, precisamos calcular essa posição, essa é a chave para a solução.

Como vamos calcular isso ?! E agora !?

Para que possamos contornar esse problema, precisamos sair da nossa zona de conforto, ou seja, dos arrays comuns que já conhecemos e precisamos aprender uma nova estrutura de dados, a tabela hash. Na tabela hash, não trabalhamos mais da forma tradicional, ou seja, de forma sequencial. Agora iremos espalhar nossos dados dentro de um array. Sim, você não leu errado, nós iremos espalhar nossos dados dentro de um array e, ainda te digo que isso permite que tenhamos o tão sonhado acesso direto.

Figura 1 - Comparativo entre tabela hash e lista

Nesse momento, imagino que você esteja realmente assustado.

Mas como iremos realizar esse espalhamento ? Vamos usar escolha randômica ? A resposta é não. Para conseguirmos espalhar com eficiência nossos dados, iremos utilizar uma função de espalhamento.

A função de espalhamento gera a posição em que vamos inserir nosso valor dentro do array. Essa posição é gerada através de uma chave passada como parâmetro. Cada chave deve ser única porque, estamos construindo uma tabela de hash sem colisões, visando um ambiente onde cada chave gere uma posição diferente. Caso existam chaves iguais, iremos gerar colisões, ou seja, duas inserções para uma mesma posição. Após nossa função de espalhamento ter sido executada, nosso acesso será reduzido para O(1).

Para uma função ser considerada uma função de espalhamento, ela deve preencher alguns pontos obrigatórios:

• Ser simples e barata de se calcular.
• Garantir que chaves diferentes produzam posições diferentes.
• Garantir que não há preferência por posições

Existem diversos tipos de funções de espalhamento já conhecidas, vou listar algumas:

• Método da divisão (iremos usar esta)
• Método da multiplicação
• Método da dobra
• String como chave

Não explicarei como funciona cada função porque iremos estender muito nosso post e você ficará cansado. Caso as funções de espalhamento tenham gerado em você um grande interesse, fique tranquilo pois, farei um post exclusivo para isso.

Já entendemos tudo o que precisamos entender para ir para prática. Então, vamos ?

Crie a classe Aluno.

 public class Aluno {  
      private int matricula;  
      private String nome;  
      private float nota1;  
      private float nota2;  
      private float nota3;  
      public Aluno(int matricula, String nome, float nota1, float nota2,  
                float nota3) {  
           super();  
           this.matricula = matricula;  
           this.nome = nome;  
           this.nota1 = nota1;  
           this.nota2 = nota2;  
           this.nota3 = nota3;  
      }  
      //gets e sets  
 }  

A classe Aluno é uma classe simples, não preciso me estender em explicações sobre ela. Próximo passo.

Crie a classe HashTable.

 public class HashTable<T> {  
      private int qtd;  
      private int size;  
      private T[] objs;  
      private Set<Integer> keys;  
      public HashTable(int size) {  
           if(size == 0){  
                throw new IllegalArgumentException("O tamanho deve ser maior que 0");  
           }  
           this.size = size;  
           this.criarHashTable();  
      }  
      private void criarHashTable(){  
           this.objs = (T[]) new Object[this.size];  
           this.keys = new HashSet<Integer>();  
      }  
      public void add(T obj, int key){  
           if(this.qtd == this.size){  
                throw new IllegalStateException("Tabela cheia.");  
           }  
           int pos = this.chaveDivisao(key);  
           this.keys.add(key);  
           objs[pos] = obj;  
           qtd++;  
      }  
      private int chaveDivisao(int key) {  
           return (key & 0x7FFFFFFF) % size;  
      }  
      public T get(int key){  
           if(objs.length == 0){  
                return null;  
           }  
           int pos = this.chaveDivisao(key);  
           if(objs[pos] == null){  
                return null;  
           }  
           return objs[pos];  
      }  
      public T remove(int key){  
           if(objs.length == 0){  
                return null;  
           }  
           int pos = this.chaveDivisao(key);  
           if(objs[pos] == null){  
                return null;  
           } else {  
                T obj = objs[pos];  
                objs[pos] = null;  
                qtd--;  
                return obj;  
           }  
      }  
      public int size(){  
           return this.qtd;  
      }  
      public boolean isEmpty(){  
           return this.qtd == 0 ? true : false;  
      }  
      public Set keys(){  
           return this.keys;  
      }  
 }  

Vou ser pontual nas minhas explicações. Precisamos entender primeiramente o método criarHashTable(). Esse método é simples, ele inicia o array interno, o Set de keys interno e, é chamado dentro do construtor da HashTable. O Set de chaves foi criado visando a obtenção das mesmas para iteração de valores.

Note que o construtor da classe acima recebe um parâmetro o qual, representa o tamanho total da nossa HashTable. Além dos atributos objs e keys os quais, já comentamos no parágrafo acima, também temos os atributos qtd e size os quais, representam respectivamente, a quantidade de elementos presente no array e o tamanho total do array.

IMPORTANTE: Ao escolher o tamanho da HashTable, dê preferência a números primos pois, reduzem a probabilidade de colisões, mesmo a função de espalhamento não sendo muito eficaz. Caso você escolha um tamanho que seja potência de dois, a velocidade da HashTable será aprimorada mas a probabilidade de colisões pode aumentar caso a função de espalhamento seja muito simples.

A função add trabalha de forma bem simples. Ela calcula a posição baseada na chave a qual, é passada como parâmetro, insere o elemento naquela posição e incrementa o contador. A função remove trabalha de forma semelhante mas, antes de remover, verifica se existe algum valor naquela posição do array. Caso haja, remove o elemento, decrementa o contador e retorna o elemento removido.

A função get calcula a posição do elemento procurado através da chave passada e retorna o valor contido dentro do array naquela posição.

Uma das vantagens da HashTable, é que ela é muito fácil de se implementar.

Crie a classe Principal.

 public class Principal {  
      public static void main(String[] args) {  
           Aluno aluno1 = new Aluno(259379, "João Paulo Maida", 10, 7, 8);  
           Aluno aluno2 = new Aluno(1145, "Bruno Souza", 8, 9, 3);  
           Aluno aluno3 = new Aluno(55712, "Raphael Marques da Silva", 6, 7, 1);  
           Aluno aluno4 = new Aluno(19, "José da Silva", 1, 2, 3);  
           Aluno aluno5 = new Aluno(4754, "Luís Marcelo", 8, 5, 10);  
           Aluno aluno6 = new Aluno(4753, "Nathan Paulo Souza", 8, 5, 10);  
           Aluno aluno7 = new Aluno(1, "Beatriz Luana Campos", 7, 1, 2);  
           Aluno aluno8 = new Aluno(32, "Isadora Fernanda Monteiro", 6, 7, 7.5f);  
           Aluno aluno9 = new Aluno(0, "Marina Bruna da Silva", 2.5f, 3.5f, 8);  
           Aluno aluno10 = new Aluno(896358, "Levi Murilo Souza", 4.5f, 3, 9.7f);  
           
           HashTable<Aluno> hashTable = new HashTable<Aluno>(2048);  
           hashTable.add(aluno1, aluno1.getMatricula());  
           hashTable.add(aluno2, aluno2.getMatricula());  
           hashTable.add(aluno3, aluno3.getMatricula());  
           hashTable.add(aluno4, aluno4.getMatricula());  
           hashTable.add(aluno5, aluno5.getMatricula());  
           hashTable.add(aluno6, aluno6.getMatricula());  
           hashTable.add(aluno7, aluno7.getMatricula());  
           hashTable.add(aluno8, aluno8.getMatricula());  
           hashTable.add(aluno9, aluno9.getMatricula());  
           hashTable.add(aluno10, aluno10.getMatricula());  
           
           Aluno alunoRemovido = hashTable.remove(aluno1.getMatricula());  
           System.out.println(hashTable.size());  
           Aluno alunoRecuperado = hashTable.get(111);  
           System.out.println(alunoRecuperado);  
           Aluno alunoRecuperado2 = hashTable.get(55712);  
           
           System.out.println("Nome: " + alunoRecuperado2.getNome());  
           System.out.println("Matrícula: " + alunoRecuperado2.getMatricula());  
           System.out.println("Notas: " + alunoRecuperado2.getNota1() + "," + alunoRecuperado2.getNota2() + "," + alunoRecuperado2.getNota3());  
           System.out.println(hashTable.keys());  
      }  
 }  

A classe Principal só cria alunos e utiliza nossa API.

Pronto !! Chegamos ao fim de mais um post !!!!

Para baixar o projeto, clique aqui.

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários ou na nossa página do facebook.

Facebook: https://www.facebook.com/precisoestudarsempre/

Referências:
Aula 89 - Tabela Hash - Definição - https://www.youtube.com/watch?v=njkANXEMHTY
Aula 90 - Tabela Hash - Implementação - https://www.youtube.com/watch?v=K40yG9bmVZ4

Aula 91 - Tabela Hash - Criando e Destruindo a Tabela - https://www.youtube.com/watch?v=X55Ku_Mpw5g
Aula 92 - Função de Hashing - https://www.youtube.com/watch?v=o0TXB3QPOWY

Aula 93 - Tabela Hash - Inserção e busca sem tratamento de colisões -https://www.youtube.com/watch?v=sYKarxRQ_-g

Leia Mais ››