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
Livro: Estruturas De Dados E Algoritmos em Java
