Analisis pitakonan lan wangsulan saka wawancara kanggo pangembang Jawa. Bagian 9

Kembang api! Dadi programmer ora gampang. Sampeyan kudu terus sinau, tansah sinau sing anyar. Nanging, kaya ing bisnis liyane, sing paling angel yaiku miwiti, njupuk langkah pertama menyang tujuan sampeyan. Lan wiwit sampeyan lagi lungguh ing situs iki lan maca artikel iki, sampeyan wis rampung langkah pisanan. Iki tegese saiki sampeyan kudu kanthi sengaja pindhah menyang tujuan sampeyan, tanpa alon-alon utawa mateni ing dalan. Yen aku ngerti kanthi bener, tujuan sampeyan dadi pangembang Jawa utawa nambah kawruh yen sampeyan wis dadi siji. Yen mangkono, mula sampeyan ana ing papan sing bener, amarga kita bakal terus nganalisis dhaptar 250+ pitakonan wawancara pangembang Jawa. Ayo diterusake!

Koleksi

84. Nyritakake babagan iterator lan panggunaane

Koleksi minangka salah sawijining topik sing paling disenengi ing wawancara pangembang Jawa, lan nalika ngomong babagan hirarki koleksi, para calon asring ujar manawa diwiwiti kanthi antarmuka Koleksi . Nanging iki ora bener, amarga ing ndhuwur antarmuka iki ana siji liyane - Iterable . Antarmuka iki nggantosi iterator () cara , sing ngijini sampeyan kanggo nelpon obyek Iterator kanggo koleksi saiki. Lan apa persis obyek Iterator iki ? Iterator minangka obyek sing nyedhiyakake kemampuan kanggo mindhah koleksi lan ngulang unsur tanpa pangguna kudu ngerti implementasine koleksi tartamtu. Yaiku, iki minangka pitunjuk kanggo unsur-unsur koleksi, sing, kaya-kaya, katon ing papan tartamtu. Iterator nduweni cara ing ngisor iki:

• hasNext () - ngasilake bener yen ana unsur dumunung sawise pitunjuk (cara iki ngijini sampeyan kanggo mangerteni apa pungkasan koleksi wis tekan);
• sabanjuré () - ngasilake unsur sabanjuré sawise pitunjuk. Yen ora ana, NoSuchElementException dibuwang . Sing, sadurunge nggunakake cara iki, iku luwih apik kanggo mesthekake yen unsur ana - nggunakake hasNext () ;
• mbusak () - mbusak unsur pungkasan ditampa saka koleksi nggunakake sabanjuré () cara . Yen sabanjuré () wis tau disebut sadurunge mbusak () disebut, pangecualian bakal di buwang - IllegalStateException ;
• forEachRemaining(<Consumer>) - nindakake tumindak liwati karo saben unsur koleksi (cara muncul ing Jawa 8).

Iki minangka conto cilik saka iterasi liwat dhaptar lan mbusak kabeh unsur nggunakake metode iterator sing dibahas:

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: Iki tegese mbusak unsur wis sukses. Sawise kita duwe iterator, kita bisa nggunakake cara kanggo nyithak kabeh unsur menyang layar:

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

Nanging sawise iki, iterator bakal dadi ora cocog kanggo nggunakake luwih, amarga bakal ngliwati kabeh dhaftar, lan iterator biasa ora duwe cara kanggo backtracking. Ing kene kita mboko sithik nyedhaki LinkedList , yaiku, metode listIterator() , sing ngasilake jinis iterator sing dimodernisasi - ListIterator . Kejabi metode iterator biasa (standar), iki duwe tambahan:

• add (<Element>) - nglebokake unsur anyar menyang dhaptar;
• hasPrevious () - ngasilake bener yen ana unsur dumunung sadurunge pointer (apa ana unsur sadurungé);
• nextIndex () - ngasilake indeks ing dhaftar unsur sabanjuré sawise pitunjuk;
• sadurungé () - ngasilake unsur sadurungé (nganti pitunjuk);
• previousIndex () - ngasilake indeks saka unsur sadurungé;
• set (<Unsur>) - Ngganti unsur pungkasan bali dening sabanjuré () utawa sadurungé () cara .

Kaya sing sampeyan ngerteni, fungsi iterator iki luwih menarik: ngidini sampeyan pindhah ing arah loro lan mbebasake tangan nalika nggarap unsur. Uga, nalika wong ngomong babagan iterator, kadang-kadang tegese pola kasebut dhewe. Kanggo ngindhari masalah lan ngomong babagan iki kanthi yakin, waca artikel iki babagan pola Iterator .

85. Apa hierarki koleksi ing Java Collection Framework?

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

• Set minangka antarmuka sing njlèntrèhaké struktur data kaya set sing ngemot unsur unik (ora diulang). Antarmuka nduweni implementasi standar - TreeSet , HashSet lan LinkedHashSet .
• Dhaptar minangka antarmuka sing nggambarake struktur data sing nyimpen urutan obyek sing diurutake. Instance sing ana ing Dhaptar bisa dilebokake lan dibusak kanthi indeks ing koleksi iki (analog karo array, nanging kanthi ukuran dinamis). Antarmuka nduweni implementasi standar - ArrayList , Vector ( dianggep lungse lan ora bener digunakake ) lan LinkedList .
• Antrian minangka antarmuka sing njlèntrèhaké struktur data sing nyimpen unsur ing wangun antrian sing miturut aturan FIFO - First In First Out . Antarmuka nduweni implementasi standar ing ngisor iki: LinkedList (ya, uga ngetrapake Antrian ) lan PriotityQueue .

Hierarki koleksi kapindho yaiku Map , sing nduweni struktur ing ngisor iki: Ing koleksi iki ora ana divisi dadi subkoleksi (amarga hirarki Peta dhewe kaya subkoleksi, nanging ngapusi kanthi kapisah). Implementasi Peta Standar yaiku Hashtable (dianggap ora digunakake), LinkedHashMap lan TreeMap . Bener, nalika ditakoni babagan Koleksi , loro hierarki biasane dimaksudake.

86. Apa struktur internal ArrayList?

ArrayList mirip karo array, nanging kanthi kemampuan kanggo nggedhekake kanthi dinamis. Iki artine apa? Kasunyatane yaiku ArrayList bisa digunakake kanthi basis array biasa, yaiku, nyimpen unsur ing array internal (ukuran standar yaiku 10 sel). Nalika larik internal kebak, larik anyar digawe, ukurane ditemtokake dening rumus:

<размерТекущегоМассива> * 3 / 2  + 1

Yaiku, yen ukuran array kita 10, ukuran sing anyar bakal dadi: 10 * 3/2 + 1 = 16. Sabanjure, kabeh nilai saka array pisanan (lawas) disalin menyang nggunakake native System.arraycopy () cara , lan Uploaded pisanan dibusak. Bener, iki kepiye ekstensibilitas dinamis ArrayList diimplementasikake . Ayo kang katon ing cara ArrayList paling digunakake : 1. nambah (<Elemen>) - nambah unsur menyang mburi Uploaded (menyang sel kosong pungkasan), lan pisanan mriksa apa ana spasi ing Uploaded iki. Yen ora ana, array anyar digawe menyang unsur sing disalin. Kompleksitas logaritma operasi iki yaiku O(1). Ana cara sing padha - add(<Indeks>,<Elemen>) . Iku nambah unsur ora kanggo mburi dhaftar (larik), nanging kanggo sel tartamtu karo indeks sing teka minangka pitakonan. Ing kasus iki, kerumitan logaritma bakal beda-beda gumantung ing ngendi ditambahake:

• Yen iki kira-kira wiwitan dhaptar, kerumitan logaritma 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 - O (N / 2) amarga kita kudu mindhah mung setengah saka dhaftar unsur siji sel menyang tengen.

Tegese, kerumitan logaritma cara iki kisaran saka O(N) nganti O(1) gumantung ing ngendi unsur dilebokake. 2. set (<Indeks>,<Elemen>) - nyerat unsur menyang posisi kasebut ing dhaftar. Yen wis ana unsur ing posisi kasebut, timpa. Kompleksitas logaritma saka operasi iki O (1), amarga ora ana owah-owahan: mung nggoleki indeks ing array, sing, kaya sing kita eling, nduweni kerumitan O (1), lan nulis unsur kasebut. 3. mbusak (<index>) - mbusak unsur dening indeks ing Uploaded internal. Nalika mbusak item sing ora ana ing mburi dhaptar, sampeyan kudu mindhah kabeh item ing sisih tengen siji sel menyang kiwa kanggo nutup longkangan kiwa sawise mbusak item. Mulane, kerumitan logaritma bakal padha karo add(<Indeks>,<Elemen>) yen unsur ana ing tengah - O(N/2) - amarga sampeyan kudu mindhah setengah saka unsur siji ngiwa. Patut, yen ing wiwitan - O(N). Inggih, yen ing pungkasan iku O (1), ana ora perlu kanggo mindhah apa-apa. Kanggo sing pengin luwih jero babagan topik iki, aku bakal ninggalake link iki menyang artikel kanthi analisis kelas ArrayList .

87. Apa struktur internal LinkedList?

Yen ArrayList ngemot unsur ing array internal, LinkedList ana ing wangun dhaptar dobel link. Iki tegese saben unsur ngemot pranala menyang unsur sadurunge ( sadurunge ) lan sabanjure ( sabanjure ). Unsur pisanan ora duwe link menyang sadurunge (iku pisanan), nanging dianggep minangka kepala dhaptar, lan LinkedList duwe link langsung menyang. Unsur pungkasan, nyatane, ora duwe unsur sabanjure, iku buntut saka dhaftar, lan mulane ana link langsung menyang LinkedList dhewe . Mulane, kompleksitas logaritma kanggo ngakses sirah utawa buntut dhaptar yaiku O(1). Ing ArrayList, nalika dhaptar tambah akeh, array internal tambah, nanging ing kene kabeh kedadeyan luwih gampang - nalika nambah unsur, sawetara tautan mung ganti. Ayo katon ing sawetara cara LinkedlList paling digunakake : 1. nambah (<Elemen>) - nambah ing mburi dhaftar, i.e. sawise unsur pungkasan (5) pranala menyang unsur anyar bakal ditambahake minangka sabanjuré . Unsur anyar bakal duwe pranala menyang pungkasan (5) minangka unsur sadurunge . Kompleksitas logaritmik saka operasi kasebut bakal dadi O (1), amarga mung link menyang unsur pungkasan sing dibutuhake, lan nalika sampeyan ngelingi, buntut kasebut duwe link langsung saka LinkedList lan kerumitan logaritmik kanggo ngakses minimal. 2. nambah (<Indeks>,<Elemen>) - nambah unsur kanthi indeks. Nalika nambah unsur, contone, ing tengah dhaftar, unsur saka sirah lan buntut (ing loro-lorone) pisanan iterated nganti panggonan sing dikarepake. Yen kita pengin nglebokake unsur ing antarane pihak katelu lan kaping papat (ing gambar ndhuwur), banjur nalika nggoleki panggonan sing bener, link sabanjure unsur katelu bakal nuding menyang sing anyar. Kanggo sing anyar, pranala sadurunge bakal nuding menyang sing katelu. Patut, pranala saka unsur papat - sadurungé - bakal wis nuding menyang unsur anyar, lan pranala sabanjuré unsur anyar bakal nuding unsur papat: Komplek logaritmik saka cara iki bakal gumantung ing indeks diwenehi kanggo unsur anyar:

• yen cedhak karo sirah utawa buntut, iku bakal nyedhaki O (1), awit iku ora bener perlu kanggo iterate liwat unsur;
• yen cedhak karo tengah, banjur O(N/2) - unsur saka sirah lan buntut bakal diurutake bebarengan nganti unsur sing dibutuhake ditemokake.

3. set (<Indeks>,<Elemen>) - nyerat unsur menyang posisi kasebut ing dhaftar. Kompleksitas logaritma saka operasi iki bakal saka O (1) kanggo O (N/2), maneh gumantung carane cedhak unsur kanggo sirah, buntut, utawa tengah. 4. mbusak (<index>) - mbusak unsur saka dhaftar, ateges nggawe unsur sing teka sadurunge kang dibusak ( sadurunge ) referensi unsur sing teka sawise kang dibusak ( sabanjure ). Lan kosok balene: supaya unsur sing teka sawise sing dibusak nuduhake siji sing teka sadurunge sing dibusak: Asil proses kuwalik kanggo nambah dening indeks ( add(<Index>,<Elelement>) ). Kanggo sing pengin sinau luwih lengkap babagan struktur internal LinkedList , aku nyaranake maca artikel iki .

88. Apa struktur internal HashMap?

Mbok menawa salah sawijining pitakonan sing paling populer nalika wawancara karo pangembang Jawa. HashMap v dianggo karo pasangan kunci-nilai . Kepiye carane disimpen ing HashMapv dhewe ? Ing HashMap ana macem-macem node:

Node<K,V>[] table

Kanthi gawan, ukuran Uploaded 16, lan kaping pindho saben wektu kapenuhan unsur (nalika LOAD_FACTOR tekan - persentasi tartamtu saka fullness, minangka standar 0,75 ) . Saben simpul nyimpen hash saka kunci, kunci, nilai, lan pranala menyang unsur sabanjure: Bener, "link menyang unsur sabanjure" tegese kita dealing karo dhaptar sing disambung siji-sijine, ing ngendi saben unsur ngemot pranala menyang sabanjure. Yaiku, HashMap nyimpen data ing macem-macem dhaptar sing disambung. Nanging aku bakal langsung nyathet: nalika siji sel saka susunan tabel duwe pranala menyang dhaptar sing disambung sing padha sing dumadi saka luwih saka siji unsur, iki ora apik. Fenomena iki diarani tabrakan . Nanging dhisik dhisik. Ayo ndeleng carane pasangan anyar disimpen nggunakake metode put . Pisanan, hachCode () tombol dijupuk. Mulane, supaya peta hash bisa mlaku kanthi bener , sampeyan kudu njupuk kelas sing cara iki diganti minangka kunci. Kode hash iki banjur digunakake ing cara internal - hash () - kanggo nemtokake nomer ing ukuran array tabel . Sabanjure, nggunakake nomer sing ditampa, sel tartamtu saka array tabel diakses . Ing kene kita duwe rong kasus:

1. Sèl kosong - nilai Node anyar disimpen ing njero .
2. Sèl ora kosong - nilai tombol dibandhingake. Yen padha, nilai Node anyar bakal nimpa sing lawas, yen ora padha, unsur sabanjure diakses lan dibandhingake karo tombol ... dhaptar sing disambung lan bakal disimpen ana minangka unsur pungkasan.

Nalika nggoleki unsur kanthi kunci ( metode get(<key>) ), kode hash saka kunci kasebut diitung, banjur nilai ing array nggunakake hash() , lan nggunakake nomer asil, sel saka array tabel ditemokake. , ing ngendi telusuran wis ditindakake kanthi ngitung simpul lan mbandhingake kunci simpul sing dikarepake karo kunci sing saiki. Operasi ing Peta ing kahanan becik duwe kerumitan algoritma O (1), amarga padha ngakses Uploaded, lan sing elinga, preduli saka nomer unsur, operasi ing Uploaded duwe kerumitan O (1). Nanging iki becik. Nalika sel array sing digunakake ora kosong (2) lan wis ana sawetara simpul ing kana, kerumitan algoritmik dadi linear O (N), amarga saiki perlu kanggo ngulang unsur sadurunge nemokake panggonan sing bener. Aku ora bisa bantuan nanging sebutno iki: miwiti karo Jawa 8, yen singly linked dhaftar simpul wis luwih saka 8 unsur (tabrakan), iku dadi wit binar. Ing kasus iki, kerumitan algoritma ora bakal dadi O (N), nanging O (log (N)) - iku masalah liyane, ta? HashMap minangka topik gedhe, lan wong seneng takon babagan iki nalika wawancara. Mulane, aku menehi saran supaya sampeyan ngerti kanthi rinci (supaya mumbul saka untune). Secara pribadi, aku ora duwe wawancara tanpa pitakonan HashMap . Sampeyan bisa nemokake nyilem jero menyang HashMap ing artikel iki . Iku kabeh kanggo dina iki, kanggo nerusake ...