Tabelas Hash - Exemplo em Java
Afluentes: Estrutura de Dados
Classe Contato
Vamos trabalhar com tabelas Hash gerenciando um tipo específico de dado definido pelo usuário que chamamos aqui de Contato. A Classe contato tem três atributos, o código, o nome e o telefone. O Código é o atributo usado para fazer o cálculo do operador da tabela Hash. Contudo, poderia-se utilizar qualquer atributo e qualquer outro cálculo.
1public class Contato { // Classe Contato
2 int codigo; // Código do contato
3 String nome; // Nome do contato
4 String telefone; // Telefone do contato
5
6 Contato(int codigo, String nome, String telefone) { // Construtor com parâmetros
7 this.codigo = codigo; // Inicializa o atributo codigo
8 this.nome = nome; // Inicializa o atributo nome
9 this.telefone = telefone; // Inicializa o atributo telefone
10 }
11
12 public String toString() { // Sobrescreve o metodo toString
13 return "(" + codigo + ", " + nome + ")"; // REtorna o código e o nome
14 }
15};
Classe No
Nosso nó trabalha aqui especificamente com a classe Contato. Poderíamos trabalhar com generics em Java, o que deixaria nossa lista mais genérica, mas não vem ao caso aqui deixar nosso código mais complexo. Para nosso aprendizado em tabelas Hash, quanto mais simples estiver o código, melhor.
1public class No { // Classe No
2 Contato info; // Atributo info do tipo Contato
3 No proximo; // Ponteiro para o próximo No
4}
Classe Lista
Veja que implementamos aqui uma lista encadeada simples bastante simplificada. Ela possui apenas o método inserir, que insere um elemento contato no início, um método buscar, com base no código do contato, para varrer a lista até encontrar o contato que possua tal código e o método toString sobrescrito para mostrar os elementos da lista.
1class Lista { // Classe Lista
2 No inicio; // Ponteiro para o inicio da Lista
3 int tamanho; // Tamanho da lista
4
5 public void inserir(Contato info) { // Metodo para inserir no inicio
6 No no = new No(); // Cria um No
7 no.info = info; // Atribui a informação ao no
8 no.proximo = inicio; // O ponteiro próximo do no inserido aponta para o inicio
9 inicio = no; // O inicio passa a ser esse novo no
10 tamanho++; // Incrementa o tamanho
11 }
12
13 public Contato buscar(int codigo) { // Metodo buscar pelo codigo
14 No no = inicio; // Vai para o inicio da lista
15 while (no != null) { // Enquanto o no nao for nulo
16 if (no.info.codigo == codigo) { // Se o codigo do no for igual ao parametro passado
17 return no.info; // retorna a informacao do tipo Codigo
18 }
19 no = no.proximo; // Vai para o proximo no
20 }
21 return null;
22 }
23
24 public String toString() { // Sobrescreve o metodo toString
25 String out = ""; // Cria uma string vazia para retorno
26 No no = inicio; // Vai para o inicio da lista
27 while (no != null) { // Enquanto o no for diferente de nulo
28 out += no.info + " "; // Adiciona a string a informacao
29 no = no.proximo; // Vai para o proximo no
30 }
31 return out; // Retorna a string
32 }
33}
Classe Hash
Aqui implementamos nossa tabela Hash. Veja que temos um vetor de listas. No nosso main, vamos criar um vetor com 4 elementos, conforme o valor do nosso operador, pois estamos trabalhando com o resto da divisão para definir em que posição do vetor vamos inserir nosso contato e com base no código dele. Veja que cada posição do vetor tem uma lista que possui sua própria forma de gerenciamento, já mostrada acima.
1public class Hash { // Classe Hash
2 int operador; // Atributo operador
3 Lista[] vetor; // Vetor de Listas
4
5 Hash(int operador) { // Construtor iniciando com um operador
6 this.operador = operador; // Inicializa o operador
7 vetor = new Lista[operador]; // Inicializa o vetor de Listas
8 for (int i = 0; i < operador; i++) { // Para cada posicao no vetor
9 vetor[i] = new Lista(); // Inicializa a Lista daquela posicao do vetor
10 }
11 }
12
13 void inserir(Contato contato) { // Metodo para inserir um contato
14 int chave = contato.codigo % operador; // Posicao = resto do codigo /operador
15 vetor[chave].inserir(contato); // Insere o contato naquela lista
16 }
17
18 Contato buscar(int codigo) { // Metodo buscar pelo codigo
19 return vetor[codigo % operador].buscar(codigo); // Busca apenas na lista especifica
20 }
21
22 public String toString() { // Sobrescreve o metodo toString
23 String out = ""; // Cria uma string de saida
24 for(int i = 0; i < operador; i++) { // Para cada posicao no vetor de Listas
25 out += "" + i + ": "; // adiciona uma string representando a Lista
26 out += vetor[i % operador] + "\n";
27 }
28 return out; // Retorna a String
29 }
30}
Classe Main
Na função principal do nosso programa, apenas inserimos contatos na nossa tabela hash e mandamos imprimir ela.
1public class Main { // Classe Main
2 public static void main(String [] args) { // Metodo main
3 Hash hash = new Hash(4); // Cria uma tabela Hash com operador 4
4 hash.inserir(new Contato(2, "Saulo", "99990000")); // Insere n elementos
5 hash.inserir(new Contato(6, "Joao", "99009900"));
6 hash.inserir(new Contato(13, "Marta", "99778877"));
7 hash.inserir(new Contato(12, "Roberta", "87872222"));
8 hash.inserir(new Contato(7, "Maria", "77887777"));
9
10 System.out.println(hash); // Imprime a tabela Hash e suas listas
11 }
12}
Resultado da Execução
Observe no resultado que cada posição do nosso vetor tem uma lista. O código de cada elemento da lista é calculado conforme o resto da divisão do código pelo operador.
0: (12, Roberta) 1: (13, Marta) 2: (6, Joao) (2, Saulo) 3: (7, Maria)
