Bisakah kita menemukan hashcode
a list
yang mengandung dirinya element
?
Saya tahu ini adalah praktik yang buruk, tetapi inilah yang diminta pewawancara.
Ketika saya menjalankan kode berikut ini melempar StackOverflowError
:
public class Main {
public static void main(String args[]) {
ArrayList<ArrayList> a = new ArrayList();
a.add(a);
a.hashCode();
}
}
Sekarang di sini saya punya dua pertanyaan:
- Kenapa ada
StackOverflowError
? - Apakah mungkin untuk menemukan kode hash dengan cara ini?
java
java-8
stack-overflow
hashcode
Pelawak
sumber
sumber
List
antarmuka,hashCode
daftar tergantung pada anggotanya. Mengingat bahwa daftar adalah anggotanya sendiri, kode hash tergantung padahashCode
, yang tergantung padahashCode
... dan seterusnya, menyebabkan rekursi tak terbatas danStackOverflowError
Anda berlari ke. Sekarang pertanyaannya adalah: mengapa Anda memerlukan daftar untuk memuat dirinya sendiri? Saya dapat menjamin Anda bahwa Anda dapat mencapai apa pun yang Anda coba lakukan, dengan cara yang lebih baik, tanpa memerlukan keanggotaan rekursif seperti ini.Jawaban:
Kode hash untuk menyesuaikan
List
implementasi telah ditentukan dalam antarmuka :Ini tidak mengharuskan implementasi terlihat persis seperti itu (lihat Cara menghitung kode hash untuk streaming dengan cara yang sama seperti List.hashCode () untuk alternatif), tetapi kode hash yang benar untuk daftar yang hanya berisi dirinya akan menjadi nomor yang
x == 31 + x
harustrue
, dengan kata lain, tidak mungkin untuk menghitung angka yang sesuai.sumber
hashCode()
untuk kembali0
. Ini secara teknis memecahkanx == 31 + x
tetapi mengabaikan persyaratan bahwa x harus setidaknya 1.ArrayList
mengimplementasikan secara harfiah, yang mengarah ke rekursi, tetapi tidak ada implementasi alternatif yang sesuai juga. Perhatikan bahwa saya memposting jawaban saya pada saat OP sudah mengerti mengapa implementasi khusus ini mengarah keStackOverflowError
, yang telah dibahas dalam jawaban lain. Jadi saya fokus pada ketidakmungkinan umum implementasi yang sesuai menyelesaikan dalam waktu yang terbatas dengan nilai.Arrays.asList("foo")
sama denganCollections.singletonList("foo")
, sama denganList.of("foo")
sama dengannew ArrayList<>(List.of("foo"))
. Semua daftar ini sama, poin. Kemudian, karena daftar ini sama, mereka harus memiliki kode hash yang sama. Tidak sebaliknya. Karena mereka harus memiliki kode hash yang sama, itu harus didefinisikan dengan baik. Terlepas dari bagaimana mereka mendefinisikannya (kembali di Jawa 2), itu harus didefinisikan dengan baik, harus disetujui oleh semua implementasi.List
atau memiliki tanda peringatan besar “jangan campur dengan daftar biasa”, bandingkan denganIdentityHashMap
dan “ Kelas ini bukan implementasi Peta tujuan umum! " peringatan. Dalam kasus sebelumnya, Anda sudah baik-baik saja dengan menerapkanCollection
tetapi menambahkan metode akses berbasis daftar indeks gaya juga. Kemudian, tidak ada kendala kesetaraan, tetapi masih berfungsi dengan lancar dengan jenis koleksi lainnya.Lihatlah implementasi kerangka
hashCode
metode diAbstractList
kelas.Untuk setiap elemen dalam daftar, ini panggilan
hashCode
. Dalam daftar kasus Anda memiliki dirinya sendiri sebagai elemen satu-satunya. Sekarang panggilan ini tidak pernah berakhir. Metode menyebut dirinya secara rekursif dan rekursi terus berliku sampai bertemuStackOverflowError
. Jadi Anda tidak bisa menemukanhashCode
cara ini.sumber
Anda telah menetapkan daftar (patologis) yang berisi dirinya sendiri.
Menurut javadocs (yaitu spesifikasinya), kode hash dari
List
didefinisikan ke fungsi kode hash dari setiap elemennya. Ia mengatakan:Jadi untuk menghitung kode hash
a
, Anda terlebih dahulu menghitung kode hasha
. Itu sangat rekursif dan mengarah dengan cepat ke stack overflow.Tidak. Jika Anda mempertimbangkan spesifikasi algoritmik di atas dalam istilah matematika, kode hash dari
List
yang berisi dirinya sendiri adalah fungsi yang tidak dapat dihitung . Tidak mungkin untuk menghitungnya dengan cara ini (menggunakan algoritma di atas) atau dengan cara lain apa pun .sumber
Tidak, dokumentasi memiliki jawaban
The dokumentasi struktur Daftar eksplisit menyatakan:
Tidak banyak lagi yang bisa dikatakan selain itu - menurut spesifikasi Java, Anda tidak akan dapat menghitung kode hash untuk daftar yang berisi dirinya sendiri; jawaban lain masuk ke detail mengapa begitu, tetapi intinya adalah bahwa itu diketahui dan disengaja.
sumber
Jawaban Ravindra memberikan penjelasan yang bagus untuk poin 1. Mengomentari pertanyaan 2:
Ada yang melingkar di sini. Setidaknya salah satu dari 2 ini pasti salah dalam konteks kesalahan overflow tumpukan ini:
Sekarang, karena kita sedang berurusan dengan
ArrayList
, poin pertama sudah diperbaiki. Dengan kata lain, mungkin Anda memerlukan implementasi yang berbeda untuk dapat secara bermakna menghitung kode hash dari daftar rekursif ... Orang dapat memperluasArrayList
dan melewatkan menambahkan kode hash elemen, sepertiMenggunakan kelas seperti itu alih-alih
ArrayList
, Anda bisa.Dengan
ArrayList
, poin kedua salah. Jadi jika pewawancara berarti "Apakah mungkin untuk menemukan kode hash dengan cara ini (dengan daftar array)?" , maka jawabannya tidak, karena itu tidak masuk akal.sumber
List
kontrak . Tidak ada implementasi yang valid dapat melewati itu sendiri. Dari sisi spesifikasi, Anda dapat memperoleh bahwa jika Anda menemukanint
nomor yangx == 31 + x
adalahtrue
, maka Anda dapat menerapkan valid short-cut ...List
secara formal menentukan logika kode hash yang harus dipenuhi dengan implementasi)List
menyediakan perhitungan kode hash, tetapi kami bisa menimpanya. Satu-satunya persyaratan nyata adalah kode hash umum: jika objek sama, maka kode hash harus sama. Implementasi ini mengikuti persyaratan itu.List
adalah antarmuka. Ini mendefinisikan kontrak , tidak memberikan implementasi. Tentu saja, kontrak mencakup keduanya, persamaan dan kode hash. Karena kontrak umum kesetaraan harus simetris, jika Anda mengubah satu implementasi daftar, Anda harus mengubah semua implementasi daftar yang ada, jika tidak, Anda bahkan akan memutus kontrak mendasarjava.lang.Object
.Karena ketika Anda memanggil fungsi yang sama dengan dari fungsi yang sama maka itu akan menciptakan kondisi rekursi yang tidak pernah berakhir. Dan untuk mencegah operasi ini, JAWA akan kembali
java.lang.StackOverflowError
Di bawah ini adalah contoh kode yang menjelaskan skenario serupa:
sumber