Java: mengapa koleksi menerima Komparator tetapi tidak (hipotetis) Hasher dan Equator?

25

Masalah ini paling jelas ketika Anda memiliki implementasi antarmuka yang berbeda, dan untuk tujuan koleksi tertentu Anda hanya peduli pada tampilan tingkat antarmuka objek. Misalnya, Anda memiliki antarmuka seperti ini:

public interface Person {
    int getId();
}

Cara biasa untuk mengimplementasikan hashcode()dan equals()mengimplementasikan kelas akan memiliki kode seperti ini dalam equalsmetode:

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

Ini menyebabkan masalah ketika Anda mencampur implementasi Persondi a HashMap. Jika HashMapsatu-satunya peduli tentang tampilan tingkat antarmuka Person, maka itu bisa berakhir dengan duplikat yang hanya berbeda dalam kelas implementasi mereka.

Anda dapat membuat kasus ini berfungsi dengan menggunakan equals()metode liberal yang sama untuk semua implementasi, tetapi kemudian Anda berisiko equals()melakukan hal yang salah dalam konteks yang berbeda (seperti membandingkan dua Persons yang didukung oleh catatan basis data dengan nomor versi).

Intuisi saya memberi tahu saya bahwa kesetaraan harus didefinisikan per koleksi, bukan per kelas. Saat menggunakan koleksi yang mengandalkan pemesanan, Anda bisa menggunakan kebiasaan Comparatoruntuk memilih pemesanan yang tepat di setiap konteks. Tidak ada analog untuk koleksi berbasis hash. Kenapa ini?

Hanya untuk memperjelas, pertanyaan ini berbeda dari " Mengapa .compareTo () dalam antarmuka sementara .equals () berada dalam kelas di Jawa? " Karena berkaitan dengan implementasi koleksi. compareTo()dan equals()/ hashcode()keduanya menderita masalah universalitas saat menggunakan koleksi: Anda tidak dapat memilih fungsi perbandingan yang berbeda untuk koleksi yang berbeda. Jadi untuk keperluan pertanyaan ini, hierarki warisan suatu objek tidak penting sama sekali; yang penting adalah apakah fungsi perbandingan didefinisikan per objek atau per koleksi.

Sam
sumber
5
Anda selalu dapat memperkenalkan objek pembungkus untuk Personmenerapkan perilaku equalsdan yang diharapkan hashCode. Anda kemudian akan memiliki HashMap<PersonWrapper, V>. Ini adalah salah satu contoh di mana pendekatan murni-OOP tidak elegan: tidak setiap operasi pada objek masuk akal sebagai metode objek itu. Seluruh Objecttipe Java adalah gabungan dari tanggung jawab yang berbeda - hanya getClass, finalizedan toStringmetode yang tampaknya dapat dibenarkan dari praktik terbaik saat ini.
amon
1
1) Dalam C # Anda bisa meneruskan IEqualityComparer<T>koleksi berbasis hash. Jika Anda tidak menentukan satu, itu menggunakan implementasi default berdasarkan Object.Equalsdan Object.GetHashCode(). 2) Penimpaan IMO Equalspada jenis referensi yang bisa berubah jarang merupakan ide yang bagus. Dengan cara itu kesetaraan standar cukup ketat, tetapi Anda dapat menggunakan aturan kesetaraan yang lebih santai saat Anda membutuhkannya melalui kebiasaan IEqualityComparer<T>.
CodesInChaos

Jawaban:

23

Desain ini kadang-kadang dikenal sebagai "Kesetaraan Universal", itu adalah keyakinan bahwa apakah dua hal sama atau tidak adalah properti universal.

Terlebih lagi, kesetaraan adalah properti dari dua objek, tetapi dalam OO, Anda selalu memanggil metode pada satu objek tunggal , dan objek itu hanya dapat memutuskan bagaimana menangani pemanggilan metode itu. Jadi, dalam desain seperti Java, di mana kesetaraan adalah properti dari salah satu dari dua objek yang dibandingkan, bahkan tidak mungkin untuk menjamin beberapa sifat dasar kesetaraan seperti simetri ( a == bb == a), karena dalam kasus pertama, metode sedang dipanggil adan dalam kasus kedua sedang dipanggil bdan karena prinsip dasar OO, itu semata a- mata keputusan (dalam kasus pertama) ataubKeputusan (dalam kasus kedua) apakah itu menganggap dirinya sama dengan yang lain. Satu-satunya cara untuk mendapatkan simetri adalah dengan membuat dua objek bekerja sama, tetapi jika mereka tidak ... keberuntungan.

Salah satu solusinya adalah membuat kesetaraan bukan properti dari satu objek, tetapi baik properti dari dua objek, atau properti dari objek ketiga. Opsi terakhir itu juga memecahkan masalah kesetaraan universal, karena jika Anda menjadikan kesetaraan sebagai properti dari objek "konteks" ketiga, maka Anda dapat membayangkan memiliki EqualityComparerobjek yang berbeda untuk konteks yang berbeda.

Ini adalah desain yang dipilih untuk Haskell, misalnya, dengan Eqtypeclass. Ini juga desain yang dipilih oleh beberapa perpustakaan Scala pihak ketiga (ScalaZ, misalnya), tetapi bukan inti Scala atau perpustakaan standar, yang menggunakan persamaan universal untuk kompatibilitas dengan platform host yang mendasarinya.

Menariknya, ini juga desain yang dipilih dengan Java Comparable/ Comparatorinterface. Para perancang Jawa jelas menyadari masalah itu, tetapi untuk beberapa alasan hanya menyelesaikannya untuk pemesanan, tetapi tidak untuk kesetaraan (atau hashing).

Jadi, seperti pertanyaannya

mengapa ada Comparatorantarmuka tetapi tidak Hasherdan Equator?

jawabannya adalah "Saya tidak tahu". Jelas, para perancang Jawa menyadari masalah itu, sebagaimana dibuktikan dengan keberadaannya Comparator, tetapi mereka jelas tidak menganggapnya sebagai masalah kesetaraan dan hashing. Bahasa dan perpustakaan lain membuat pilihan yang berbeda.

Jörg W Mittag
sumber
7
+1, tetapi perhatikan bahwa ada bahasa OO di mana banyak pengiriman ada (Smalltalk, Common Lisp). Jadi selalu terlalu kuat dalam kalimat berikut: "di OO, Anda selalu memanggil metode pada satu objek tunggal".
coredump
Saya telah menemukan kutipan yang saya cari; menurut JLS 1.0, The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtableyaitu keduanya equalsdan hashCodediperkenalkan sebagai Objectmetode oleh Java devs semata - mata demi Hashtable- tidak ada gagasan UE atau apa pun silimar di mana pun dalam spesifikasi, dan kutipannya cukup jelas bagi saya; jika bukan karena Hashtable, equalsmungkin sudah di antarmuka seperti Comparable. Karena itu, meski sebelumnya saya yakin jawaban Anda benar, sekarang saya menganggapnya tidak berdasar.
vaxquis
@ JörgWMittag itu salah ketik, IFTFY. BTW, berbicara tentang clone- itu awalnya operator , bukan metode (lihat Spesifikasi Bahasa Oak), kutipan: 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)- tiga operator seperti kata kunci itu instanceof new clone(bagian 8.1, operator). Saya berasumsi bahwa itulah alasan (bersejarah) nyata dari clone/ Cloneablemess - Cloneablehanyalah sebuah penemuan di kemudian hari, dan clonekode yang ada diperbaiki.
vaxquis
2
"Ini adalah desain yang dipilih untuk Haskell, misalnya, dengan typeclass Persamaan" Ini semacam benar, tetapi perlu dicatat bahwa Haskell secara eksplisit menyatakan di depan bahwa dua objek dari jenis yang berbeda tidak pernah sama ketika pendekatan Java tidak. Operasi kesetaraan dengan demikian merupakan bagian dari tipe , (karenanya "typeclass") bukan bagian dari nilai konteks ketiga.
Jack
19

Jawaban nyata untuk

mengapa ada Comparatorantarmuka tetapi tidak Hasherdan Equator?

adalah, kutipan dari Josh Bloch :

API Java asli dilakukan dengan sangat cepat di bawah tenggat waktu yang ketat untuk memenuhi jendela pasar penutupan. Tim Java asli melakukan pekerjaan luar biasa, tetapi tidak semua API sempurna.

Masalahnya terletak semata-mata dalam sejarah Jawa, seperti dengan hal-hal lain yang serupa, misalnya .clone()vs Cloneable.

tl; dr

itu karena alasan historis terutama; perilaku / abstraksi saat ini diperkenalkan di JDK 1.0 dan tidak diperbaiki kemudian karena itu hampir tidak mungkin dilakukan dengan mempertahankan kompatibilitas kode mundur.


Pertama, mari kita simpulkan beberapa fakta Java yang terkenal:

  1. Java, dari awal hingga hari ini, dengan bangga kompatibel dengan mundur, membutuhkan API lama untuk tetap didukung dalam versi yang lebih baru,
  2. dengan demikian, hampir setiap konstruksi bahasa yang diperkenalkan dengan JDK 1.0 bertahan hingga hari ini,
  3. Hashtable, .hashCode()& .equals()diimplementasikan di JDK 1.0, ( Hashtable )
  4. Comparable/ Comparatordiperkenalkan di JDK 1.2 ( Sebanding ),

Sekarang, ini sebagai berikut:

  1. itu hampir mustahil & tidak masuk akal untuk retrofit .hashCode()& .equals()untuk antarmuka yang berbeda sambil tetap mempertahankan kompatibilitas ke belakang setelah orang-orang menyadari ada abstraksi yang lebih baik daripada menempatkan mereka di superobject, karena misalnya masing-masing dan setiap programmer Java oleh 1,2 tahu bahwa setiap Objectmemilikinya, dan mereka memiliki tinggal di sana secara fisik untuk memberikan kompatibilitas kode terkompilasi (JVM) juga - dan menambahkan antarmuka eksplisit untuk setiap Objectsubkelas yang benar-benar menerapkannya akan membuat kekacauan ini sama (sic!) dengan Clonablesatu ( Bloch membahas mengapa Cloneable menyebalkan , juga dibahas dalam misalnya EJ 2 dan banyak tempat lain, termasuk SO),
  2. mereka hanya membiarkannya di sana agar generasi mendatang memiliki sumber WTF yang konstan.

Sekarang, Anda mungkin bertanya "apa yang terjadi Hashtabledengan semua ini"?

Jawabannya adalah: hashCode()/ equals()kontrak dan keterampilan desain bahasa yang tidak begitu baik dari pengembang Java inti pada 1995/1996.

Kutipan dari Java 1.0 Language Spec, tanggal 1996 - 4.3.2 The Class Object, hal.41:

Metode equalsdan hashCodedideklarasikan untuk kepentingan hashtable seperti java.util.Hashtable(§ 21.7). Metode sama dengan mendefinisikan gagasan tentang kesetaraan objek, yang didasarkan pada nilai, bukan referensi, perbandingan.

(perhatikan pernyataan ini tepat telah berubah di versi, mengatakan, kutipan: The method hashCode is very useful, together with the method equals, in hashtables such as java.util.HashMap., sehingga mustahil untuk membuat langsung Hashtable- hashCode- equalskoneksi tanpa membaca JLS sejarah!)

Tim Java memutuskan mereka ingin koleksi kamus-gaya yang baik, dan mereka menciptakan Hashtable(ide bagus sejauh ini), tetapi mereka ingin programmer untuk dapat menggunakannya dengan kode sesedikit mungkin / kurva belajar (oops! Kesulitan masuk!) - dan, karena tidak ada obat generik belum [itu JDK 1.0 setelah semua], itu berarti bahwa baik setiap Object put ke Hashtableharus secara eksplisit mengimplementasikan beberapa antarmuka (interface dan masih hanya di awal mereka saat itu ... tidak ada Comparablebelum bahkan!) , membuat ini jera untuk menggunakannya untuk banyak - atau Objectharus implisit menerapkan beberapa metode hashing.

Jelas, mereka pergi dengan solusi 2, karena alasan yang diuraikan di atas. Yup, sekarang kita tahu mereka salah. ... mudah untuk menjadi pintar di belakang. tertawa kecil

Sekarang, hashCode() mengharuskan setiap objek yang memilikinya harus memiliki equals()metode yang berbeda - jadi itu cukup jelas yang equals()harus dimasukkan Objectjuga.

Karena implementasi default dari metode-metode tersebut pada valid a& b Objects pada dasarnya tidak berguna dengan menjadi berlebihan (membuat a.equals(b) sama dengan a==bdan a.hashCode() == b.hashCode() kira-kira sama dengan a==bjuga, kecuali hashCodedan / atau equalsditimpa, atau Anda GC ratusan ribu Objects selama siklus hidup aplikasi Anda 1 ) , aman untuk mengatakan mereka disediakan terutama sebagai ukuran cadangan dan untuk kenyamanan penggunaan. Ini adalah persis bagaimana kita sampai pada fakta terkenal yang selalu menimpa keduanya .equals()& .hashCode()jika Anda berniat benar-benar membandingkan objek atau menyimpan hash. Mengganti hanya satu dari mereka tanpa yang lain adalah cara yang baik untuk mengacaukan kode Anda (dengan membandingkan hasil yang jahat atau nilai tabrakan bucket yang sangat tinggi) - dan menggerakkan kepala Anda di sekitarnya merupakan sumber kebingungan & kesalahan konstan untuk pemula (cari SO untuk melihat untuk Anda sendiri) dan gangguan terus-menerus ke yang lebih berpengalaman.

Juga, perhatikan bahwa meskipun C # berurusan dengan sama dengan & kode hash dalam cara yang sedikit lebih baik, Eric Lippert sendiri menyatakan bahwa mereka melakukan kesalahan yang hampir sama dengan C # yang Sun lakukan dengan Jawa tahun sebelum dimulainya C # :

Tetapi mengapa harus demikian halnya bahwa setiap objek harus dapat hash sendiri untuk dimasukkan ke dalam tabel hash? Sepertinya hal yang aneh mengharuskan setiap objek untuk dapat melakukannya. Saya pikir jika kita mendesain ulang sistem tipe dari awal hari ini, hashing mungkin dilakukan secara berbeda, mungkin dengan IHashableantarmuka. Tetapi ketika sistem tipe CLR dirancang tidak ada tipe generik dan oleh karena itu tabel hash tujuan umum diperlukan untuk dapat menyimpan objek apa pun.

1 tentu saja, Object#hashCodemasih bisa bertabrakan, tetapi perlu sedikit usaha untuk melakukan itu, lihat: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6809470 dan laporan bug yang ditautkan untuk detail; /programming/1381060/hashcode-uniqueness/1381114#1381114 membahas subjek ini lebih mendalam.

vaxquis
sumber
Tapi bukan hanya Java. Banyak orang sezamannya (Ruby, Python, ...) dan pendahulunya (Smalltalk, ...) dan beberapa penggantinya juga memiliki Kesetaraan Universal dan Keramahan Universal (apakah itu sebuah kata?).
Jörg W Mittag
@ JörgWMittag lihat programmers.stackexchange.com/questions/283194/… - Saya sudah tidak setuju tentang "UE" di Jawa; UE secara historis tidak pernah menjadi perhatian nyata dalam Objectdesain; hashability adalah.
vaxquis
@vquisquis Saya tidak ingin membahas ini, tetapi komentar saya sebelumnya menunjukkan bahwa dua objek yang dapat dijangkau secara bersamaan dapat memiliki kode hash yang sama (default).
Pasang kembali Monica
1
@vquisquis OK. Saya membelinya. Kekhawatiran saya adalah bahwa seseorang yang sedang belajar akan melihat ini dan berpikir bahwa mereka pintar dengan menggunakan kode hash Sistem dan bukan yang setara dll. Jika mereka melakukannya, kemungkinan akan bekerja dengan cukup baik kecuali untuk saat-saat langka tidak dan akan ada tidak ada cara untuk mereproduksi masalah dengan andal.
JimmyJames
1
Ini harus menjadi jawaban yang diterima, karena kesimpulan jawaban yang diterima adalah "saya tidak tahu"
Phoenix