Java: dlaczego kolekcje akceptują Komparator, ale nie (hipotetyczny) Hasher i Equator?

25

Ten problem jest najbardziej widoczny, gdy masz różne implementacje interfejsu, a do celów konkretnej kolekcji dbasz tylko o widok obiektów na poziomie interfejsu. Załóżmy na przykład, że masz taki interfejs:

public interface Person {
    int getId();
}

Zwykły sposób implementacji hashcode()i equals()implementacji klas miałby taki kod w equalsmetodzie:

if (getClass() != other.getClass()) {
    return false;
}

Powoduje to problemy podczas mieszania implementacji Personw HashMap. Jeśli HashMapzależy tylko na widoku na poziomie interfejsu Person, może to oznaczać, że duplikaty różnią się jedynie klasami implementacyjnymi.

Możesz sprawić, by ten przypadek działał, stosując tę ​​samą liberalną equals()metodę dla wszystkich implementacji, ale wtedy ryzykujesz equals()zrobienie niewłaściwej rzeczy w innym kontekście (np. Porównanie dwóch Persons, które są wspierane przez rekordy bazy danych z numerami wersji).

Moja intuicja mówi mi, że równość powinna być zdefiniowana dla kolekcji zamiast dla klasy. Korzystając z kolekcji, które opierają się na zamawianiu, możesz użyć niestandardowego, Comparatoraby wybrać odpowiednie porządkowanie w każdym kontekście. Nie ma analogii dla kolekcji opartych na haszowaniu. Dlaczego to?

Aby wyjaśnić, to pytanie różni się od „ Dlaczego .compareTo () w interfejsie, podczas gdy .equals () jest w klasie w Javie? ”, Ponieważ dotyczy implementacji kolekcji. compareTo()i equals()/ i hashcode()oba mają problem z uniwersalnością podczas korzystania z kolekcji: nie można wybrać różnych funkcji porównania dla różnych kolekcji. Na potrzeby tego pytania hierarchia dziedziczenia obiektu w ogóle nie ma znaczenia; liczy się tylko to, czy funkcja porównania jest zdefiniowana dla obiektu czy dla kolekcji.

Sam
źródło
5
Zawsze możesz wprowadzić obiekty opakowania dla Persontej implementacji oczekiwanego equalsi hashCodezachowania. Miałbyś wtedy HashMap<PersonWrapper, V>. Jest to przykład, w którym podejście oparte na czystym OOP nie jest eleganckie: nie każda operacja na obiekcie ma sens jako metoda tego obiektu. Cała Java Objecttyp jest amalgamatem różnych zadań - tylko getClass, finalizea toStringmetody wydają się uzasadnione zdalnie przez dzisiejszych najlepszych praktyk.
Amon
1
1) W języku C # możesz przekazać IEqualityComparer<T>kolekcję opartą na haszowaniu. Jeśli nie określisz, używa domyślnej implementacji opartej na Object.Equalsi Object.GetHashCode(). 2) Nadpisywanie przez IMO Equalszmiennego typu odniesienia rzadko jest dobrym pomysłem. W ten sposób domyślna równość jest dość surowa, ale możesz użyć bardziej swobodnej reguły równości, gdy potrzebujesz jej za pomocą niestandardowego IEqualityComparer<T>.
CodesInChaos
2
Powiązane meta pytanie: czy te pytania się powtarzają?

Odpowiedzi:

23

Ten projekt jest czasem znany jako „Uniwersalna równość”, to przekonanie, że to, czy dwie rzeczy są równe, czy nie, jest uniwersalną własnością.

Co więcej, równość jest właściwością dwóch obiektów, ale w OO zawsze wywołujesz metodę na jednym obiekcie , a ten obiekt może jedynie decydować, jak obsłużyć to wywołanie metody. Tak więc w projekcie takim jak Java, w którym równość jest właściwością jednego z dwóch porównywanych obiektów, nie jest nawet możliwe zagwarantowanie niektórych podstawowych właściwości równości, takich jak symetria ( a == bb == a), ponieważ w pierwszym przypadku metoda jest wzywany, aaw drugim przypadku jest wzywany bi ze względu na podstawowe zasady OO, jest to wyłącznie adecyzja (w pierwszym przypadku) lubbdecyzja (w drugim przypadku), czy uważa się za równą drugiej. Jedynym sposobem na uzyskanie symetrii jest współpraca dwóch obiektów, ale jeśli nie… mają pecha.

Jednym rozwiązaniem byłoby uczynienie z równości nie własności jednego obiektu, ale albo własności dwóch obiektów, albo własności trzeciego obiektu. Ta ostatnia opcja rozwiązuje również problem uniwersalnej równości, ponieważ jeśli uczynisz równość właściwością trzeciego obiektu „kontekstowego”, możesz sobie wyobrazić, że masz różne EqualityComparerobiekty dla różnych kontekstów.

Jest to projekt wybrany dla Haskell, na przykład z Eqtypem. Jest to również projekt wybrany przez niektóre biblioteki Scala innych firm (na przykład ScalaZ), ale nie rdzeń Scala lub standardowa biblioteka, która używa uniwersalnej równości dla kompatybilności z bazową platformą hosta.

Co ciekawe, jest to również projekt wybrany z interfejsami Java Comparable/ Comparator. Projektanci Javy wyraźnie zdawali sobie sprawę z problemu, ale z jakiegoś powodu rozwiązali go tylko dla porządku, ale nie dla równości (lub mieszania).

Co do pytania

dlaczego istnieje Comparatorinterfejs, ale nie Hasheri Equator?

odpowiedź brzmi „nie wiem”. Najwyraźniej projektanci Java byli świadomi problemu, o czym świadczy istnienie Comparator, ale oczywiście nie uważali tego za problem równości i mieszania. Inne języki i biblioteki dokonują różnych wyborów.

Jörg W Mittag
źródło
7
+1, ale pamiętaj, że istnieją języki OO, w których istnieje wiele wysyłek (Smalltalk, Common Lisp). Dlatego zawsze jest zbyt silny w następującym zdaniu: „w OO zawsze wywołujesz metodę na jednym obiekcie”.
Coredump
Znalazłem cytat, którego szukałem; według JLS 1.0 The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtable, czyli zarówno equalsi hashCodezostały wprowadzone jako Objectmetod przez Java DEVS wyłącznie dla dobra Hashtable- nie ma pojęcia UE lub cokolwiek silimar gdziekolwiek w ciemno, a cytat jest wystarczająco jasne dla mnie; gdyby nie Hashtable, equalsprawdopodobnie byłby w takim interfejsie Comparable. Jako taki, chociaż wcześniej uważałem twoją odpowiedź za poprawną, teraz uważam ją za bezpodstawną.
vaxquis
@ JörgWMittag to literówka, IFTFY. BTW, mówiąc o clone- to był pierwotnie operator , a nie metoda (patrz Specyfikacja języka dębowego), cytat: The unary operator clone is applied to an object. (...) The clone operator is normally used inside new to clone the prototype of some class, before applying the initializers (constructors)- trzema operatorami podobnymi do słów kluczowych instanceof new clone(sekcja 8.1, operatory). Zakładam, że to jest prawdziwa (historyczna) przyczyna clone/ Cloneablemess - Cloneablebył to po prostu wynalazek późniejszy, a istniejący clonekod został z nim zmodernizowany.
vaxquis
2
„Jest to projekt wybrany dla Haskell, na przykład z typem Eq”. Jest to trochę prawda, ale warto zauważyć, że Haskell wyraźnie stwierdza z góry, że dwa różne typy obiektów nigdy nie są równe, podczas gdy podejście Java nie. Operacja równości jest zatem częścią typu (stąd „typeclass”), a nie częścią trzeciej wartości kontekstu.
Jack
19

Prawdziwa odpowiedź na

dlaczego istnieje Comparatorinterfejs, ale nie Hasheri Equator?

cytat dzięki uprzejmości Josha Blocha :

Oryginalne interfejsy API Java zostały wykonane bardzo szybko w krótkim terminie, aby sprostać zamykającemu się rynkowi. Oryginalny zespół Java wykonał niesamowitą robotę, ale nie wszystkie interfejsy API są idealne.

Problem leży wyłącznie w historii Javy, podobnie jak w innych podobnych sprawach, np . .clone()Vs.Cloneable

tl; dr

dzieje się tak głównie z przyczyn historycznych; Obecne zachowanie / abstrakcja zostało wprowadzone w JDK 1.0 i nie zostało później naprawione, ponieważ było to praktycznie niemożliwe z zachowaniem kompatybilności kodu wstecznego.


Najpierw podsumujmy kilka dobrze znanych faktów o Javie:

  1. Java od samego początku do dnia dzisiejszego była dumnie kompatybilna wstecz, wymagając, aby starsze interfejsy API były nadal obsługiwane w nowszych wersjach,
  2. dlatego prawie każdy konstrukt językowy wprowadzony w JDK 1.0 przetrwał do dnia dzisiejszego,
  3. Hashtable, .hashCode()i .equals()zostały zaimplementowane w JDK 1.0, ( Hashtable )
  4. Comparable/ Comparatorzostał wprowadzony w JDK 1.2 ( porównywalny ),

Teraz wygląda to następująco:

  1. praktycznie niemożliwe i bezsensowne było modernizowanie .hashCode()i .equals()wyróżnianie interfejsów przy jednoczesnym zachowaniu kompatybilności wstecznej po tym, jak ludzie zdali sobie sprawę, że istnieją lepsze abstrakcje niż umieszczanie ich w superobjektach, ponieważ np. każdy programista Java w wersji 1.2 wiedział, że każdy Objectje ma, i mieli pozostanie tam fizycznie w celu zapewnienia kompatybilności skompilowanego kodu (JVM) - i dodanie jawnego interfejsu do każdej Objectpodklasy, która naprawdę je zaimplementowała, sprawiłoby, że ten bałagan byłby równy (sic!) do Clonablejednego ( Bloch omawia, dlaczego klonowanie jest do bani , również omówione np. w EJ 2nd i wiele innych miejsc, w tym SO),
  2. po prostu zostawili je tam, aby przyszłe pokolenie miało stałe źródło WTF.

Teraz możesz zapytać „co Hashtablema z tym wszystkim”?

Odpowiedź brzmi: hashCode()/ equals()kontrakt i niezbyt dobre umiejętności projektowania języka przez głównych programistów Java w latach 1995/1996.

Cytat ze specyfikacji języka Java 1.0, z 1996 r. - 4.3.2 The Class Object, str. 41:

Metody equalsi hashCodezostały zadeklarowane na korzyść java.util.Hashtabletablic mieszających, takich jak (§21.7). Metoda równa się definiuje pojęcie równości obiektu, które opiera się na porównaniu wartości, a nie odniesienia.

(uwaga dokładny ta wypowiedź została zmieniona w późniejszych wersjach, aby powiedzieć, cytat: The method hashCode is very useful, together with the method equals, in hashtables such as java.util.HashMap., uniemożliwiając, aby bezpośredni Hashtable- hashCode- equalspołączenia bez czytania JLS historycznych!)

Zespół Java zdecydował, że chce dobrej kolekcji w stylu słownika, i stworzył Hashtable(jak dotąd dobry pomysł), ale chciał, aby programista mógł go używać przy możliwie najmniejszej krzywej kodu / uczenia się (oops! Problemy z nadchodzącym!) - a ponieważ nie było jeszcze żadnych generycznych [to w końcu JDK 1.0], oznaczałoby to, że każdy Object włożony Hashtablemusiałby jawnie zaimplementować jakiś interfejs (a interfejsy były wtedy jeszcze w początkowej fazie ... Comparablenawet jeszcze!) , co zniechęca do korzystania z niego przez wiele osób - lub Objectmusiałoby niejawnie zaimplementować jakąś metodę haszującą.

Oczywiście wybrali rozwiązanie 2 z powodów przedstawionych powyżej. Tak, teraz wiemy, że się mylili. ... z perspektywy czasu łatwo być mądrym. chichot

Teraz hashCode() wymaga, aby każdy obiekt, który go posiada, musiał mieć odrębną equals()metodę - więc było całkiem oczywiste, że equals()trzeba go również wprowadzić Object.

Ponieważ domyślne implementacje tych metod na ważność ai b Objects są w zasadzie bezużyteczne, będąc zbędny (co a.equals(b) równa się a==bi a.hashCode() == b.hashCode() mniej więcej równa się a==brównież, chyba że hashCodei / lub equalsjest nadpisane, albo GC setki tysięcy Objects podczas całego cyklu życia aplikacji 1 ) , można bezpiecznie powiedzieć, że zostały one dostarczone głównie jako środek zapasowy i dla wygody użytkowania. Właśnie w ten sposób dochodzimy do dobrze znanego faktu, który zawsze zastępuje oba .equals()i .hashCode()jeśli zamierzasz faktycznie porównywać obiekty lub przechowywać je w postaci skrótów. Zastąpienie tylko jednego z nich bez drugiego jest dobrym sposobem na wkręcenie kodu (przez nikczemne porównanie wyników lub niesamowicie wysokie wartości kolizji z wiadrem) - a obejście go jest źródłem ciągłego zamieszania i błędów dla początkujących (wyszukaj SO, aby zobaczyć to dla siebie) i ciągłe uciążliwości dla bardziej doświadczonych.

Zauważ też, że chociaż C # radzi sobie z equals i hashcode w nieco lepszy sposób, sam Eric Lippert twierdzi, że popełnił prawie taki sam błąd z C #, jaki Sun zrobił z Javą na wiele lat przed początkiem C # :

Ale dlaczego miałoby tak być, że każdy obiekt powinien mieć możliwość mieszania się w celu wstawienia do tablicy skrótów? Wydaje się dziwne, że każdy obiekt musi być w stanie to zrobić. Myślę, że gdybyśmy dzisiaj przeprojektowywali system typów od nowa, mieszanie mogłoby być wykonane inaczej, być może z IHashableinterfejsem. Ale kiedy zaprojektowano system typu CLR, nie istniały żadne typy ogólne, dlatego też tablica mieszająca ogólnego przeznaczenia musiała być w stanie przechowywać dowolny obiekt.

1 oczywiście Object#hashCodenadal może się kolidować, ale zajmuje to trochę wysiłku, patrz: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6809470 i powiązane raporty błędów, aby uzyskać szczegółowe informacje; /programming/1381060/hashcode-uniqueness/1381114#1381114 obejmuje ten temat bardziej szczegółowo.

vaxquis
źródło
Ale to nie tylko Java. Wielu współczesnych (Ruby, Python,…) i poprzedników (Smalltalk,…) oraz niektórzy z ich następców mają także Universal Equality i Universal Hashability (czy to słowo?).
Jörg W Mittag
@ JörgWMittag patrz programmers.stackexchange.com/questions/283194/... - Nie mogę się zgodzić na temat „UE” w Javie; UE historycznie nigdy nie była prawdziwym problemem w Objectprojektowaniu; hashability was.
vaxquis
@vaxquis Nie chcę tego omijać, ale mój poprzedni komentarz pokazuje, że dwa jednocześnie osiągalne obiekty mogą mieć ten sam (domyślny) kod skrótu.
Przywróć Monikę
1
@vaxquis OK. Kupuję to Obawiam się, że ktoś, kto się uczy, zobaczy to i będzie myślał, że jest sprytny, używając systemowego kodu skrótu zamiast równego itp. Jeśli to zrobi, prawdopodobnie będzie działał wystarczająco dobrze, z wyjątkiem rzadkich przypadków, gdy tego nie będzie i będzie nie ma możliwości wiarygodnego odtworzenia problemu.
JimmyJames,
1
To powinna być zaakceptowana odpowiedź, ponieważ konkluzja tej odpowiedzi jest następująca: „nie wiem”
Phoenix,