Kode hash ArrayList yang berisi dirinya sebagai elemen

38

Bisakah kita menemukan hashcodea listyang 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:

  1. Kenapa ada StackOverflowError?
  2. Apakah mungkin untuk menemukan kode hash dengan cara ini?
Pelawak
sumber
7
Karena Anda menambahkan Daftar ke dirinya sendiri. coba a.hashCode () tanpa pernyataan add
Jens
Ketika Anda meletakkan objek ke dalam daftar array, Anda menyimpan referensi ke objek. Dalam kasus Anda, Anda menempatkan penyihir ArrayList adalah referensi itu sendiri.
Vishwa Ratna
Ok, saya mengerti mengapa ada stackoverflow, ada yang bisa membantu saya menjelaskan masalah nomor 2 - Bagaimana menemukan ini
Joker
9
Seperti orang lain telah menjawab, ini tidak mungkin, dengan definisi Listantarmuka, hashCodedaftar tergantung pada anggotanya. Mengingat bahwa daftar adalah anggotanya sendiri, kode hash tergantung pada hashCode, yang tergantung pada hashCode... dan seterusnya, menyebabkan rekursi tak terbatas dan StackOverflowErrorAnda 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.
Alexander - Pasang kembali Monica

Jawaban:

36

Kode hash untuk menyesuaikan Listimplementasi telah ditentukan dalam antarmuka :

Mengembalikan nilai kode hash untuk daftar ini. Kode hash dari daftar didefinisikan sebagai hasil dari perhitungan berikut:

 int hashCode = 1;
 for (E e : list)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Ini memastikan hal itu list1.equals(list2)menyiratkan bahwa list1.hashCode()==list2.hashCode()untuk dua daftar, list1dan list2, sebagaimana disyaratkan oleh kontrak umum Object.hashCode().

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 + xharus true, dengan kata lain, tidak mungkin untuk menghitung angka yang sesuai.

Holger
sumber
1
@ Holger, Eirc ingin mengganti kode dari seluruh fungsi hashCode()untuk kembali 0. Ini secara teknis memecahkan x == 31 + xtetapi mengabaikan persyaratan bahwa x harus setidaknya 1.
bxk21
4
@EricDuminil inti dari jawaban saya adalah, kontrak menggambarkan logika yang ArrayListmengimplementasikan 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 ke StackOverflowError, yang telah dibahas dalam jawaban lain. Jadi saya fokus pada ketidakmungkinan umum implementasi yang sesuai menyelesaikan dalam waktu yang terbatas dengan nilai.
Holger
2
@ pdem tidak masalah apakah spesifikasi menggunakan deskripsi bertele-tele dari suatu algoritma, rumus, kode pseudo, atau kode aktual. Seperti yang dikatakan dalam jawaban, kode yang diberikan dalam spesifikasi tidak menghalangi implementasi alternatif secara umum. Bentuk spek tidak mengatakan apa-apa tentang apakah analisis terjadi atau tidak. Kalimat dokumentasi antarmuka " Meskipun daftar diizinkan untuk memuat diri mereka sebagai elemen, sangat hati-hati disarankan: metode kode hash dan sama tidak lagi didefinisikan dengan baik pada daftar seperti itu " menunjukkan bahwa analisis seperti itu memang terjadi.
Holger
2
@ pdem Anda membalikkannya. Saya tidak pernah mengatakan bahwa daftar tersebut harus sama karena kode hash. Daftar yang sama, menurut definisi. Arrays.asList("foo")sama dengan Collections.singletonList("foo"), sama dengan List.of("foo")sama dengan new 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.
Holger
2
@pdem tepatnya, implementasi khusus yang tidak menerapkan Listatau memiliki tanda peringatan besar “jangan campur dengan daftar biasa”, bandingkan dengan IdentityHashMapdan “ Kelas ini bukan implementasi Peta tujuan umum! " peringatan. Dalam kasus sebelumnya, Anda sudah baik-baik saja dengan menerapkan Collectiontetapi menambahkan metode akses berbasis daftar indeks gaya juga. Kemudian, tidak ada kendala kesetaraan, tetapi masih berfungsi dengan lancar dengan jenis koleksi lainnya.
Holger
23

Lihatlah implementasi kerangka hashCodemetode di AbstractListkelas.

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

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 bertemu StackOverflowError. Jadi Anda tidak bisa menemukan hashCodecara ini.

Ravindra Ranwala
sumber
Jadi jawabannya adalah tidak ada cara untuk menemukan kode hash dengan cara ini?
Joker
3
Ya, karena kondisi rekursif
spring
Tidak hanya itu, itu didefinisikan dengan cara ini.
chrylis -pada mogok-
14

Anda telah menetapkan daftar (patologis) yang berisi dirinya sendiri.

Kenapa ada StackOverflowError?

Menurut javadocs (yaitu spesifikasinya), kode hash dari Listdidefinisikan ke fungsi kode hash dari setiap elemennya. Ia mengatakan:

"Kode hash dari daftar didefinisikan sebagai hasil dari perhitungan berikut:"

int hashCode = 1;
    for (E e : list)
         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Jadi untuk menghitung kode hash a, Anda terlebih dahulu menghitung kode hash a. Itu sangat rekursif dan mengarah dengan cepat ke stack overflow.

Apakah mungkin untuk menemukan kode hash dengan cara ini?

Tidak. Jika Anda mempertimbangkan spesifikasi algoritmik di atas dalam istilah matematika, kode hash dari Listyang 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 .

Stephen C
sumber
Saya tidak tahu mengapa jawaban ini lebih rendah dari dua lainnya karena sebenarnya menanggapi pertanyaan OP dengan penjelasan.
Neyt
1
@Tidak beberapa pengguna hanya membaca jawaban di atas.
Holger
8

Tidak, dokumentasi memiliki jawaban

The dokumentasi struktur Daftar eksplisit menyatakan:

Catatan: Meskipun daftar diizinkan untuk memuat diri mereka sebagai elemen, sangat hati-hati disarankan: metode kode hash sama dan tidak lagi didefinisikan dengan baik pada daftar tersebut.

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.

Peter adalah
sumber
1
Anda memang tahu mengapa itu di luar spesifikasi, jadi itu menjelaskan bahwa itu bukan bug. Itu adalah bagian yang hilang dari jawaban lainnya.
pdem
3

Jawaban Ravindra memberikan penjelasan yang bagus untuk poin 1. Mengomentari pertanyaan 2:

Apakah mungkin untuk menemukan kode hash dengan cara ini?

Ada yang melingkar di sini. Setidaknya salah satu dari 2 ini pasti salah dalam konteks kesalahan overflow tumpukan ini:

  • bahwa kode hash daftar harus memperhitungkan elemen-elemennya
  • bahwa boleh saja daftar menjadi elemennya sendiri

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 memperluas ArrayListdan melewatkan menambahkan kode hash elemen, seperti

for (E e : this)
  if(e == this) continue; //contrived rules
  hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Menggunakan 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.

ernest_k
sumber
1
Perhitungan kode hash yang diamanatkan oleh para Listkontrak . Tidak ada implementasi yang valid dapat melewati itu sendiri. Dari sisi spesifikasi, Anda dapat memperoleh bahwa jika Anda menemukan intnomor yang x == 31 + xadalah true, maka Anda dapat menerapkan valid short-cut ...
Holger
Saya tidak begitu mengerti apa yang dikatakan @ Holger. Tetapi ada 2 Masalah dengan solusi: Pertama: Ini memecahkan Masalah hanya ketika daftar ini adalah item dari dirinya sendiri dan tidak jika daftar di mana item dari item itu sendiri (lapisan rekursi yang lebih dalam) Kedua: Jika Daftar melompat sendiri itu mungkin sama dengan daftar kosong.
Jonas Michel
1
@JonasMichel Saya tidak cukup mengusulkan solusi. Saya hanya secara filosofis berdebat tentang absurditas pertanyaan 2. Jika kita harus menghitung kode hash untuk daftar seperti itu, maka itu tidak akan berfungsi kecuali kita menghapus kendala dari daftar array (dan Holger memperkuatnya dengan mengatakan bahwa Listsecara formal menentukan logika kode hash yang harus dipenuhi dengan implementasi)
ernest_k
Pemahaman saya (terbatas) adalah yang Listmenyediakan 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.
Teepeemm
1
@Teepeemm Listadalah 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 mendasar java.lang.Object.
Holger
1

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 kembalijava.lang.StackOverflowError

Di bawah ini adalah contoh kode yang menjelaskan skenario serupa:

public class RefTest {

    public static void main(String... strings) {
        RefTest rf = new RefTest();
        rf.message(message("test"));
    }

    public static String message2(String s){
        return message(s);
    }

    public static String message(String s){
        return message2(s);
    }

}   
Simmant
sumber