Njelajah pitakonan lan jawaban saka wawancara proyek kanggo posisi pangembang Jawa. Bagian 9

Dadi programmer ora gampang. Tansah ana sing anyar kanggo sinau. Lan, kaya ing upaya liyane, sing paling angel yaiku miwiti, njupuk langkah pertama menyang tujuan sampeyan. Nanging amarga sampeyan wis ana ing kene lan maca artikel iki, sampeyan wis ngrampungake langkah pertama. Iki tegese saiki sampeyan kudu kanthi sengaja pindhah menyang tujuan sampeyan, tanpa alon-alon utawa miring. Aku nganggep tujuan sampeyan dadi pangembang Jawa utawa nambah kawruh yen sampeyan wis dadi pangembang. Yen mangkono, ayo terus ngrampungake dhaptar pitakonan wawancara pangembang Jawa. Ayo diterusake!

Koleksi

84. Marang kita bab iterator lan carane padha digunakake

Koleksi minangka topik favorit ing wawancara pangembang Java. Nalika mangsuli pitakon babagan hirarki koleksi, calon asring ujar manawa diwiwiti karo antarmuka Koleksi . Nanging iki ora kaya ngono. Ana antarmuka liyane siji tingkat ndhuwur: Iterable . Antarmuka iki kasusun saka iterator () cara, sing ngijini sampeyan ngakses obyek Iterator kanggo koleksi saiki. Lan apa persis obyek Iterator iki ? Obyek Iterator menehi kemampuan kanggo pindhah liwat koleksi lan iterate liwat unsur, lan pangguna ora perlu ngerti rincian implementasine tartamtu saka koleksi. Ing tembung liyane, iku jenis pointer kanggo unsur koleksi, kaya-kaya ngintip ing salah siji saka wong-wong mau. Iterator nduweni cara kayata:

• hasNext () - ngasilake bener yen pengulangan nduweni unsur liyane (cara iki ngidini sampeyan ngerti yen sampeyan wis tekan pungkasan koleksi);

• sabanjuré () - ngasilake item sabanjuré ing pengulangan. Yen ora ana siji, banjur NoSuchElementException dibuwang. Tegese sadurunge sampeyan nggunakake cara iki, iku paling apik nggunakake hasNext () cara kanggo mesthekake yen unsur sabanjuré ana;

• mbusak () - mbusak saka koleksi unsur pungkasan ditampa nggunakake sabanjuré () cara. Yen sabanjuré () wis tau disebut, banjur nelpon mbusak () bakal nimbulaké IllegalStateException di buwang;

• forEachRemaining(<Consumer>) - nglakokake tumindak sing dilewati ing saben unsur koleksi (cara iki muncul ing Jawa 8).

Iki minangka conto cilik saka iterasi liwat dhaptar lan mbusak kabeh unsur nggunakake macem-macem metode iterator sing kita deleng:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

Konsol bakal nampilake ing ngisor iki: Iki tegese unsur wis kasil dibusak. Sawise sampeyan entuk iterator, sampeyan bisa nggunakake cara kanggo nampilake kabeh unsur ing layar:

iterator.forEachRemaining(x -> System.out.print(x));

Nanging yen kita nindakake iki, iterator dadi ora cocog kanggo nggunakake luwih: wis traversed kabeh dhaftar, lan iterator biasa ora duwe cara kanggo iterasi mundur. Lan sing nggawe segue becik menyang diskusi LinkedList , khusus, cara listIterator () , sing ngasilake jinis iterator sing ditingkatake: ListIterator . Saliyane metode iterator biasa (standar), jinis iki nduweni:

• add (<Element>) - nambah unsur anyar menyang dhaptar;

• hasPrevious () - ngasilake bener yen ana unsur sing ana sadurunge unsur sabanjure (yen ana unsur sadurunge);

• nextIndex () - ngasilake indeks saka unsur sabanjuré;

• sadurungé () - ngasilake unsur sadurungé (siji sadurunge unsur sabanjuré);

• PreviousIndex ngasilake indeks saka unsur sadurunge.

• set (<Elemen>) - ngganti unsur pungkasan bali dening sabanjuré () utawa sadurungé () .

Kaya sing sampeyan ngerteni, iterator iki nduweni fungsi sing luwih menarik: ngidini sampeyan mlaku ing loro arah lan menehi kebebasan sing cukup nalika nggarap unsur. Sampeyan uga kudu ngerti yen nalika wong ngomong babagan iterator, kadang-kadang tegese pola desain kasebut dhewe.

85. Hierarki koleksi apa sing ana ing Kerangka Koleksi Jawa?

Ana rong hirarki koleksi ing Jawa. Hierarki pisanan yaiku hirarki Koleksi, sing nduweni struktur ing ngisor iki: Iki dipérang dadi subkoleksi ing ngisor iki:

• Set minangka antarmuka sing njlèntrèhaké sawijining set, struktur data sing ngemot unsur unik sing ora diurutake (ora diulang). Antarmuka iki nduweni sawetara implementasi standar: TreeSet , HashSet , lan LinkedHashSet .

• Dhaptar minangka antarmuka sing njlèntrèhaké struktur data sing nyimpen urutan obyek. Obyek ing Dhaptar bisa dilebokake lan dibusak dening indeks ing dhaptar (kaya array, nanging kanthi ukuran dinamis). Antarmuka iki uga nduweni sawetara implementasi standar: ArrayList , Vector ( deprecated and not actually used ), lan LinkedList .

• Antrian minangka antarmuka sing njlèntrèhaké struktur data sing nyimpen item ing antrian First In First Out (FIFO) . Antarmuka iki nduweni implementasi standar ing ngisor iki: LinkedList (pancen, uga ngetrapake Queue ) lan PriotityQueue .

Hierarki koleksi kapindho yaiku hirarki Peta , sing nduweni struktur ing ngisor iki: Hirarki koleksi iki ora ana divisi dadi subkoleksi (amarga hirarki Peta dhewe minangka subkoleksi sing madeg dhewe). Implementasi Peta standar yaiku Hashtable (ditinggalake), LinkedHashMap , lan TreeMap . Ing laku, nalika wong takon babagan Koleksi , biasane tegese loro hirarki.

86. Apa struktur internal ArrayList?

ArrayList kaya array, nanging bisa nggedhekake kanthi dinamis . Apa tegese? Ing hood, ArrayList nggunakake array biasa, yaiku nyimpen unsur ing array internal sing ukuran standar 10 sel. Sawise array internal kebak, array anyar digawe. Ukuran array anyar ditemtokake dening rumus iki:

<size of the current array> * 3 / 2 + 1

Dadi, yen ukuran array kita 10, banjur ukuran sing anyar bakal dadi: 10 * 3/2 + 1 = 16. Banjur kabeh nilai saka array asli (lawas) disalin menyang nggunakake built-in. System.arraycopy () cara, lan Uploaded asli dibusak. Cekakipun, punika cara ArrayList ngleksanakake pangowahan ukuran dinamis. Ayo dadi nimbang cara ArrayList paling populer : 1. nambah (<Elemen>) - nambah unsur menyang mburi Uploaded (ing sel kosong pungkasan), sawise pisanan mriksa apa ana sel kasedhiya ing Uploaded. Yen ora, larik anyar digawe, lan unsur disalin menyang. Kompleksitas wektu operasi iki yaiku O(1). Ana metode add(<Indeks>, <Elemen>) sing padha . Iku nambah unsur ora kanggo mburi dhaftar (larik), nanging kanggo sel tartamtu dituduhake dening indeks sing teka ing minangka pitakonan. Ing kasus iki, kerumitan wektu bakal beda-beda gumantung ing ngendi sampeyan nambah:

• yen tambah cedhak karo wiwitan dhaptar, banjur kerumitan wektu bakal cedhak karo O (N), amarga kabeh unsur sing ana ing sisih tengen sing anyar kudu dipindhah siji sel menyang sisih tengen;
• yen unsur dilebokake ing tengah, iku bakal O (N / 2), awit kita mung kudu ngalih setengah saka dhaftar item siji sel menyang tengen.

Tegese, kerumitan wektu cara iki kisaran saka O(1) nganti O(N), gumantung ing ngendi unsur dilebokake. 2. set (<Indeks>, <Unsur>) - nyerat unsur menyang posisi kasebut ing dhaftar. Yen unsur wis ana ing posisi kasebut, metode kasebut bakal nimpa. Kerumitan wektu operasi iki yaiku O (1), amarga ora kalebu operasi shift: kita mung nggunakake indeks kanggo ngetung alamat sel ing array, sing nduweni kerumitan O (1), banjur nulis unsur anyar. . 3. mbusak (<index>) - mbusak unsur dening indeks ing Uploaded internal. Nalika mbusak item sing ora ana ing mburi dhaptar, kabeh item ing sisih tengen sing dibusak kudu dipindhah siji sel menyang ngiwa kanggo nutup longkangan asil saka pambusakan. Mulane, kerumitan wektu bakal padha karo add(<Index>, <Element>) nalika unsur ditambahake ing tengah: O(N/2). Sawise kabeh, sampeyan kudu mindhah setengah saka unsur siji sel ing sisih kiwa. Lan yen kita ngomong babagan wiwitan, banjur O (N). Utawa yen ing mburi, banjur O (1), wiwit sampeyan ora perlu kanggo mindhah apa.

87. Apa struktur internal LinkedList?

ArrayList ngemot unsur ing array internal, nanging LinkedList nyimpen ing dhaptar dobel-link. Iki tegese saben unsur ngemot pranala menyang unsur sadurunge lan menyang unsur sabanjure . Unsur pisanan ora nyambung menyang unsur sadurunge (sawise kabeh, iku pisanan). Iki uga dianggep minangka kepala dhaptar, lan obyek LinkedList duwe referensi langsung. Kajaba iku, unsur pungkasan ora duwe unsur sabanjure, amarga iku buntut saka dhaftar. Objek LinkedList uga ngrujuk langsung. Iki tegese kerumitan wektu ngakses sirah utawa buntut dhaptar yaiku O (1). Ing ArrayList , yen dhaftar mundak akeh, banjur array internal mundak akeh. Ing kene kabeh luwih gampang: nambah referensi gampang kaya ngganti sawetara tautan. Ayo goleki sawetara cara LinkedList sing paling akeh digunakake: 1. nambah (<Elemen>) - nambah unsur ing pungkasan dhaptar, yaiku sawise unsur pungkasan (5), link menyang unsur anyar bakal ditambahake minangka sabanjure. . Referensi sadurunge ing unsur anyar bakal nuduhake unsur (5) sing saiki ndhisiki ing dhaptar. Kerumitan wektu operasi iki O (1), awit kita mung perlu link menyang unsur pungkasan, lan sing bakal ngelingi, obyek LinkedList referensi langsung kanggo buntut, lan ngakses wis minimal kerumitan wektu pancet. 2. nambah (<Indeks>, <Elemen>) - nambah unsur kanthi indeks. Nalika nambah unsur, ayo ngomong, ing tengah dhaftar, cara iki pisanan iterates liwat unsur saka sirah lan buntut (ing loro arah) nganti panggonan sing dipengini ketemu. Yen kita nambah unsur antarane unsur katelu lan papat (ing gambar ndhuwur), banjur link sabanjuré saka unsur katelu bakal nuding unsur anyar. Lan sadurunge saka unsur sing mentas ditambahake bakal nuding menyang sing katelu. Sabanjure, pranala lawas unsur papat lawas saiki bakal nuding menyang unsur anyar, lan pranala sabanjuré unsur anyar bakal nuding unsur papat anyar: Komplek wektu cara iki gumantung ing indeks saka unsur anyar:

• yen cedhak karo sirah utawa buntut, operasi bakal nyedhaki O (1), awit iku ora bener perlu kanggo iterate liwat unsur;
• yen cedhak karo tengah, kita bakal duwe O (N / 2), wiwit cara bakal nelusuri saka sirah lan buntut ing wektu sing padha nganti unsur sing dikarepake ditemokake.

3. set (<Indeks>, <Element>) - nulis unsur menyang posisi kasebut ing dhaftar. Kerumitan wektu operasi iki bakal sawetara saka O (1) kanggo O (N / 2), maneh gumantung carane cedhak unsur anyar kanggo sirah, buntut, utawa tengah. 4. mbusak (<index>) - mbusak unsur saka dhaftar dening nggawe supaya unsur sadurunge dibusak ( sadurunge ) saiki nuduhake unsur sawise dibusak ( sabanjure ). Lan kosok balene, yaiku unsur sawise sing dibusak saiki nuduhake siji sadurunge sing dibusak: Proses iki kebalikan saka nambah kanthi indeks ( add(<Index>, <Element>) ).

88. Apa struktur internal HashMap?

Iki bisa dadi salah sawijining pitakonan wawancara sing paling populer kanggo takon marang calon pangembang Jawa. A HashMap bisa digunakake karo pasangan kunci-nilai . Kepiye carane disimpen ing HashMap dhewe? HashMap nduweni susunan node internal:

Node<K,V>[] table

Kanthi gawan, ukuran array 16, lan tikel kaping pindho saben diisi unsur (yaiku, nalika LOAD_FACTOR tekan ; nemtokake batesan kanggo kebak array bisa entuk - minangka standar, yaiku 0.75 ) . Saben simpul nyimpen hash kunci, kunci, nilai, lan referensi kanggo unsur sabanjure: Ing kasus iki, "referensi kanggo unsur sabanjure" tegese kita lagi dealing karo dhaptar siji-disambung, ing ngendi saben unsur ngemot pranala menyang sabanjure. Ing tembung liyane, HashMap nyimpen data ing macem-macem dhaptar sing disambungake. Nanging supaya kula ngomong langsung yen sel saka Uploaded Tabel wis dhaftar siji-disambung sing kasusun saka luwih saka siji unsur, iku ora apik. Fenomena iki diarani tabrakan . Nanging dhisik dhisik. Ayo ndeleng carane pasangan anyar disimpen nggunakake metode put . Pisanan, metode kasebut entuk kode hash () kunci . Iki tegese supaya HashMap bisa digunakake kanthi bener, kunci sing sampeyan gunakake kudu kelas sing ngilangi metode iki. Kode hash iki banjur digunakake ing metode hash internal () kanggo nemtokake indeks sawetara sel ing array tabel. Indeks asil ngidini kita ngakses sel tartamtu saka array tabel. Kita duwe rong kasus ing kene:

1. Sèl kosong - ing kasus iki, nilai Node anyar disimpen ing njero.
2. Sèl ora kosong — ing kasus iki, nilai tombol dibandhingake. Yen padha, banjur Nilai Node anyar nimpa sing lawas; yen ora padha, banjur sabanjuré diakses , lan tombol dibandhingake ... Lan ing, nganti nilai anyar salah siji overwrites sawetara nilai lawas utawa kita tekan mburi singly disambung dhaftar lan banjur nyimpen nilai anyar ana minangka unsur pungkasan.

Nalika nggoleki unsur kanthi tombol (nggunakake metode get(<key>) ), kode hash () tombol diwilang, banjur indeks ing array diwilang nggunakake hash () . Nomer sing diasilake yaiku indeks sel ing array tabel , sing banjur kita telusuri kanthi ngulang simpul lan mbandhingake kunci simpul sing dikarepake karo kunci simpul saiki. Saenipun, operasi Map duwe kerumitan algoritma O (1), amarga kita ngakses Uploaded, lan, sing bakal ngelingi, O (1), preduli saka nomer unsur ngandhut. Nanging kita ora ngatasi kasus sing cocog. Nalika sel ora kosong (2) lan wis nyimpen sawetara kelenjar, banjur kerumitan algoritma dadi O (N) (linear), amarga saiki iku perlu kanggo iterate liwat unsur sadurunge kita nemokake panggonan tengen. Aku ora bisa nyebataken bilih wiwit ing Jawa 8, yen simpul ing wangun dhaptar siji-linked duwe luwih saka 8 unsur (tabrakan), banjur bakal diowahi dadi wit binar. Ing kasus iki, kerumitan algoritma ora maneh O (N), nanging O (log (N)) - lan iku kabeh prakara liyane, iku ora? HashMap minangka topik gedhe, lan wong seneng takon babagan iki ing wawancara kerja. Dadi, aku menehi saran supaya sampeyan ngerti kaya mburi tangan sampeyan. Secara pribadi, aku ora tau ngalami wawancara sing ora kalebu pitakonan ing HashMap . Sing kabeh kanggo dina iki. Diterusake...