Paggalugad ng mga tanong at sagot mula sa isang job interview para sa isang Java developer position. Bahagi 9

Ang pagiging programmer ay hindi madali. Laging may bagong matututunan. At, tulad ng anumang iba pang pagsisikap, ang pinakamahirap na bagay ay magsimula, gawin ang unang hakbang patungo sa iyong layunin. Ngunit dahil narito ka na at binabasa ang artikulong ito, nakumpleto mo na ang unang hakbang. Nangangahulugan ito na ngayon ay kailangan mong sadyang lumipat patungo sa iyong layunin, nang hindi bumabagal o lumilihis sa gilid. Ipinapalagay ko na ang iyong layunin ay maging isang developer ng Java o dagdagan ang iyong kaalaman kung isa ka nang developer. Kung gayon, magpatuloy tayo sa pagharap sa isang malawak na listahan ng mga tanong sa panayam ng developer ng Java. Ituloy natin!

Mga koleksyon

84. Sabihin sa amin ang tungkol sa mga iterator at kung paano ginagamit ang mga ito

Ang mga koleksyon ay isang paboritong paksa sa anumang panayam ng developer ng Java. Kapag sumasagot sa mga tanong tungkol sa hierarchy ng koleksyon, kadalasang sinasabi ng mga kandidato na nagsisimula ito sa interface ng Collection . Ngunit hindi ito ganoon. May isa pang interface sa isang antas sa itaas: Iterable . Binubuo ang interface na ito ng iterator() method, na nagbibigay-daan sa iyong ma-access ang Iterator object para sa kasalukuyang koleksyon. At ano nga ba ang Iterator object na ito? Ang bagay na Iterator ay nagbibigay ng kakayahang lumipat sa isang koleksyon at umulit sa mga elemento nito, at hindi kailangang malaman ng user ang mga partikular na detalye ng pagpapatupad ng koleksyon. Sa madaling salita, ito ay isang uri ng pointer sa mga elemento ng koleksyon, na parang nakasilip sa loob ng isa sa mga ito. Ang iterator ay may mga pamamaraan tulad ng:

• hasNext() — nagbabalik ng true kung ang pag-ulit ay may isa pang elemento (ang pamamaraang ito ay nagpapaalam sa iyo kapag naabot mo na ang dulo ng koleksyon);

• next() — ibinabalik ang susunod na item sa iteration. Kung walang isa, pagkatapos ay isang NoSuchElementException ay itinapon. Nangangahulugan iyon na bago mo gamitin ang paraang ito, pinakamahusay na gamitin ang hasNext() na paraan upang matiyak na mayroong susunod na elemento;

• remove() — inaalis mula sa koleksyon ang huling elementong natanggap gamit ang susunod na() na pamamaraan. Kung ang next() ay hindi pa natawagan, ang pagtawag sa remove() ay magdudulot ng isang IllegalStateException na itapon;

• forEachRemaining(<Consumer>) — nagsasagawa ng ipinasa na aksyon sa bawat elemento ng koleksyon (lumalabas ang paraang ito sa Java 8).

Narito ang isang maliit na halimbawa ng pag-ulit sa isang listahan at pag-alis ng lahat ng mga elemento nito gamit ang iba't ibang mga pamamaraan ng iterator na aming tiningnan:

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());

Ipapakita ng console ang sumusunod: Nangangahulugan ito na matagumpay na naalis ang mga elemento. Kapag nakakuha ka ng isang iterator, maaari kang gumamit ng isang paraan upang ipakita ang lahat ng mga elemento sa screen:

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

Ngunit sa sandaling gawin natin ito, ang iterator ay nagiging hindi na angkop para sa karagdagang paggamit: ito ay dumaan sa buong listahan, at ang isang ordinaryong iterator ay walang mga pamamaraan para sa pag-ulit pabalik. At iyon ay gumagawa para sa isang magandang segue sa isang talakayan ng LinkedList , partikular, ang listIterator() na pamamaraan nito, na nagbabalik ng pinahusay na uri ng iterator: ListIterator . Bilang karagdagan sa mga pamamaraan ng isang regular (karaniwang) iterator, ang ganitong uri ay may mga sumusunod:

• add(<Element>) — nagdaragdag ng bagong elemento sa listahan;

• hasPrevious() — nagbabalik ng true kung mayroong isang elemento na matatagpuan bago ang susunod na elemento (kung mayroong isang nakaraang elemento);

• nextIndex() — ibinabalik ang index ng susunod na elemento;

• previous() — ibinabalik ang nakaraang elemento (ang isa bago ang susunod na elemento);

• Ibinabalik ng previousIndex ang index ng nakaraang elemento.

• set(<Element>) — pinapalitan ang huling elementong ibinalik ng next() o previous() .

Gaya ng nakikita mo, ang iterator na ito ay may mas kawili-wiling pag-andar: hinahayaan kang maglakad sa magkabilang direksyon at nagbibigay ng malaking kalayaan kapag nagtatrabaho sa mga elemento. Dapat mo ring malaman na kapag pinag-uusapan ng mga tao ang tungkol sa mga iterator, kung minsan ang ibig sabihin nila ay ang mismong pattern ng disenyo.

85. Anong collection hierarchy ang umiiral sa Java Collection Framework?

Mayroong dalawang hierarchy ng koleksyon sa Java. Ang unang hierarchy ay ang Collection hierarchy, na may sumusunod na istraktura: Ito ay nahahati sa mga sumusunod na subcollections:

• Ang set ay isang interface na naglalarawan sa isang set, isang istraktura ng data na naglalaman ng hindi nakaayos na natatanging (hindi umuulit) na mga elemento. Ang interface na ito ay may ilang karaniwang pagpapatupad: TreeSet , HashSet , at LinkedHashSet .

• Ang listahan ay isang interface na naglalarawan ng istraktura ng data na nag-iimbak ng isang nakaayos na pagkakasunud-sunod ng mga bagay. Ang mga bagay sa isang Listahan ay maaaring ipasok at alisin sa pamamagitan ng kanilang index sa listahan (tulad ng isang array, ngunit may dynamic na pagbabago ng laki). Ang interface na ito ay mayroon ding ilang karaniwang pagpapatupad: ArrayList , Vector ( deprecated and not actually used ), at LinkedList .

• Ang Queue ay isang interface na naglalarawan ng istraktura ng data na nag-iimbak ng mga item sa isang First In First Out (FIFO) queue. Ang interface na ito ay may mga sumusunod na karaniwang pagpapatupad: LinkedList (tama, nagpapatupad din ito ng Queue ) at PriotityQueue .

Ang pangalawang hierarchy ng koleksyon ay ang Map hierarchy, na may sumusunod na istraktura: Ang collection hierarchy na ito ay walang mga dibisyon sa mga subcollections (dahil ang Map hierarchy mismo ay isang subcollection na hiwalay sa sarili nitong). Ang mga karaniwang pagpapatupad ng Map ay Hashtable (hindi na ginagamit), LinkedHashMap , at TreeMap . Sa pagsasagawa, kapag nagtanong ang mga tao tungkol sa Mga Koleksyon , karaniwan nilang ibig sabihin ay parehong hierarchy.

86. Ano ang panloob na istraktura ng isang ArrayList?

Ang ArrayList ay parang array, ngunit maaari itong lumawak nang pabago-bago. Anong ibig sabihin niyan? Sa ilalim ng hood, gumagamit ang ArrayList ng isang ordinaryong array, ibig sabihin, iniimbak nito ang mga elemento nito sa isang panloob na array na ang default na laki ay 10 cell. Kapag puno na ang panloob na array, gagawa ng bagong array. Ang laki ng bagong array ay tinutukoy ng formula na ito:

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

Kaya, kung ang laki ng aming array ay 10, kung gayon ang laki ng bago ay: 10 * 3 / 2 + 1 = 16. Pagkatapos ang lahat ng mga halaga mula sa orihinal (lumang) array ay kinopya dito gamit ang built-in System.arraycopy() method, at ang orihinal na array ay tatanggalin. Sa madaling sabi, iyan ay kung paano ipinapatupad ng ArrayList ang dynamic na pagbabago ng laki. Isaalang-alang natin ang pinakasikat na paraan ng ArrayList : 1. add(<Element>) — nagdaragdag ng elemento sa dulo ng array (sa huling walang laman na cell), pagkatapos munang suriin kung mayroong available na cell sa array. Kung hindi, ang isang bagong array ay nilikha, at ang mga elemento ay kinopya dito. Ang pagiging kumplikado ng oras ng operasyong ito ay O(1). Mayroong katulad na paraan ng add(<Index>, <Elelement>) . Nagdaragdag ito ng elemento hindi sa dulo ng listahan (array), ngunit sa partikular na cell na ipinahiwatig ng index na pumasok bilang argumento. Sa kasong ito, ang pagiging kumplikado ng oras ay mag-iiba depende sa kung saan mo idaragdag:

• kung ang pagdaragdag ay malapit sa simula ng listahan, ang pagiging kumplikado ng oras ay magiging malapit sa O(N), dahil ang lahat ng mga elemento na matatagpuan sa kanan ng bago ay kailangang ilipat ng isang cell sa kanan;
• kung ang elemento ay ipinasok sa gitna, ito ay magiging O(N/2), dahil kailangan lang nating ilipat ang kalahati ng mga item sa listahan ng isang cell sa kanan.

Ibig sabihin, ang pagiging kumplikado ng oras ng pamamaraang ito ay mula sa O(1) hanggang O(N), depende sa kung saan ipinapasok ang elemento. 2. set(<Index>, <Element>) — nagsusulat ng elemento sa tinukoy na posisyon sa listahan. Kung ang isang elemento ay naroroon na sa posisyong iyon, ang pamamaraan ay na-overwrite ito. Ang pagiging kumplikado ng oras ng operasyong ito ay O(1), dahil hindi ito nagsasangkot ng anumang mga pagpapatakbo ng shift: ginagamit lang namin ang index upang kalkulahin ang address ng cell sa array, na may kumplikadong O(1), at pagkatapos ay isulat ang bagong elemento . 3. remove(<index>) — inaalis ang isang elemento sa pamamagitan ng index nito sa internal array. Kapag nag-aalis ng isang item na wala sa dulo ng listahan, ang lahat ng mga item sa kanan ng tinanggal ay dapat ilipat ang isang cell sa kaliwa upang isara ang puwang na nagreresulta mula sa pagtanggal. Alinsunod dito, ang pagiging kumplikado ng oras ay magiging kapareho ng para sa add(<Index>, <Element>) kapag may idinagdag na elemento sa gitna: O(N/2). Pagkatapos ng lahat, kailangan mong ilipat ang kalahati ng mga elemento sa isang cell sa kaliwa. At kung pinag-uusapan natin ang simula, pagkatapos ay O(N). O kung sa dulo, pagkatapos ay O(1), dahil hindi mo kailangang ilipat ang anuman.

87. Ano ang panloob na istraktura ng isang LinkList?

Ang isang ArrayList ay naglalaman ng mga elemento sa panloob na hanay, ngunit ang isang LinkedList ay nag-iimbak sa kanila sa isang dobleng naka-link na listahan. Nangangahulugan ito na ang bawat elemento ay naglalaman ng isang link sa nakaraang elemento at sa susunod na elemento. Ang unang elemento ay hindi naka-link sa isang nakaraang elemento (pagkatapos ng lahat, ito ang una). Ito rin ay itinuturing na pinuno ng listahan, at ang LinkList object ay may direktang sanggunian dito. Katulad nito, ang huling elemento ay walang susunod na elemento, dahil ito ang buntot ng listahan. Direkta rin itong tinutukoy ng object na LinkList . Nangangahulugan ito na ang pagiging kumplikado ng oras ng pag-access sa ulo o buntot ng isang listahan ay O(1). Sa ArrayList , kung lumalaki ang listahan, lalago ang panloob na array. Dito mas madali ang lahat: ang pagdaragdag ng reference ay kasing simple ng pagpapalit ng ilang link. Tingnan natin ang ilan sa mga pinaka ginagamit na pamamaraan ng LinkedList : 1. add(<Element>) — nagdaragdag ng elemento sa dulo ng listahan, ibig sabihin, pagkatapos ng huling elemento (5), isang link sa bagong elemento ang idadagdag bilang susunod. . Ang nakaraang sanggunian sa bagong elemento ay ituturo sa elemento (5) na nauuna ngayon dito sa listahan. Ang pagiging kumplikado ng oras ng operasyong ito ay O(1), dahil kailangan lang namin ng link sa huling elemento, at bilang iyong matatandaan, ang LinkedList object ay may direktang sanggunian sa buntot, at ang pag-access dito ay may kaunting pare-parehong kumplikadong oras. 2. add(<Index>, <Element>) — nagdaragdag ng elemento ayon sa index. Kapag nagdaragdag ng elemento, sabihin nating, sa gitna ng isang listahan, ang pamamaraang ito ay unang umuulit sa mga elemento mula sa ulo at buntot (sa magkabilang direksyon) hanggang sa matagpuan ang nais na lugar. Kung magdaragdag tayo ng elemento sa pagitan ng ikatlo at ikaapat na elemento (sa larawan sa itaas), ang susunod na link ng ikatlong elemento ay ituturo sa bagong elemento. At ang nakaraan ng bagong idinagdag na elemento ay ituturo sa pangatlo. Sa turn, ang dating link ng lumang ikaapat na elemento ay tuturo na ngayon sa bagong elemento, at ang susunod na link ng bagong elemento ay ituturo sa bagong ikaapat na elemento: Ang pagiging kumplikado ng oras ng pamamaraang ito ay depende sa index ng bagong elemento:

• kung ito ay malapit sa ulo o buntot, ang operasyon ay lalapit sa O(1), dahil hindi naman talaga ito kakailanganing umulit sa mga elemento;
• kung ito ay malapit sa gitna, magkakaroon tayo ng O(N/2), dahil ang pamamaraan ay maghahanap mula sa ulo at buntot nang sabay hanggang sa matagpuan ang nais na elemento.

3. set(<Index>, <Element>) — nagsusulat ng elemento sa tinukoy na posisyon sa listahan. Ang pagiging kumplikado ng oras ng operasyong ito ay mula sa O(1) hanggang O(N/2), muli depende sa kung gaano kalapit ang bagong elemento sa ulo, buntot, o gitna. 4. remove(<index>) — nag-aalis ng isang elemento mula sa listahan sa pamamagitan ng paggawa nito upang ang elemento bago ang tinanggal ( nakaraan ) ay tumutukoy na ngayon sa elemento pagkatapos ng tinanggal na isa ( susunod ). At kabaligtaran, ibig sabihin, ang elemento pagkatapos ng tinanggal ay tumutukoy na ngayon sa isa bago ang tinanggal: Ang prosesong ito ay kabaligtaran ng pagdaragdag sa pamamagitan ng index ( add(<Index>, <Element>) ).

88. Ano ang panloob na istraktura ng isang HashMap?

Ito ay maaaring isa sa mga pinakasikat na tanong sa panayam na itatanong sa mga kandidato ng developer ng Java. Gumagana ang isang HashMap sa mga pares ng key-value . Paano sila nakaimbak sa loob mismo ng HashMap ? Ang isang HashMap ay may panloob na hanay ng mga node:

Node<K,V>[] table

Bilang default, ang laki ng array ay 16, at ito ay nagdodoble sa bawat oras na ito ay puno ng mga elemento (iyon ay, kapag ang LOAD_FACTOR ay naabot; ito ay tumutukoy sa threshold para sa kung gaano kabuo ang array ay maaaring makuha - bilang default, ito ay 0.75 ) . Ang bawat isa sa mga node ay nag-iimbak ng isang hash ng key, ang susi, isang halaga, at isang reference sa susunod na elemento: Sa kasong ito, ang "reference sa susunod na elemento" ay nangangahulugan na kami ay nakikitungo sa isang solong-link na listahan, kung saan ang bawat elemento ay naglalaman ng isang link patungo sa susunod. Sa madaling salita, ang isang HashMap ay nag-iimbak ng data nito sa isang hanay ng mga single-linked na listahan. Ngunit sabihin ko kaagad na kapag ang isang cell ng hanay ng talahanayan ay may isang solong naka-link na listahan na binubuo ng higit sa isang elemento, iyon ay hindi mabuti. Ang kababalaghang ito ay tinatawag na banggaan . Ngunit una sa lahat. Tingnan natin kung paano nai-save ang isang bagong pares gamit ang put method. Una, nakukuha ng pamamaraan ang hashCode() ng susi . Ipinahihiwatig nito na upang gumana nang tama ang isang HashMap , ang mga susi na iyong ginagamit ay dapat na mga klase na nag-o-override sa paraang ito. Ang hash code na ito ay gagamitin sa internal hash() na paraan upang matukoy ang isang index ng ilang cell sa loob ng table array. Ang resultang index ay nagpapahintulot sa amin na ma-access ang isang partikular na cell ng table array. Mayroon kaming dalawang kaso dito:

1. Ang cell ay walang laman — sa kasong ito, ang bagong halaga ng Node ay nakaimbak dito.
2. Walang laman ang cell — sa kasong ito, inihahambing ang mga halaga ng mga susi. Kung pantay-pantay ang mga ito, ang bagong halaga ng Node ay ma-overwrite ang luma; kung hindi katumbas, ang susunod ay maa-access, at ang susi nito ay inihahambing... At iba pa, hanggang sa ma-overwrite ng bagong halaga ang ilang lumang halaga o maabot natin ang dulo ng isa-isang naka-link na listahan at pagkatapos ay iimbak ang bagong halaga doon bilang ang huling elemento.

Kapag naghahanap ng elemento sa pamamagitan ng key (gamit ang get(<key>) method), ang hashCode() ng key ay kinakalkula, at pagkatapos ay ang index nito sa loob ng array ay kinakalkula gamit ang hash() . Ang resultang numero ay ang index ng isang cell sa hanay ng talahanayan , na pagkatapos ay hahanapin namin sa pamamagitan ng pag-ulit sa mga node at paghahambing ng susi ng nais na node sa susi ng kasalukuyang node. Sa isip, ang mga pagpapatakbo ng Map ay may algorithmic complexity ng O(1), dahil ina-access namin ang isang array, at, tulad ng maaalala mo, ay O(1), anuman ang bilang ng mga elementong nilalaman nito. Ngunit hindi namin nakikitungo sa perpektong kaso. Kapag ang cell ay walang laman (2) at nag-imbak na ng ilang mga node, ang algorithmic complexity ay nagiging O(N) (linear), dahil ngayon ay kinakailangan na ulitin ang mga elemento bago natin mahanap ang tamang lugar. Hindi ko maiwasang banggitin na simula sa Java 8, kung ang isang node sa anyo ng isang single-linked na listahan ay may higit sa 8 elemento (mga banggaan), pagkatapos ay mako-convert ito sa isang binary tree. Sa kasong ito, ang algorithmic complexity ay hindi na O(N), ngunit O(log(N)) — at iyon ay isang buong ibang bagay, hindi ba? Ang HashMap ay isang malaking paksa, at gustong magtanong ng mga tao tungkol dito sa mga panayam sa trabaho. Kaya, iminumungkahi ko na alam mo ito tulad ng likod ng iyong kamay. Sa personal, hindi pa ako nagkaroon ng panayam na hindi kasama ang mga tanong sa HashMap . Yan lamang para sa araw na ito. Itutuloy...