2012-03-19 19 views
6

Zastanawiam się, czy domyślna implementacja Java Hashtable#hashCode() jest zepsuta, gdy Hashtable zawiera tylko wpisy z identycznymi kluczami i wartościami na parę.Implementacja Java HashTable # hashCode() jest zepsuta?

Patrz na przykład następujący wniosek:

public class HashtableHash { 
    public static void main(final String[] args) { 
     final Hashtable<String, String> ht = new Hashtable<String, String>(); 

     final int h1 = ht.hashCode(); 
     System.out.println(h1); // output is 0 

     ht.put("Test", "Test"); 

     final int h2 = ht.hashCode(); 
     System.out.println(h2); // output is 0 ?!? 

     // Hashtable#hashCode() uses this algorithm to calculate hash code 
     // of every element: 
     // 
     // h += e.key.hashCode()^e.value.hashCode() 
     // 
     // The result of XOR on identical hash codes is always 0 
     // (because all bits are equal) 

     ht.put("Test2", "Hello world"); 

     final int h3 = ht.hashCode(); 
     System.out.println(h3); // output is some hash code 
    } 
} 

Kod skrótu dla pustego Hashtable jest 0. Po klawiszem "Test" i wartości "Test" został dodany do Hastable kod hash jeszcze 0.

problemem jest to, że w hashCode() metody Hashtable jest kod hash każdego wejścia jest obliczana i dodany do kodu skrótu następująco

h += e.key.hashCode()^e.value.hashCode() 

Jednak XOR na identycznych kodach hash (co ma miejsce w przypadku identycznych ciągów znaków) jest zawsze równe 0. Zatem wpisy z identycznymi kluczami i wartościami nie są częścią kodu skrótu Hashtable.

Ta implementacja jest imho zepsuta, ponieważ tablica Hashtable faktycznie się zmieniła. Nie powinno mieć znaczenia, czy klucz i wartość są identyczne.

+2

Zastanawiam się, dlaczego zostało to odrzucone, ponieważ jest to uzasadnione pytanie i może uratować trochę problemów. Szukałem wiele godzin, aby znaleźć błąd, który został spowodowany przez to zachowanie. –

+2

Nie możesz * polegać na innym haśle, ponieważ obiekt jest inny. Powiedziałbyś, że hashCode również jest zepsuty, jeśli dodaję dwa zupełnie różne obiekty, a hashCode również pozostanie taki sam? W takim przypadku każda możliwa implementacja hashcode zostanie przerwana, jeśli wszechświat możliwych obiektów jest większy niż 2^32 .. – Voo

+0

To więcej obserwacji niż pytania. (Chociaż nie moja lekcja). –

Odpowiedz

6

Z dokumentacji na hashCode;

jest nie wymagane, jeżeli dwa obiekty są nierówne metodą równe (java.lang.Object), a następnie wywołanie metody hashCode na każdego z dwóch przedmiotów musi wytwarzać różne wyniki całkowite. Programista powinien jednak zdawać sobie sprawę z tego, że wygenerowanie różnych wyników całkowitych dla nierównych obiektów może poprawić wydajność elementów hashtables z .

Innymi słowy, złe wdrożenie - być może. Zepsuty - niezgodny ze specyfikacją.

5

Nie jest uszkodzony, działa zgodnie z założeniami i reklamą. Kod skrótu dwóch równań Map nie wymaga równości dwóch wartości Map.

1

Jedynym wymaganiem dla hashCode jest to, że jeśli dwa obiekty są równe, to ich kody skrótu muszą być równe. Tak więc

public int hashCode() { 
    return 123; 
} 

jest całkowicie poprawne, chociaż nie optymalne.