Dúvida em hashcode e equals

13 respostas
T
import java.util.HashSet;  
      
   public class WrappedString    
   {     
       private String s;     
       public WrappedString(String s){ this.s = s;}

       public static void main(String args[]){

           HashSet<Object> hs = new HashSet<Object>();     
           WrappedString ws1 = new WrappedString("aardvark");     
           WrappedString ws2 = new WrappedString("aardvark");     
           String s1 = new String("aardvark");     
           String s2 = new String("aardvark");     
       
           System.out.println(hs.add(ws1));          
           System.out.println(hs.add(ws2));
           System.out.println(hs.add(s1));       
           System.out.println(hs.add(s2));
       
           System.out.println( hs.size() );     
       }     

  }

A) 0
B) 1
C) 2
D) 3
E) 4
F) Compilation fails
G) An exception is thrown at runtime

A resposta correta é a D. Porém, tenho uma dúvida. Acompanhem o raciocínio:

No primeiro hs.add ( hs.add(ws1) ), como não existe nenhum objeto dentro do conjunto ainda, ele é adicionado sem problema. No segundo hs.add ( hs.add(ws2) ) ele calcula primeiramente o hashcode. Será usado o hashcode da classe pertencente ao objeto que estou inserindo no HashMap, ou seja, será utilizado o hashcode da minha classe WrappedString. Porém, como eu não sobrescrevi o método hashcode, então o que será usado é o da implementação da classe Object. Na documentação da classe Object, está escrito:

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects.

Mas em primeiro lugar, eu não acho que essa informação é válida para 100% dos casos. Como hashcode retorna um int, temos que o número máximo de hashcodes permitidos são 2^32 = 4.294.967.296. Assim, imaginando um caso hipotético com 4.294.967.297 objetos do tipo WrappedString na memória (e considerando todos eles diferentes um do outro), temos que teremos pelo menos um hashcode repetido, mesmo sendo todos os objetos diferentes uns dos outros.

Voltando ao problema, considerando que o hashcode do objeto ws2 seja diferente do hashcode de ws1, então o objeto ws2 será inserido no HashSet também. Caso o hashcode de ws1 fosse igual ao hashcode de ws2, então o método equals seria chamado. Como a classe WrappedString não implementa o equals, será utilizado o equals da classe Object. Mas o equals da classe Object compara as referências dos objetos, que, neste caso, são diferentes. Então, mesmo que o hashcode de ws1 e ws2 sejam iguais, ws2 irá ser adicionado no HashSet pois o método equals irá retornar false.

Continuando, inserimos um objeto do tipo String (hs.add(s1) ). O hashcode chamado para o objeto s1 será o da classe String. Considerando que nem o hashcode de ws1 e nem o hashcode de ws2 são iguais ao hashcode de s1, então s1 será inserido no conjunto HashSet. Porém, aqui entra a minha dúvida: caso o hashcode de s1 fosse igual ao hashcode de ws1 por exemplo, o método equals seria utilizado. Mas desta vez, o método equals que será utilizado será o da classe String, pois o objeto (s1) que está sendo inserido é o da classe String. Assim, quando internamente s1 fosse comparado com ws1 ocorreria uma exceção! (por causa do cast inválido de WrappedString para String).

Esse caso não pode ocorrer? Caso esse caso ocorresse, então a alternativa G também estaria correta!!!

Eu errei em alguma parte do raciocínio?

13 Respostas

V

isso provavelmente não ocorrerá porque geralmente nas implementações de equals existe um teste para impedir o cast errado de objetos ex:

public boolean equals(Object o) {
 
  //verifica o casting
  if( ! (o instanceOf String) ) return false;
  ...

}

entendeu??? com isso não ocorrerá uma exceção…

V

bom, a respeito da hipótese de ter 4.294.967.297 objetos iguais na memória aí(paciência neh rsrsrsrs) um objeto vai ter que sair da lista… mas acho bem improvável ter um caso desse, mas é válido a discussão :slight_smile:

T

vmsb11:
isso provavelmente não ocorrerá porque geralmente nas implementações de equals existe um teste para impedir o cast errado de objetos ex:

public boolean equals(Object o) {
 
  //verifica o casting
  if( ! (o instanceOf String) ) return false;
  ...

}

entendeu??? com isso não ocorrerá uma exceção…

Entendi. Realmente acabei de confirmar isso olhando o código fonte da classe String. Para quem quiser, aqui está:

public boolean equals(Object anObject) { 1013 if (this == anObject) { 1014 return true; 1015 } 1016 if (anObject instanceof String) { 1017 String anotherString = (String)anObject; 1018 int n = count; 1019 if (n == anotherString.count) { 1020 char v1[] = value; 1021 char v2[] = anotherString.value; 1022 int i = offset; 1023 int j = anotherString.offset; 1024 while (n-- != 0) { 1025 if (v1[i++] != v2[j++]) 1026 return false; 1027 } 1028 return true; 1029 } 1030 } 1031 return false; 1032 }

Obrigado vmsb11 :slight_smile:

T
T
V

Legal, esse assunto é bom pra se discutir numa aula de estrutura de dados, mas para a prova não se preocupe com os detalhes porq na prova é importante saber como implementar corretamente o hashcode…

T

Mas esse realmente é um caso para se pensar… O exemplo que eu dei (com 4.294.967.297 objetos) é exagerado, mas eu acho que poderiam ocorrer dois hashs iguais muito antes desse valor, por exemplo, com 100 milhões de objetos…). Ou mesmo isso pode ocorrer com 2 objetos! (Se vc for a pessoa mais azarada do mundo). Então, eu acho que deve haver alguma coisa por trás disso tudo para não permitir tais casos…

Caso alguém saiba de alguma coisa, por favor, complemente aqui. Apesar de não cair um detalhe tão grande na certificação, acho interessante saber essas coisas…

V

acho que a jvm deve ter um mecanismo para gerar um código aletatório para cada objeto quando hashcode não é implementado, sobre o caso de termos 100 milhões de objetos na memória eu acho improvável por questões de memória…se vc ja tiver 5000 objetos na memória a jvm ja lança uma exceção rsrsrsrs… mas é óbvio que num máquina mais potente a história é diferente… se vc quiser tb pode olhar no site da sun la tem um material sobre as especificações da jvm, concerteza deve ter alguma coisa falando disso…

T

Acabei de ver aqui também que o método compareTo da interface Comparable NÃO faz checagem de tipo com o instanceof antes… É bom saber disso pois métodos como Arrays.sort usam o compareTo e, então, caso todos os objetos não sejam do mesmo tipo, uma ClassCastException será lançada…

Vejam, por exemplo, o compareTo da classe String:

public int compareTo(String anotherString) { 1175 int len1 = count; 1176 int len2 = anotherString.count; 1177 int n = Math.min(len1, len2); 1178 char v1[] = value; 1179 char v2[] = anotherString.value; 1180 int i = offset; 1181 int j = anotherString.offset; 1182 1183 if (i == j) { 1184 int k = i; 1185 int lim = n + i; 1186 while (k < lim) { 1187 char c1 = v1[k]; 1188 char c2 = v2[k]; 1189 if (c1 != c2) { 1190 return c1 - c2; 1191 } 1192 k++; 1193 } 1194 } else { 1195 while (n-- != 0) { 1196 char c1 = v1[i++]; 1197 char c2 = v2[j++]; 1198 if (c1 != c2) { 1199 return c1 - c2; 1200 } 1201 } 1202 } 1203 return len1 - len2; 1204 }

V

é exatamente, ou seja se no primeiro exercício vc estiver usando um treeset, seria lançada uma exceção porq vc estaria comparando tipos diferentes…

V

e tb a classe WrappedString não está implementando a interface Comparable…

andeb

Pera aí, você se confundiu em alguns pontos, vamos por partes:

O método compareTo da interface Comparable usa um tipo genérico, então nesse caso não vai gerar ClassCast porque você só pode passar uma String pra ele, não é igual ao equals() que você passa um Object (que consequentemente, pode ser uma String ou um Integer).

O método de hashcode() de Object é implementado nativamante para retornar um inteiro com base na posição da memória, sendo assim, quando acabar a memória não teremos dois objetos com o mesmo hash, mas sim um OutOfMemory hehe

O Arrays.sort() define explicitamente na sua domunetação que pode gerar ClassCast caso os valores do arrays não são mutualmente comparáveis, isso deve-se que seria muito caro verificar se todos os valores são mutualmente comparáveis, nesses casos, é preferível deixa rolar a exceção mesmo.

Leia a domentação do método hashcode(), não é necessariamente que dois métodos prozuzam false no equals() que eu preciso gerar dois hashcodes diferentes, basta ter consciência que isso pode prejudicar em tabelas hashs. O hashcode serve somente para definir em qual repositório o objeto será armanezado, o equals que é utilizado para definir se o método é igual, nesse exemplo, apesar de não ser recomendado fazer isso, ambos produziriam a saída 3:

class Foo {

        @Override
        public int hashCode() {
            return 1;
        }

    }


    class Bar {
      public static void main(String[] args) throws ScriptException, IOException {

        Map<Foo, Foo> tmp = new HashMap<Foo, Foo>();
        tmp.put(new Foo(), new Foo());
        tmp.put(new Foo(), new Foo());
        tmp.put(new Foo(), new Foo());
        System.out.println(tmp.size()); // retorna 3

        Set<Foo> tmp2 = new HashSet<Foo>();
        tmp2.add(new Foo());
        tmp2.add(new Foo());
        tmp2.add(new Foo());
        System.out.println(tmp2.size()); // retorna 3 também
      }
    }
pmlm

E qual é o problema? Não é o hash que diz se os objectos são iguais ou não, simplesmente torna o processo mais rápido, já que dois objectos iguais têm de ter o mesmo hash. O contrário não é verdade, ou seja, dois objectos com o mesmo hash podem ser diferentes.

Criado 22 de janeiro de 2010
Ultima resposta 23 de jan. de 2010
Respostas 13
Participantes 4