Apa sing bisa ditakoni nalika wawancara: Struktur data ing basa Jawa. Bagean 2

PART 1 Saiki kita ngomong babagan basis sing kudu dingerteni saben pangembang Jawa. Babagan kawruh klasik saka ngendi kabeh diwiwiti. Dina iki aku pengin ndemek salah sawijining topik dhasar saka wawancara apa wae - struktur data ing Jawa . Dadi, tinimbang ngalahake grumbulan, ayo miwiti. Terusake dhaptar pitakonan sing bisa ditakoni babagan topik iki sajrone wawancara.

6. Marang kita bab List

Dhaptar minangka antarmuka sing nggambarake struktur obyek sing diurutake, sing diarani dhaptar. "Trik" saka struktur iki yaiku unsur-unsur sing ana ing Dhaptar bisa dilebokake, diowahi utawa dibusak kanthi indeks, yaiku, pengenal internal Dhaftar . Ing tembung liya, indeks tegese: "pira unsur saka wiwitan dhaptar." Elemen List pisanan duwe indeks 0, sing nomer loro duwe indeks 1, lan liya-liyane. Dadi unsur kaping lima yaiku papat unsur adoh saka wiwitan dhaptar. Kaya kasebut ing ndhuwur, urutan item sing ditambahake menyang dhaptar iku penting. Pramila struktur data kasebut diarani dhaptar . Kita dhaptar metode unik kanggo struktur iki sing ngarahake nggarap unsur kanthi indeks:

• njaluk - ngasilake unsur ing posisi sing ditemtokake (kanthi nilai indeks),
• mbusak - mbusak unsur ing posisi sing ditemtokake,
• set - ngganti unsur ing posisi sing ditemtokake karo unsur sing ditemtokake ing metode kasebut.

Implementasi utama yaiku ArrayList lan LinkedList . Kita bakal ngomong luwih akeh babagan dheweke mengko. Vektor minangka dhaptar sing aman kanggo benang, mula saben metode ing kelas iki disinkronake. Nanging elinga yen sampeyan pengin ngamanake sawetara tumindak dhaptar, sampeyan bakal nyinkronake kabeh urutan operasi. Lan nyinkronake operasi individu kurang aman lan luwih alon. Mesthi, Vector uga duwe nduwur sirah ngunci, sanajan sampeyan ora butuh kunci kasebut. Mulane, kelas iki saiki dianggep lungse lan ora digunakake. Miturut cara: ArrayList padha karo Vector , nanging ora nggunakake ngunci, supaya digunakake nang endi wae. Stack minangka subclass saka kelas Vector karo siji konstruktor standar lan kabeh cara saka kelas Vector , plus sawetara dhewe (kita bakal ngomong babagan mengko). Minangka conto, sampeyan bisa mbayangno proses kasebut minangka tumpukan folder kanthi dokumen. Sampeyan nyeleh siji folder ing ndhuwur tumpukan, lan sampeyan mung bisa njupuk folder iki ing urutan mbalikke, miwiti saka ndhuwur. Bener, iki minangka mekanisme jinis LIFO , yaiku, Last In First Out , sing pungkasan teka yaiku sing pertama lunga. Tumpukan ngetrapake cara dhewe:

• push - nambah unsur liwati menyang ndhuwur tumpukan;
• Ndeleng - ngasilake unsur sing ana ing ndhuwur tumpukan;
• pop - uga ngasilake unsur sing ana ing ndhuwur tumpukan, nanging mbusak;
• kosong - mriksa apa tumpukan kosong - bener utawa ora - salah ;
• search - nggoleki tumpukan kanggo unsur tartamtu. Yen unsur ditemokake, nomer urutan relatif kanggo ndhuwur tumpukan bali. Yen unsur ora ditemokake, nilai -1 bali.

Ing wayahe, subclass Stack ora bener digunakake amarga kesederhanaan lan infleksibilitas, nanging, sampeyan bisa uga nemokake. Contone, nalika sampeyan nampa sawetara kesalahan lan ing console sampeyan ndeleng tumpukan pesen babagan. Sampeyan bisa maca liyane babagan tumpukan lan antrian ing artikel iki .

7. Marang kita bab Peta

Kaya sing kasebut ing ndhuwur, Peta minangka koleksi sing nduweni struktur antarmuka sing kapisah lan implementasine. Iki kapisah amarga ing kene nilai ora disimpen siji-sijine, nanging ing pasangan "nilai kunci". Metode Peta Dasar :

• sijine (tombol K, Nilai V) - nambah unsur menyang Peta;
• njaluk (tombol obyek) - nelusuri nilai kanthi kunci;
• containsKey(Obyek kunci) - mriksa Peta kanggo ngarsane tombol iki;
• containsValue (Nilai Obyek) - mriksa Peta kanggo anané nilai iki;
• mbusak (tombol obyek) - mbusak nilai kanthi tombol.

Kaya sing sampeyan ngerteni, umume operasi bisa digunakake kanthi nggunakake tombol. Minangka aturan, obyek sing ora bisa diganti dipilih minangka kunci . Conto khas obyek iki yaiku String . Implementasi Peta Dasar :

1. HashMap - dirancang kanggo nyimpen nilai kanthi acak, nanging ngidini sampeyan nggoleki unsur peta kanthi cepet. Ngidini sampeyan nemtokake kunci nggunakake tembung kunci null , nanging ora luwih saka sepisan, amarga pasangan karo tombol padha ditulis ing ndhuwur saben liyane. Kondisi utama yaiku keunikan tombol: nilai bisa diulang (bisa uga ana sawetara nilai null).
2. LinkedHashMap minangka analog saka HashMap sing nyimpen nilai miturut urutan sing ditambahake. Mulane, kaya LinkedList , nduweni header - kepala dhaptar sing disambung kaping pindho. Nalika diinisialisasi, iku nuduhake dhewe.

   LinkedHashMap uga nduweni accessOrder sing nemtokake cara unsur bakal diakses nalika iterator digunakake. Yen accessOrder palsu, akses bakal ditindakake miturut urutan unsur sing dilebokake. Yen bener, unsur kasebut bakal ana ing urutan diakses pungkasan (elemen sing diakses pungkasan bakal diselehake ing pungkasan).

3. TreeMap minangka Peta sing ngurutake unsur miturut nilai kunci. Padha karo TreeSet , nanging kanggo pasangan adhedhasar nilai kunci. Kanggo nyetel aturan ngurutake TreeMap , tombol kudu ngleksanakake antarmuka Comparable . Yen ora, kudu ana Key-oriented Comparator (sing kasebut ing konstruktor TreeMap ), TreeSet - diimplementasikake karo obyek TreeMap ing njero, sing nyatane kabeh keajaiban kedadeyan.

   Sampeyan bisa maca liyane babagan ngurutake ing TreeMap nggunakake wit abang-ireng ing artikel babagan fitur TreeMap .

4. Hashtable padha karo HashMap , nanging ora ngidini nulls disimpen minangka kunci utawa nilai. Diselarasake kanthi teliti saka sudut pandang multi-threading, sing tegese aman saka sudut pandang multi-threading. Nanging implementasine iki wis ketinggalan jaman lan alon, mula saiki sampeyan ora bakal bisa ndeleng Hashtable ing proyek anyar utawa kurang.

8. ArrayList vs LinkedList. Kang siji luwih apik kanggo nggunakake?

Pitakonan iki mbok menawa paling populer ing struktur data lan duwe sawetara pitfalls. Sadurunge mangsuli, ayo sinau luwih lengkap babagan struktur data kasebut. ArrayList ngetrapake antarmuka List lan ngoperasikake array internal sing ditambahi yen perlu. Nalika Uploaded internal wis rampung kapenuhan, lan unsur anyar kudu dilebokake, Uploaded anyar digawe karo ukuran (oldSize * 1,5) +1. Sawise iki, kabeh data saka array lawas disalin menyang unsur anyar + anyar, lan sing lawas bakal dibusak dening kolektor uwuh . Cara nambah nambahake unsur menyang sel kosong pungkasan ing array. Yaiku, yen kita wis duwe 3 unsur ing kana, bakal nambah sing sabanjure menyang sel kaping 4. Ayo goleki kinerja metode dhasar:

• njaluk (int index) - njupuk unsur ing array dening indeks paling cepet ing O (1) ;
• nambah (Obyek obj) - yen ana cukup papan ing Uploaded internal kanggo unsur anyar, banjur karo selipan normal O (1) wektu bakal ngginakaken , wiwit tambahan diangkah menyang sel pungkasan.

  Yen kita kudu nggawe larik anyar lan nyalin isi kasebut, banjur wektu kita bakal sebanding karo jumlah unsur ing larik O(n) ;

• mbusak (indeks int) - nalika mbusak unsur, contone, saka tengah, kita bakal O (n / 2) wektu, awit kita kudu mindhah unsur ing sisih tengen siji sel bali. Mulane, yen mbusak saka wiwitan dhaptar, banjur O(n), saka mburi - O(1);
• add (int index, Object obj) - kahanan sing padha mbusak: nalika nambah ing tengah, kita kudu mindhah unsur ing sisih tengen siji sel maju, supaya wektu O (n / 2). Mesthi, saka awal - O (n), saka mburi - O (1);
• set (indeks int, Obyek obj) - kene kahanan beda, wiwit sampeyan mung kudu golek unsur sing dipengini lan nulis liwat tanpa obah liyane, supaya O (1).

Waca liyane babagan ArrayList ing artikel iki . LinkedList ngleksanakake loro antarmuka bebarengan - Dhaftar lan Antrian , lan mulane nduweni sifat lan cara gawan ing loro struktur data. Saka List, dheweke entuk akses menyang unsur kanthi indeks, saka Queue - anane "sirah" lan "buntut". Secara internal, iki dileksanakake minangka struktur data sing makili dhaptar sing disambung kaping pindho. Yaiku, saben unsur nduweni pranala menyang sabanjure lan sadurunge, kajaba "buntut" lan "sirah".

• njaluk (int index) - nalika nelusuri unsur sing ana ing tengah dhaftar, iku wiwit nelusuri liwat kabeh unsur ing urutan nganti sing dikarepake ketemu. Logis, panelusuran kudu njupuk O(n/2) , nanging LinkedList uga duwe buntut, supaya panelusuran ditindakake bebarengan saka loro-lorone. Dadi, wektu dikurangi dadi O(n/4) .

  Yen unsur cedhak karo wiwitan dhaptar utawa pungkasan, banjur wektu bakal O (1) ;

• nambah (Obyek obj) - nalika nambah unsur anyar, unsur "buntut" bakal duwe link menyang unsur sabanjuré ditambahaké, lan anyar bakal nampa link menyang unsur sadurungé lan dadi anyar "buntut". Patut, wektu bakal O(1) ;
• mbusak (int index) - logika padha karo get(int index) method . Kanggo mbusak unsur saka tengah dhaftar, sampeyan kudu nemokake iku. Iki maneh O (n / 4) , nalika pambusakan dhewe bener njupuk apa-apa, awit iku mung ngganti pitunjuk saka obyek tetanggan (padha wiwit ngrujuk kanggo saben liyane). Yen unsur ana ing wiwitan utawa ing pungkasan, banjur maneh - O(1) ;
• add (int index, Object obj) lan set (int index, Object obj) - metode kasebut bakal duwe kerumitan wektu sing padha kanggo njaluk (int index) , amarga paling akeh wektu kanggo nggoleki unsur kasebut. Mulane, kanggo tengah dhaptar - O(n/4) , kanggo wiwitan - O(1).

Informasi liyane babagan nggarap LinkedList diterangake ing artikel iki . Ayo ndeleng kabeh iki ing tabel: Kaya sing wis dingerteni, sampeyan ora bisa mangsuli pitakon iki kanthi jelas. Sawise kabeh, ing macem-macem kahanan padha bisa ing kacepetan beda. Mulane, yen sampeyan dijaluk pitakonan kaya iki, sampeyan kudu langsung takon apa dhaptar iki bakal fokus lan operasi apa sing paling kerep ditindakake. Miwiti saka iki, menehi jawaban, nanging kanthi panjelasan kenapa kaya ngono. Ayo ngringkes perbandingan kita: ArrayList:

• pilihan sing paling apik yen operasi paling kerep nggoleki unsur, nimpa unsur;
• pilihan paling awon yen operasi selipan lan pambusakan ing awal-tengah, amarga operasi shift unsur ing sisih tengen bakal njupuk Panggonan.

LinkedList:

• pilihan sing paling apik yen operasi Kerep kita selipan lan pambusakan ing wiwitan-tengah;
• pilihan paling awon yen operasi paling umum nggoleki.

9. Kepiye unsur disimpen ing HashMap?

Koleksi HashMap ngemot tabel Node[] array internal , sel sing uga disebut buckets . Node ngandhut:

• kunci - link menyang kunci,
• nilai - referensi kanggo nilai,
• hash - nilai hash,
• sabanjuré - pranala menyang Node sabanjuré .

Siji sel saka tabel[] array bisa ngemot referensi menyang obyek Node kanthi pranala menyang unsur Node sabanjure , lan bisa uga duwe pranala menyang liyane, lan sateruse... Akibate, unsur Node iki bisa mbentuk dhaptar sing digandhengake siji-sijine , kanthi unsur-unsur kanthi pranala menyang sabanjure. Ing kasus iki, nilai hash saka unsur siji chain padha. Sawise digression cendhak, ayo ndeleng carane unsur disimpen ing HashMap :

1. Tombol dicenthang kanggo null . Yen null , banjur kunci bakal disimpen ing sel tabel[0] amarga kode hash kanggo null tansah 0.
2. Yen kunci ora null , banjur metode hashcode () obyek tombol diarani , sing bakal ngasilake kode hash. Kode hash iki digunakake kanggo nemtokake sel array ing ngendi obyek Node bakal disimpen.
3. Sabanjure, kode hash iki diselehake ing hash internal () cara , sing ngetung kode hash, nanging ing ukuran tabel [] array .
4. Sabanjure, gumantung saka nilai hash, Node diselehake ing sel tartamtu ing tabel [] array .
5. Yen sel tabel [] sing digunakake kanggo nyimpen unsur Node saiki ora kosong, nanging wis sawetara unsur, banjur unsur Node diulang liwat nilai sabanjuré nganti unsur pungkasan tekan. Yaiku , sing kolom sabanjure null .

   Sajrone panelusuran iki, kunci obyek Node sing dilindhungi dibandhingake karo tombol sing digoleki:

   • yen cocog ditemokake, telusuran bakal rampung, lan Node anyar bakal nimpa Node sing cocog ditemokake (mung kolom nilai sing bakal ditindih );
   • yen ora ana sing cocog karo tombol, banjur Node anyar bakal dadi sing pungkasan ing dhaptar iki, lan sing sadurunge bakal duwe link sabanjure .

Pitakonan asring muncul nalika wawancara: apa konflik ? Kahanan nalika sel saka Tabel[] array nyimpen ora siji unsur, nanging chain saka loro utawa luwih, disebut tabrakan a . Ing kasus normal ing ngendi mung siji unsur sing disimpen ing sel tabel siji [] , ngakses unsur HashMap nduweni kerumitan wektu O(1) konstan . Nanging nalika sèl karo unsur sing dipengini ngandhut chain saka unsur ( tabrakan ), banjur O (n) , wiwit ing kasus iki wektu iku langsung ceceg karo nomer unsur diurutake.

10. Nerangake iterator

Ing diagram pemetaan hirarki Koleksi ing ndhuwur, antarmuka Koleksi minangka ngendi kabeh hirarki diwiwiti, nanging ing praktik kasebut ora kaya ngono. Koleksi warisan saka antarmuka karo iterator () cara , kang ngasilake obyek sing ngleksanakake Iterator<E> antarmuka . Antarmuka Iterator katon kaya iki:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

sabanjuré () - dening nelpon cara iki, sampeyan bisa njaluk unsur sabanjuré. hasNext () - ngijini sampeyan kanggo mangerteni apa ana unsur sabanjuré, lan apa pungkasan koleksi wis tekan. Lan nalika isih ana unsur, hasNext () bakal bali true . Biasane, hasNext () disebut sadurunge sabanjuré () cara , wiwit sabanjuré () bakal uncalan NoSuchElementException nalika tekan mburi koleksi . mbusak () - Mbusak unsur sing dijupuk dening telpon pungkasan kanggo sabanjuré () . Tujuan saka Iterator yaiku kanggo ngulang unsur. Tuladhane:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

Bener, saben daur ulang dileksanakake ing sangisore hood nggunakake iterator. Sampeyan bisa maca liyane babagan iki kene . List nyedhiyakake versi iterator dhewe, nanging sing luwih adhem lan luwih canggih - ListIterator . Antarmuka iki ngluwihi Iterator lan duwe cara tambahan:

• hasPrevious bakal bali bener yen ana unsur sadurungé ing koleksi, palsu digunakake;
• sadurungé ngasilake unsur saiki lan pindhah menyang sing sadurunge; yen ora ana, banjur NoSuchElementException dibuwang;
• nambah bakal masang obyek liwati sadurunge unsur kanggo bali dening telpon sabanjuré kanggo sabanjuré () ;
• set menehi unsur saiki referensi kanggo obyek liwati;
• nextIndex ngasilake indeks saka unsur sabanjure. Yen ora ana sing kaya mengkono, ukuran dhaptar kasebut bali;
• PreviousIndex ngasilake indeks saka unsur sadurunge. Yen ora ana, banjur nomer -1 bali.

Nah, iku kabeh kanggo kula dina iki. Muga-muga sawise maca artikel iki, sampeyan luwih cedhak karo impen sing dikarepake - dadi pangembang.