Söhbetdeşlikde sorajak zatlary: Java-daky maglumatlar gurluşlary. 2-nji bölüm

1-nji BÖLÜM Indi her Java döredijiniň bilmeli esaslary hakda gürleşýäris. Bularyň hemmesiniň başlaýan nusgawy bilimleri hakda. Bu gün islendik söhbetdeşligiň esasy mowzuklaryndan biri - Java-daky maglumat gurluşlary barada durup geçmek isleýärin . Şeýlelik bilen, gyrymsylygyň töwereginde urmagyň ýerine başlalyň. Söhbetdeşlik wagtynda bu mowzukda size berilip bilinjek soraglaryň sanawynyň dowamyny ele alyň.

6. Sanaw hakda bize aýdyň

Sanaw, sanaw diýlip atlandyrylýan obýektleriň tertipli gurluşyny görkezýän interfeýsdir. Bu gurluşyň “hilesi”, Sanawdaky elementleriň indeks, ýagny sanawyň içki kesgitleýjisi bilen girizilip, üýtgedilip ýa-da pozulmagydyr . Başgaça aýdylanda, indeks: “sanawyň başyndan näçe element bar” diýmekdir. Birinji sanaw elementinde 0 indeks, ikinjisinde 1 indeks we ş.m. Şeýlelik bilen bäşinji element sanawyň başyndan dört element uzaklykda. Aboveokarda belläp geçişimiz ýaly, sanawda elementleriň goşulmagynyň tertibi möhümdir. Şonuň üçin maglumat gurluşyna sanaw diýilýär . Elementler bilen işlemäge gönükdirilen bu gurluşa mahsus usullary sanap geçýäris:

• almak - görkezilen elementi görkezýär (indeks bahasy boýunça),
• aýyrmak - görkezilen ýagdaýda elementi aýyrýar,
• set - görkezilen ýerdäki elementi usulda görkezilen element bilen çalyşýar.

Esasy ýerine ýetirişler “ArrayList” we “LinkedList” . Biraz soň olar hakda has giňişleýin gürleşeris. Wektor sapakdan ygtybarly sanaw, şonuň üçin bu synpdaky her bir usul sinhronlaşdyrylýar. Listöne ýadyňyzdan çykarmaň, käbir sanaw hereketlerini goramak isleseňiz, amallaryň tutuş yzygiderliligini sinhronlaşdyrarsyňyz. Aýry-aýry amallary sinhronlamak hem az ygtybarly, hem haýal. Elbetde, gulp gerek däl bolsa-da, Vektoryň üstünde gulplama bar. Şonuň üçin bu synp indi köne hasaplanýar we ulanylmaýar. Theeri gelende aýtsak, “ArrayList” “Vektor” -a meňzeýär , ýöne gulpy ulanmaýar, şonuň üçin hemme ýerde ulanylýar. Stack , bir deslapky konstruktor we Vektor synpynyň ähli usullary , üstesine-de birnäçe görnüşi bolan Vektor synpynyň kiçi toparydyr (bu hakda soňrak gürleşeris). Mysal hökmünde, prosesi resminamalar bilen bukjalar toplumy hökmünde göz öňüne getirip bilersiňiz. Bir bukjany stakanyň ýokarsyna ýerleşdirýärsiňiz we bu bukjalary diňe ýokardan başlap ters tertipde alyp bilersiňiz. Aslynda, bu LIFO görnüşli mehanizm , ýagny “ Iň soňky çykan” , iň soňky gelen ilkinji. Stack öz usullaryny durmuşa geçirýär:

• iteklemek - geçen elementi stakanyň ýokarsyna goşýar;
• peek - stakanyň ýokarsyndaky elementi gaýtaryp berýär;
• pop - stakanyň ýokarsyndaky elementi hem yzyna berýär, ýöne ony aýyrýar;
• boş - stakanyň boşdygyny ýa-da ýokdugyny barlaýar - ýalan ;
• gözlemek - berlen element üçin stakany gözleýär. Eger bir element tapylsa, stakanyň ýokarsyna degişlilikde yzygiderlilik belgisi yzyna gaýtarylýar. Element tapylmasa -1 bahasy yzyna gaýtarylýar.

Häzirki wagtda “Stack” kiçi klassy ýönekeýligi we çeýeligi sebäpli aslynda ulanylmaýar, ýöne muňa garamazdan, duşup bilersiňiz. Mysal üçin, haýsydyr bir ýalňyşlyk alanyňyzda we konsolda bu hakda bir topar habar görýärsiňiz. Stak we nobat hakda has giňişleýin maglumaty şu makalada okap bilersiňiz .

7. Karta barada bize aýdyň

Aboveokarda aýdylyşy ýaly, Karta interfeýsleriň aýratyn gurluşy we ýerine ýetirilişi bolan ýygyndydyr. Aýry-aýry, sebäbi bu ýerde bahalar bir gezekde däl-de, “açar-baha” jübütinde saklanýar. Kartanyň esasy usullary :

• goý (K düwmesi, V bahasy) - Kartada element goşmak;
• almak (Obýekt açary) - açar boýunça baha gözlemek;
• içindeKey (Obýekt açary) - Kartany bu açaryň bardygyny barlaýar;
• içindeValue (Obýektiň bahasy) - bu bahanyň bardygyny Kartany barlaýar;
• aýyrmak (Obýekt açary) - açary bilen bahany aýyrmak.

Görşüňiz ýaly, amallaryň köpüsi açar ulanyp işleýär. Düzgün bolşy ýaly, üýtgewsiz zatlar açar hökmünde saýlanýar . Bu obýektiň adaty mysaly Stringdir . Kartanyň esasy durmuşa geçirilmegi :

1. HashMap - bahalary tötänleýin tertipde saklamak üçin döredilen, ýöne karta elementlerini çalt gözlemäge mümkinçilik berýär. Nul açar sözüni ulanyp açary kesgitlemäge mümkinçilik berýär , ýöne bir gezekden köp däl, sebäbi birmeňzeş düwmelerli jübütler biri-biriniň üstünde ýazylýar. Esasy şert, düwmeleriň özboluşlylygy: bahalar gaýtalanyp bilner (birnäçe null bahalar bolup biler).
2. LinkedHashMap, bahalary goşulan tertipde saklaýan HashMap-yň meňzeşidir . Şoňa görä-de, LinkedList ýaly , bir sözbaşy bar - iki gezek baglanyşdyrylan sanawyň başlygy. Başlananda, özüni görkezýär.

   “LinkedHashMap” -da iterator ulanylanda elementlere nädip girip boljakdygyny kesgitleýän “AccessOrder” hem bar . “AccessOrder” ýalňyş bolsa , giriş elementleriň goýlan tertibi boýunça ýerine ýetiriler. Çyn bolsa , elementler iň soňky giriş tertibinde bolar (iň soňky giriş elementi ahyrynda ýerleşdiriler).

3. TreeMap , elementleri esasy bahalar boýunça tertipleýän karta . TreeSet -e meňzeýär , ýöne esasy gymmatlyklara esaslanýan jübütler üçin. TreeMap sortlamak düzgünlerini bellemek üçin düwmeler Deňeşdirilýän interfeýsi durmuşa geçirmeli . Otherwiseogsam, açara gönükdirilen deňeşdiriji ( TreeMap konstruktorynda görkezilen ), TreeSap - içindäki TreeMap obýekti bilen ýerine ýetirilen, aslynda ähli jadyly bolup geçýän TreeSet bolmaly .

   TreeMap-da aýratynlyklar barada makalada gyzyl-gara agaçlary ulanyp, TreeMap-da sortlamak barada has giňişleýin maglumat alyp bilersiňiz .

4. “Hashtable” “HashMap” -a meňzeýär , ýöne nulllaryň açar ýa-da baha hökmünde saklanmagyna rugsat bermeýär . Köp sapakly nukdaýnazardan seresaplylyk bilen sinhronlaşdyrylýar, bu bolsa öz gezeginde köp sapakly nukdaýnazardan howpsuzdygyny aňladýar. Emma bu ýerine ýetiriş köne we haýal, şonuň üçin indi has köp täze taslamada “Hashtable” -ni görmersiňiz .

8. ArrayList vs LinkedList. Haýsyny ulanmagy makul bilýär?

Bu sorag, belki-de, maglumat gurluşlarynda iň meşhurdyr we käbir ýalňyşlyklary öz içine alýar. Oňa jogap bermezden ozal bu maglumatlar gurluşlary barada has giňişleýin öwreneliň. “ArrayList” sanaw interfeýsini ýerine ýetirýär we zerur bolanda giňeldilen içerki massiwde işleýär. Içerki massiw doly doldurylanda we täze element goýulmaly bolanda (oldSize * 1.5) +1 ululygynda täze massiw döredilýär. Ondan soň köne massiwdäki ähli maglumatlar täze + täze elemente göçürilýär we köne maglumatlary zibil ýygnaýjy ýok eder . Goşmak usuly massiwiň soňky boş öýjügine element goşýar. .Agny, eýýäm 3 elementimiz bar bolsa, indiki elementini 4-nji öýjüge goşar. Esasy usullaryň ýerine ýetirilişine geçeliň:

• get (int index) - bir elementi indeks boýunça almak O (1) iň çaltdyr ;
• goş (Obýekt garşy) - täze element üçin içerki massiwde ýeterlik ýer bar bolsa, adaty goýmak bilen O (1) wagt sarp ediler , sebäbi goşma soňky öýjüge gönükdirilendir.

  Täze massiw döretmeli we mazmuny göçürmeli bolsa, wagtymyz O (n) massiwindäki elementleriň sanyna göni proporsional bolar ;

• aýyrmak (int indeks) - bir elementi aýyranymyzda, meselem, ortadan O (n / 2) wagt alarys, sebäbi elementleri onuň sag tarapyna bir öýjük yza çekmeli bolarys. Şoňa laýyklykda sanawyň başyndan pozulsa, O (n), soňundan - O (1);
• goş (int index, Object obj) - pozulmaga meňzeş ýagdaý: ortasyna goşulanda elementleri sag bir öýjükde öňe süýşürmeli bolarys, şonuň üçin wagt O (n / 2). Elbetde, başyndan - O (n), soňundan - O (1);
• set (int index, Object obj) - bu ýerde ýagdaý başga, sebäbi diňe islenýän elementi tapyp, galanlaryny göçürmän üstünde ýazmaly, şonuň üçin O (1).

ArrayList hakda has giňişleýin okaň . LinkedList birbada iki interfeýsi amala aşyrýar - Sanaw we nobat , şonuň üçin iki maglumat gurluşyna mahsus häsiýetler we usullar bar. Sanawdan indeks boýunça bir elemente, nobatdan - “kelläniň” we “guýrugyň” barlygyna girdi. Içerde, goşa baglanyşdyrylan sanawy görkezýän maglumat gurluşy hökmünde amala aşyrylýar. .Agny, “guýruk” we “kelle” -den başga her elementiň indiki we öňki elementine baglanyşygy bar.

• get (int index) - sanawyň ortasyndaky elementi gözläniňizde, islenýänini tapýança ähli elementleri gözläp başlaýar. Logika görä, gözleg O (n / 2) almaly , ýöne LinkedList-iň guýrugy hem bar, şonuň üçin gözleg iki tarapdan bir wagtda amala aşyrylýar. Şoňa görä wagt O (n / 4) -e çenli azalýar .

  Eger element sanawyň başyna ýa-da soňuna ýakyn bolsa, wagt O bolar (1) ;

• goş (Obýektiň garşylygy) - täze element goşulanda, “guýruk” elementiniň indiki elemente baglanyşygy bolar we täze element öňki elemente baglanyşyk alar we täze “guýruk” bolar. Şoňa görä wagt O (1) bolar ;
• aýyrmak (int indeks) - almak (int indeks) usulyna meňzeş logika . Sanawyň ortasyndan bir elementi aýyrmak üçin ilki bilen ony tapmaly. Bu ýene O (n / 4) , öçürmegiň özi hiç zat almaýar, sebäbi diňe goňşy obýektleriň görkezijisini üýtgedýär (biri-birine ýüzlenip başlaýarlar). Eger element başynda ýa-da ahyrynda bolsa, onda ýene - O (1) ;
• goşuň (int index, Object obj) we set (int index, Object obj) - usullaryň (int indeks) almak üçin birmeňzeş wagt çylşyrymlylygy bolar , sebäbi köplenç element gözlemek üçin sarp edilýär. Şonuň üçin sanawyň ortasy üçin - O (n / 4) , başda - O (1).

LinkedList bilen işlemek barada has giňişleýin maglumat bu makalada beýan edilýär . Bularyň hemmesine tablisada seredeliň: Mümkin, eýýäm düşünşiňiz ýaly, bu soraga biragyzdan jogap bermek mümkin däl. Galyberse-de, dürli ýagdaýlarda dürli tizlikde işleýärler. Şonuň üçin size şuňa meňzeş sorag berlende, bu sanawyň nämä gönükdiriljekdigini we haýsy amallaryň köplenç ýerine ýetiriljekdigini derrew soramaly. Mundan başlap, jogap beriň, ýöne munuň näme üçin beýle bolýandygyny düşündiriň. Deňeşdirişimizi jemläliň: ArrayList:

• iň ýygy operasiýa bir elementi gözlemek, bir elementiň üstünden ýazmak bolsa iň gowy saýlaw;
• amal iň başynda goýmak we aýyrmak bolsa iň erbet saýlaw, sebäbi sag tarapdaky elementleriň çalşyk amallary bolar.

LinkedList:

• frequygy-ýygydan işleýänimiz, başynda goýmak we aýyrmak bolsa iň gowy saýlaw;
• Iň köp ulanylýan operasiýa gözleýän bolsa, iň erbet saýlaw.

9. HashMap-da elementler nädip saklanýar?

“HashMap” kolleksiýasynda öýjüklere çelek hem diýilýän içerki massiw düwün [] tablisasy bar . Düwün öz içine alýar:

• açar - açara baglanyşyk,
• bahasy - bahasyna salgylanma,
• hash - hash gymmaty,
• indiki - indiki düwmä baglanyşyk .

Tablisa [] massiwiniň bir öýjüginde indiki düwün elementine baglanyşygy bolan düwün obýektine salgylanma bolup biler , beýlekisine baglanyşyk bolup biler we ş.m. ... Netijede, bu düwün elementleri a emele getirip biler ýeke-täk baglanyşyk sanawy , indiki baglanyşygy bolan elementler bilen. Bu ýagdaýda bir zynjyryň elementleriniň hash bahasy deňdir. Gysga bir gözlegden soň, elementleriň “HashMap” -da nädip saklanýandygyna seredeliň :

1. Açar null barlanýar . Eger null bolsa , açar tablisanyň [0] öýjüginde saklanar , sebäbi null üçin hash kody hemişe 0 bolýar.
2. Eger açar null däl bolsa , onda esasy obýektiň hashkody () usuly diýilýär , ol hash koduny yzyna gaýtaryp berýär. Bu hash kody, düwün obýektiniň saklanjak massiw öýjügini kesgitlemek üçin ulanylýar.
3. Ondan soň, bu hashkod hashkody hasaplaýan, ýöne tablisanyň [] massiwiniň ululygynda içerki hash () usulyna ýerleşdirildi .
4. Ondan soň, hash bahasyna baglylykda düwün tablisanyň [] massiwinde belli bir öýjüge ýerleşdirilýär .
5. Häzirki düwün elementini tygşytlamak üçin ulanylýan tablisa [] öýjügi boş däl, ýöne eýýäm käbir elementi bar bolsa, düwün elementleri soňky elemente ýetýänçä indiki baha boýunça gaýtalanýar. Nextagny, indiki meýdany boş .

   Bu gözlegiň dowamynda goralýan düwün obýektiniň açary gözlenýänleriň açarlary bilen deňeşdirilýär:

   • gabat gelýän tapylsa, gözleg gutarar we täze düwün oýnuň tapylan düwünini täzeden ýazar (diňe onuň bahasy meýdançasy ýazylar );
   • esasy gabat gelýänler tapylmasa, täze düwün bu sanawdaky iň soňky bolar we öňküsi bilen indiki baglanyşygy bolar .

Söhbetdeşlik wagtynda köplenç sorag ýüze çykýar: gapma-garşylyk näme ? Stol [] massiwiniň öýjügi bir elementi däl-de, iki ýa-da has köp zynjyry saklaýan ýagdaýyna çaknyşyk diýilýär . Bir tablisada [] öýjükde diňe bir element saklanýan adaty ýagdaýlarda , HashMap elementlerine girmek hemişelik O (1) wagt çylşyrymlylygyna eýe . Desiredöne islenýän elementli öýjük elementleriň zynjyryny ( çaknyşmagy ) öz içine alanda, O (n) bolýar , sebäbi bu ýagdaýda wagt tertiplenýän elementleriň sanyna göni proporsionaldyr.

10. iterator hakda düşündiriň

Aboveokardaky Kolleksiýa iýerarhiýasynyň kartalaşdyryş diagrammasynda , Toplama interfeýsi tutuş iýerarhiýanyň başlanan ýeri, ýöne iş ýüzünde beýle beýle däl. Collectionygyndy, Iterator <E> interfeýsini ýerine ýetirýän obýekti yzyna gaýtarýan iterator () usuly bilen interfeýsden miras alýar . Iterator interfeýsi şeýle:

public interface Iterator <E>{

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

indiki () - bu usula jaň edip, indiki elementi alyp bilersiňiz. hasNext () - indiki elementiň bardygyny ýa-da kolleksiýanyň ahyryna ýetendigini anyklamaga mümkinçilik berýär. Elementler bar bolsa, hasNext () hakykata gaýdyp geler . Adatça, hasNext () indiki () usuldan öň çagyrylýar , sebäbi indiki () kolleksiýanyň soňuna ýetende NoSuchElementException atar . aýyrmak () - Soňky jaň bilen indiki () -e alnan elementi aýyrýar . Iteratoryň maksady elementleriň üstünde gaýtalamak. Mysal üçin:

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

Aslynda, her bir aýlaw iterator ulanyp kapotyň aşagynda amala aşyrylýar. Bu hakda has giňişleýin maglumaty şu ýerden okap bilersiňiz . Sanaw iteratoryň öz wersiýasyny hödürleýär, ýöne has sowuk we has çylşyrymly - ListIterator . Bu interfeýs Iterator-y giňeldýär we goşmaça usullary bar:

• hasPrevious ýygyndyda öňki element bar bolsa, başgaça ýalan bolsa, hakykata gaýdyp geler;
• öňki elementi yzyna gaýtaryp, öňki elementine geçýär; ýok bolsa, NoSuchElementException zyňylýar;
• goşmak, indiki jaň bilen indiki () yzyna gaýtaryljak elementiň öňünden geçen obýekti goýar ;
• toplum häzirki elementi geçen obýekte salgylanma belleýär;
• nextIndex indiki elementiň görkezijisini gaýtaryp berýär. Şeýle zat ýok bolsa, sanawyň ululygy yzyna gaýtarylýar;
• previousIndex öňki elementiň indeksini görkezýär. Eger ýok bolsa, -1 belgisi yzyna gaýtarylýar.

Dogrusy, bu gün meniň üçin. Bu makalany okanyňyzdan soň, öz arzuw edýän arzuwyňyza has ýakynlaşarsyňyz diýip umyt edýärin.