Wchodzenie w szarą strefę „on / off topic”, ale konieczne, aby wyeliminować nieporozumienia dotyczące sugestii Oscara Reyesa, że więcej zderzeń z haszowaniem jest dobrą rzeczą, ponieważ zmniejsza liczbę elementów w HashMap. Mogę źle zrozumieć, co mówi Oscar, ale nie wydaje mi się, że jestem jedyny: kdgregory, delfuego, Nash0 i wszyscy zdaje się mieć to samo (błędne) zrozumienie.
Jeśli rozumiem, co mówi Oscar o tej samej klasie z tym samym hashcode, proponuje, aby tylko jedna instancja klasy z podanym hashcode została wstawiona do HashMap. Na przykład, jeśli mam wystąpienie SomeClass z kodem skrótu 1 i drugie wystąpienie SomeClass z kodem skrótu 1, wstawiane jest tylko jedno wystąpienie SomeClass.
Przykład wklejanego kodu Java pod adresem http://pastebin.com/f20af40b9 wydaje się wskazywać, że powyższe poprawnie podsumowuje to, co proponuje Oscar.
Niezależnie od jakiegokolwiek zrozumienia lub nieporozumienia, dzieje się tak, że różne instancje tej samej klasy nie są wstawiane tylko raz do HashMap, jeśli mają ten sam hashcode - nie dopóki nie zostanie ustalone, czy klucze są równe, czy nie. Kontrakt z hashcode wymaga, aby równe obiekty miały ten sam hashcode; jednak nie wymaga, aby nierówne obiekty miały różne hashcodes (chociaż może to być pożądane z innych powodów) [1].
Poniżej znajduje się przykład pastebin.com/f20af40b9 (do którego Oscar odwołuje się co najmniej dwukrotnie), ale został on nieco zmodyfikowany, aby używać asercji JUnit zamiast printlines. Ten przykład służy do wspierania propozycji, że te same kody skrótów powodują kolizje, a gdy klasy są takie same, tworzony jest tylko jeden wpis (np. Tylko jeden ciąg znaków w tym konkretnym przypadku):
@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
String s = new String("ese");
String ese = new String("ese");
// same hash right?
assertEquals(s.hashCode(), ese.hashCode());
// same class
assertEquals(s.getClass(), ese.getClass());
// AND equal
assertTrue(s.equals(ese));
Map map = new HashMap();
map.put(s, 1);
map.put(ese, 2);
SomeClass some = new SomeClass();
// still same hash right?
assertEquals(s.hashCode(), ese.hashCode());
assertEquals(s.hashCode(), some.hashCode());
map.put(some, 3);
// what would we get?
assertEquals(2, map.size());
assertEquals(2, map.get("ese"));
assertEquals(3, map.get(some));
assertTrue(s.equals(ese) && s.equals("ese"));
}
class SomeClass {
public int hashCode() {
return 100727;
}
}
Jednak hashcode nie jest kompletną historią. To, czego przykład pastebin pomija, to fakt, że oba si esesą równe: oba są łańcuchem „ese”. Zatem wstawianie lub pobieranie zawartości mapy przy użyciu klucza slub eselub "ese"jako klucza jest równoważne, ponieważ s.equals(ese) && s.equals("ese").
Drugi test dowodzi, że błędem jest stwierdzić, że identyczne hashcodes na tej samej klasy jest powód klucz -> wartość s -> 1jest zastępowane przez ese -> 2kiedy map.put(ese, 2)nazywa się w jednym teście. W teście dwa, si esenadal mają taką samą hashcode (jak zweryfikowane assertEquals(s.hashCode(), ese.hashCode());) i są tej samej klasy. Jednak si esesą to MyStringinstancje w tym teście, a nie Stringinstancje Javy - jedyną różnicą istotną dla tego testu jest równość: String s equals String esew teście pierwszym powyżej, podczas gdy MyStrings s does not equal MyString esew teście drugim:
@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
MyString s = new MyString("ese");
MyString ese = new MyString("ese");
// same hash right?
assertEquals(s.hashCode(), ese.hashCode());
// same class
assertEquals(s.getClass(), ese.getClass());
// BUT not equal
assertFalse(s.equals(ese));
Map map = new HashMap();
map.put(s, 1);
map.put(ese, 2);
SomeClass some = new SomeClass();
// still same hash right?
assertEquals(s.hashCode(), ese.hashCode());
assertEquals(s.hashCode(), some.hashCode());
map.put(some, 3);
// what would we get?
assertEquals(3, map.size());
assertEquals(1, map.get(s));
assertEquals(2, map.get(ese));
assertEquals(3, map.get(some));
}
/**
* NOTE: equals is not overridden so the default implementation is used
* which means objects are only equal if they're the same instance, whereas
* the actual Java String class compares the value of its contents.
*/
class MyString {
String i;
MyString(String i) {
this.i = i;
}
@Override
public int hashCode() {
return 100727;
}
}
Opierając się na późniejszym komentarzu, Oscar wydaje się odwracać to, co powiedział wcześniej, i uznaje znaczenie równości. Jednak nadal wydaje się, że to, co się liczy, a nie „ta sama klasa”, jest równe, jest niejasne (wyróżnienie moje):
"Niezupełnie. Lista jest tworzona tylko wtedy, gdy hash jest taki sam, ale klucz jest inny. Na przykład, jeśli String daje hashcode 2345, a Integer daje ten sam hashcode 2345, to liczba całkowita jest wstawiana do listy, ponieważ String. equals (Integer) jest fałszem. Ale jeśli masz tę samą klasę (lub przynajmniej .equals zwraca true), to używany jest ten sam wpis. Na przykład new String („one”) i „new String („ one ”) używane jako keys, użyją tego samego wpisu. Właściwie jest to CAŁY punkt HashMap na pierwszym miejscu! Przekonaj się sam: pastebin.com/f20af40b9 - Oscar Reyes "
w porównaniu z wcześniejszymi komentarzami, które wyraźnie odnoszą się do znaczenia identycznej klasy i tego samego kodu skrótu, bez wzmianki o równych:
"@delfuego: Przekonaj się sam: pastebin.com/f20af40b9 Więc w tym pytaniu używana jest ta sama klasa (poczekaj chwilę, ta sama klasa jest używana, prawda?) Co oznacza, że gdy ten sam hash jest używany ten sam wpis jest używany i nie ma "listy" wpisów. - Oscar Reyes "
lub
"Właściwie to zwiększyłoby wydajność. Im więcej kolizji równa się mniej wpisów w równaniu z hashtagiem. Mniej pracy do wykonania. Czy hash (który wygląda dobrze) ani hashtable (który działa świetnie), założę się, że jest na obiekcie) kreacja, w której wydajność jest degradująca. - Oscar Reyes ”
lub
„@kdgregory: Tak, ale tylko wtedy, gdy kolizja występuje z różnymi klasami, dla tej samej klasy (co ma miejsce) używany jest ten sam wpis. - Oscar Reyes”
Ponownie, mogę źle zrozumieć, co właściwie próbował powiedzieć Oscar. Jednak jego oryginalne komentarze spowodowały tyle zamieszania, że rozsądne wydaje się wyjaśnienie wszystkiego za pomocą kilku wyraźnych testów, więc nie ma żadnych wątpliwości.
[1] - Z Effective Java, Second Edition autorstwa Joshua Blocha:
Za każdym razem, gdy jest wywoływana na tym samym obiekcie więcej niż jeden raz podczas wykonywania aplikacji, metoda hashCode musi konsekwentnie zwracać tę samą liczbę całkowitą, pod warunkiem, że nie zostaną zmodyfikowane żadne informacje użyte w porównaniach równych na obiekcie. Ta liczba całkowita nie musi pozostawać spójna od jednego wykonania aplikacji do innego wykonania tej samej aplikacji.
Jeśli dwa obiekty są równe zgodnie z metodą equal s (Obj ect), to wywołanie metody hashCode na każdym z dwóch obiektów musi dać ten sam wynik w postaci liczby całkowitej.
Nie jest wymagane, aby jeśli dwa obiekty były nierówne zgodnie z metodą equal s (Object), to wywołanie metody hashCode na każdym z dwóch obiektów musi dać różne wyniki w postaci liczb całkowitych. Jednak programista powinien mieć świadomość, że tworzenie różnych wyników całkowitych dla nierównych obiektów może poprawić wydajność tablic mieszających.