GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

Dúvida hashCode() e tabela Hash


#1

Salve galera, tudo beleza? Bom, já vou dizendo que sou novo aqui no fórum, então qualquer crítica será muito bem aceita.
Então, estou tendo dificuldades em entender o funcionamento do ‘hashCode()’ e da Tabela Hash, eu já entendi o conceito do ‘equals()’ que serve para checar se dois objetos são realmente iguais e etc, mas não estou conseguindo entender muito bem o funcionamento do 'hashCode();

  1. A tabela Hash possui vários vetores dentro que armazenam objetos que possuem valores hashCodes() semelhantes? tipo a do HashMap

  2. O valor inteiro gerado pelo hashCode() é o que determina o índice em que o objeto será armazenado dentro da tabela Hash? Ou a tabela possui infinitos valores, e cada ‘intervalo’ destes valores é reservado para hashCodes() semelhantes?

  3. A Tabela Hash realmente possui vetores dentro??

Muito obrigado galera!!


#2

Boa noite amigo.

O hashCode serve para verificar se objetos são iguais.

cliente.hashCode() == cliente2.hashCode();
cliente.equals(cliente2);

basicamente é a mesma coisa, o hash transforma um objeto em um valor númerico e o equals verifica todos os seus atributos um a um retornando um boolean.


#3

Então o valor inteiro gerado pelo hashCode() seria o índice em que o objeto pode ser armazenado dentro de uma tabela hash?


#4

Boa noite amigo

Tabelas Hash não tem nada a ver com o hashCode, tabelas hash são basicamente vetores que armazenam valores utilizando chaves para acessa-los.

 Integer[] valores = {1,2,3};
 System.out.println(valores[3]);
 //-------------------------------------
 Map<String, Object> map = new HashMap();
 map.put("teste1", imagem);
 map.put("teste2", "texto");
 map.put("teste3", 3L);
 System.out.println(map.get("teste3"));

Existem vários tipos de tabelas hash, mas tomas seguem essa linha de raciocínio. Agora, se você quiser formar uma tabela hash usando o hashcode como chave, não tem problema nenhum.


#5

Acho que entendi, então o HashMap faz uso de uma tabela hash, e cada chave(key) serve para acessar um vetor dentro desta tabela? é isso? então posso criar mais de um valor usando a mesma key?

Ex:

Map<String, String> mapa = new HashMap();
mapa.put(“teste1”,“valor1”);
mapa.put(“teste1”,“valor2”);

//“teste1” seria a chave de acesso para um vetor?

Ou no caso, tabela Hash seria um vetor com valores do tamanho que eu precisar que reservam determinados índices para acesso das keys?


#6

ñ…cada chave é única


#7

Um cuidado com isso é que o hashCode nao garante igualdade de objetos.
As strings “FB” e “Ea” por exemplo compartilham o mesmo hashCode 2236.

Com o hashCode você pode ter certeza que dois objetos sao diferentes (se os hashCodes sao diferentes) mas nao que sao iguais.


#8

Por isto mesmo perceba que eu estou falando de objetos e não de variáveis, mas obrigado pela contribuição, não me lembrei de dar este alerta.


#9

Eu usei strings como exemplo, por ser simples, mas qualquer objeto tem o mesmo risco.
Aliás, strings sao objetos também!


#10

A implementação do método hashCode exige algumas regras:

  • se uma classe sobrescreve o equals, ela deve sobrescrever o hashCode também;

  • se ambos são sobrescritos, equals e hashCode devem usar o mesmo conjunto de campos;

  • se o equals entre dois objetos é true, o hashCode desses objetos deve ser o mesmo;

  • se o objeto for imutável, então o hashCode pode ser inicializado através de lazy initialization e ser guardado em cache;

Isso vai depender de como a estrutura de dados foi implementada.
As classes HashMap e Hashtable do Java por exemplo possuem um atributo que é um array de um tipo de dado que possui dois atributos, a chave e o valor daquela chave.

Ele é usado no algoritmo que determina o índice, se você olhar o código fonte da classe HashMap e da classe Hashtable, verá que elas usam algoritmos diferentes, mas em ambas o hashCode é utilizado no cálculo.

Não, pelo menos não no caso do HasMap e Hashtable.

Sim, é como originalmente a estrutura foi proposta.
A classe HashMap possui um atributo Node<K,V>[] table
A classe Hashtable possui um atributo Entry<?,?>[] table

Na verdade é o hashCode que tem a ver com Tabelas Hash. Esse método foi declarado na classe Object justamente para facilitar a implementação de Tabelas Hash. A própria documentação diz isso.

No Java não foram implementados dessa forma, mas você poderia implementar algo nesse sentido.
Sugiro que dê uma olhada no fonte das classes HashMap e Hashtable.

Não, cada chave armazena um valor. Se você quer armazenar mais de um valor pra cada chave, então na realidade o seu valor terá de ser uma coleção de objetos, aí a cada inserção, você obtém a coleção para a chave informada e adiciona um elemento nela.


#11

Obrigado a todos que me ajudaram galera, agora eu realmente entendi

Um bom dia a todos :smile: