Kathy Sierra diz em seu livro que quanto mais único for o hashCode de um objeto mais rápido é o processo de pesquisa em Collection.
Mas, levando-se ao extremo, se tivermos um hashCode diferente para cada objeto não é igual a termos 1 hashCode para todos os objetos?
fui claro?
Como assim?
sim…temos um hash code para cada objeto diferente que for criado…a não ser que eles sejam iguais…>
não é?
Não. Podem existir 2 objetos diferentes com 1 mesmo hashCode. Esse é o cerne da questão…
Se eu entendi, vc quis dizer que ter um hashcode diferente pra cada objeto é o mesmo que ter um mesmo hashcode igual para todos eles, isso?
Bom, se for isso, nao é a mesma coisa nao, muito pelo contrario. A ideia basica de uma tabela de hash é construir um vetor de listas ligadas. Cada indice do vetor é o hashcode. Quando dois objetos tem codigos iguais, sao armazenados na mesma posição do vetor (q aponta pra uma lista ligada);
Exemplificando:
Imagine que vc tem 10 objetos. Os 4 1os tem codigo = 1 e os demais tem codigos diferentes entre si. Se vc faz uma busca na tabela pelo o codigo 4, ele vai na posição 4 (ou 3) do vetor e ver pra qual lista ele aponta. Chegando na lista, ele vai achar 4 objetos. Ou seja, ele terá que ver qual desses 4 objetos é o que vc quer.
Se essa lista soh tem 1 objeto, q é o caso onde um objeto tem hashcode unico, ele nao precisa verificar nada.
Isto é, se todos seus objetos tem hashcodes diferentes, vc só precisa saber em que lista ele tá. Se todos os objetos tem mesmo codigo, além de achar a lista, vc tbm terá que achar o objeto dentro dessa lista, ja q todos eles estarão na mesma.
Xi cara,
Acho que o autor desse livro fumou pamonha estragada (de doce).
No javadoc do Object no método equals temos
Note that it is generally necessary to override the <tt>hashCode</tt>
method whenever this method is overridden, so as to maintain the
general contract for the <tt>hashCode</tt> method, which states
that equal objects must have equal hash codes.
equal objects must have equal hash codes.
:arrow: Objetos iguais devem ter hash codes iguais.
:arrow: Hash codes diferentes implica em objetos diferentes.
:arrow: Objetos diferentes podem ter, apesar de não recomendável, hash codes iguais.
Escrevi uma vez sobre isso no meu blog: http://joseoliveira.com/blog/2005/12/06/contrato-entre-equals-e-hashcode/
[quote=hashcode]Xi cara,
Acho que o autor desse livro fumou pamonha estragada (de doce).
No javadoc do Object no método equals temos
Note that it is generally necessary to override the <tt>hashCode</tt>
method whenever this method is overridden, so as to maintain the
general contract for the <tt>hashCode</tt> method, which states
that equal objects must have equal hash codes.
equal objects must have equal hash codes.
[/quote]
Parece estranho né? até hoje não entendi muito sobre como funciona esse contrato…
As vezes você reenscreve seu equals mas o objeto não precisa necessariamente ter o mesmo hash code…pelo menos para mim soa estranho isso!!(apesar de eu saber que é util o hash code para fazer sort de Hashtables e etc)
[quote=ZehOliveira]:arrow: Objetos iguais devem ter hash codes iguais.
:arrow: Hash codes diferentes implica em objetos diferentes.
:arrow: Objetos diferentes podem ter, apesar de não recomendável, hash codes iguais.
Escrevi uma vez sobre isso no meu blog: http://joseoliveira.com/blog/2005/12/06/contrato-entre-equals-e-hashcode/[/quote]
Exato, se os objetos sao iguais, nao tem pq criar hshcodes diferentes, ja que qq um deles serve. É o mesmo q vc adicionar numa lista 5 coisas iguais e depois pegar um elemento dela: qq um serve.
Agora se vc tem uma lista com objetos diferentes, quando for procura-la, terá q compara-los pra ver qual vc quer.
bbviana, acho que vc foi o único que entendeu minha dúvida.
Mas sua explicação é justamente o meu questionamento.
Partindo-se do princípio que buscas em Collection possuem 2 etapas (primeiro a pesquisa pelo hashcode, e depois a pesquisa entre todos os objetos que possuem esse hashcode, através do método equals())
Se existirem 1000 objetos, com 1000 hashcodes diferentes. Ao fazer uma pesquisa na Collection teria que ser realizado uma busca nesses 1000 hashcodes, para então achar o objeto procurado.
Por outro lado, se existirem 1000 objetos com apenas 1 hashcode, a primeira etapa da busca não ocorreria, já que temos apenas 1 hashcode. Mas teríamos que pesquisar entre os nossos 1000 objetos…
certo? do mesmo jeito faríamos uma pesquisa entre 1000 elementos?! viajei?
[quote=felipe_gdr]bbviana, acho que vc foi o único que entendeu minha dúvida.
Mas sua explicação é justamente o meu questionamento.
Partindo-se do princípio que buscas em Collection possuem 2 etapas (primeiro a pesquisa pelo hashcode, e depois a pesquisa entre todos os objetos que possuem esse hashcode, através do método equals())
Se existirem 1000 objetos, com 1000 hashcodes diferentes. Ao fazer uma pesquisa na Collection teria que ser realizado uma busca nesses 1000 hashcodes, para então achar o objeto procurado.
Por outro lado, se existirem 1000 objetos com apenas 1 hashcode, a primeira etapa da busca não ocorreria, já que temos apenas 1 hashcode. Mas teríamos que pesquisar entre os nossos 1000 objetos…
certo? do mesmo jeito faríamos uma pesquisa entre 1000 elementos?! viajei?[/quote]
É que não é bem assim que o hashcode é implementado. Não pense em Collection, pense em vetor(array) Um vetor com ponteiros para listas(ligadas). Vou tentar desenhar:
[0] -> [L0]-> [L0]
[1] -> [L1]-> [L1]-> [L1]-> [L1]-> [L1]-> [L1]
[2] -> [L2]-> [L2]-> [L2]-> [L2] -> [L2]
[3]-> [L3]
Na vertical, temos o vetor, com indices de 0 a 3, que sao os hashcodes. Cada posição desse vetor aponta para uma lista L.
O hashcode funciona assim: Descoberto o hshcode, vc busca no vetor o indice correspondente. Se seu hashcode for 2, vc vai na posição 2 do vetor. Essa posição apontará pra uma lista, no caso a L2. Veja que a L2 tem 5 elementos. Se esses 5 elementos forem diferentes, vc terá q descobrir, comparando um a um, qual deles vc quer. Mas se a lista tiver apenas um elemento, no caso da 3, vc nao precisa comparar nada. Do mesmo modo se vc tiver elementos iguais na lista. Se sao iguais, qq um serve.
Veja a diferença:
Todos os elementos (dieferentes) com o mesmo hashcode:
[0] -> [L0]-> [L0]-> [L0]-> [L0]-> [L0]-> [L0]
Uma posição do vetor aponta pra uma lista gigante. Vc perderá muito tempo comparando
os elementos na lista.
Todo elemento diferente tem hashcode diferente:
[0]->[L0]
[1]->[L1]
[2]->[L2]
[3]->[L3]
[4]->[L4]
Vc tem um vetor grande, mas apontando pra uma lista com um elemento só. Entao vc soh precisa achar o indice do vetor correspondente.
Só pra finalizar: fazer uma busca num vetor é extremamente rapido (ele foi feito pra isso), ao passo q fazer comparações em listas é bem demorado.
Bom, nao sei se deu pra responder.
Esse é o ponto, valeu!
ps.: Vector é um tipo de Collection
Esse é o ponto, valeu!
ps.: Vector é um tipo de Collection[/quote]
É o vicio do C: qdo eu digo vetor, quero dizer array. Nao me refiro á classe Vector.
Hashing serve para poder separar os objetos em várias cestas distintas.
A conta para descobrir qual um objeto pertence demora o mesmo tempo independe de existirem 2 ou 2 bilhões de cestas. O processo de olhar todos objetos de uma cesta leva tempo proporcional ao número de objetos nela, pois todos tem que ser olhados.
Vale lembra uma coisa, cada valor do hashcode tem sua cesta, e sim que escolhemos um grupo de hashcodes por cesta. Por exemplo, temos 2 cestas, na primeira vão os hashcodes pares, na outro os ímpares.