Wayoluň başlangyjy
Bu gün “ Java kolleksiýa çarçuwasy ” ýa-da ýönekeý sözler bilen kolleksiýalar hakda gyzykly mowzuk hakda gürleşmek isleýärin . Kodyň işiniň köpüsi maglumatlary bir görnüşde gaýtadan işlemekdir. Ulanyjylaryň sanawyny alyň, salgylaryň sanawyny alyň we ş.m. Näme-de bolsa olary tertipläň, gözleg geçiriň, deňeşdiriň. Şonuň üçin kolleksiýalary bilmek esasy ussatlyk hasaplanýar. Şonuň üçin bu hakda gürleşmek isleýärin. Mundan başga-da, Java dörediji söhbetdeşliklerinde iň köp ýaýran soraglaryň biri ýygyndydyr. Mysal üçin, "ýygyndylaryň iýerarhiýasyny çyzyň". Onlaýn düzüji ýolumyzda bize kömek eder. Mysal üçin, " Tutorialspoint
Online Java Compiler " ýa-da
Repl.it. ulanyp bilersiňiz. Islendik maglumat gurluşy bilen tanyşmagyň ýoly adaty üýtgeýjilerden (üýtgeýänler) başlaýar. Oracle web sahypasynda dürli mowzuklar "ýollar" ýa-da ýollar hökmünde görkezilýär. Şeýlelik bilen, Java bilen tanyşmagyň ýoluna “
Trail: Java dilini öwrenmek: Mazmuny ” diýilýär. Diliň esaslary (ýagny Dil esaslary) Üýtgeýjilerden başlaýar. Şonuň üçin ýönekeý kod ýazalyň:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Bu koduň diňe bir üýtgeýji üçin gowy we owadandygyna düşünýändigimizden başga hemme zat gowy. Olaryň birnäçesi bar bolsa näme etmeli? Bir görnüşdäki maglumatlary saklamak üçin massiwler oýlanyp tapyldy. “Oracle” -dan şol bir ýolda massiwlere bagyşlanan aýratyn bölüm bar.
Bu bölüm: " Toplumlar " diýilýär . Toplumlar bilen işlemek hem gaty ýönekeý:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
Toplumlar bir ýerde birnäçe bahany saklamak meselesini çözýär. Itöne çäklendirme girizýär: massiwiň ululygy hemişelik. Mysaldaky ýaly, ululygy = 2 diýsek, onda ikä deňdir. Bu hemmesi. Has uly massiw islesek, täze mysal döretmeli. Mundan başga-da, element tapmak hem bir massiw üçin kyn zat. Usul bar
Arrays.binarySearch, ýöne bu gözleg diňe tertipleşdirilen massiwde işleýär (tertipleşdirilmedik massiw üçin, netije kesgitlenmedik ýa-da öňünden aýdyp bolmaýar). .Agny, gözleg her gezek tertiplemäge mejbur eder. Öçürmek hem bahany arassalaýar. Şonuň üçin henizem massiwde näçe maglumatyň bardygyny bilemzok, diňe massiwde näçe öýjügiň bardygyny bilýäris. Toplumlar baradaky bilimleriňizi täzelemek üçin:
Java diliniň ösmeginiň netijesinde Java kolleksiýalary çarçuwasy JDK 1.2-de peýda boldy, bu gün gürleşeris.
Collectionygyndy
Bahasyny başyndan başlaň. Näme üçin kolleksiýalar? Bu adalganyň özi "Görnüş teoriýasy" we "Abstrakt maglumatlaryň görnüşleri" ýaly zatlardan gelip çykýar. Highöne haýsydyr bir möhüm meselä seretmeseňiz, birnäçe zadymyz bar bolsa, olara “zatlaryň ýygyndysy” diýip bileris. Haryt ýygnaýanlar. Umuman aýdanyňda, ýygnamak sözi Lat dilinden gelýär. kollektio "ýygnamak, ýygnamak." .Agny, ýygyndy bir zadyň ýygyndysy, käbir elementler üçin gap. Şeýlelik bilen bizde elementler ýygyndysy bar. Munuň bilen näme etmek isläp bileris:
Görşüňiz ýaly, gaty logiki zatlar isläp bileris. Şeýle hem, birnäçe ýygyndy bilen bir zat etmek isleýändigimize düşünýäris:
Şoňa laýyklykda Java döredijiler ähli kolleksiýalar üçin bu umumy häsiýeti suratlandyrmak üçin
java.util.Collection interfeýsini ýazdylar . Collectionygyndy interfeýsi, ähli kolleksiýalaryň dörän ýeri. Collectionygyndy ideýa, ähli kolleksiýalaryň özüni alyp barşynyň pikiri. Şonuň üçin "Toplama" adalgasy interfeýs hökmünde aňladylýar. Elbetde, interfeýs durmuşa geçirilmegine mätäç. Interfeýsde
java.util.Collectionabstrakt synp bar
AbstractCollection, ýagny beýleki amallar üçin skeleti aňladýan käbir "abstrakt ýygyndy" (synpyň ýokarsynda JavaDoc-da ýazylyşy ýaly
java.util.AbstractCollection). Kolleksiýalar barada aýdanymyzda, yza gaýdyp geleliň we olaryň üstünden gaýtalamak isleýändigimizi ýatdan çykaralyň. Bu, elementleriň üsti bilen ýeke-ýekeden gaýtalamak isleýändigimizi aňladýar. Bu örän möhüm düşünje. Şonuň üçin interfeýs
Collectionmiras galypdyr
Iterable. Bu gaty möhüm, sebäbi ... ilki bilen, Iterable-iň hemme zady, mazmuny boýunça Iterator-y yzyna gaýtarmagy başarmaly. Ikinjiden, Iterable-iň hemme zady aýlawda ulanyp bolýar
for-each-loop. We iteratoryň kömegi bilen ,
AbstractCollectionýaly usullar durmuşa geçirilýär . Kolleksiýalara düşünmegiň ýoly iň köp ýaýran maglumatlar gurluşlaryndan biri - sanawdan başlaýar. .
containstoArrayremoveList
Sanawlar
Şeýlelik bilen, sanawlar ýygyndylaryň iýerarhiýasynda möhüm orny eýeleýär:
Görşümiz ýaly, sanawlar
java.util.List interfeýsini durmuşa geçirýär . Sanawlar yzly-yzyna yzygiderli tertiplenen elementler ýygyndysynyň bardygyny görkezýär. Her elementiň görkezijisi bar (massiwdäki ýaly). Adatça, sanaw birmeňzeş bahaly elementlere eýe bolmaga mümkinçilik berýär. Aboveokarda aýdyşymyz ýaly,
Listelementiň görkezijisi hakda bilýär. Bu size bir elementi indeks boýunça almaga
getýa-da belli bir indeks () üçin baha bellemäge mümkinçilik berýär
set. Collectionygnamak usullary ,
addolary ýerine ýetirjek indeksiňizi kesgitlemäge mümkinçilik berýär. Mundan başga-da, y diýilýän iteratoryň öz wersiýasy bar . Bu iterator elementiň görkezijisi barada bilýär, şonuň üçin ol diňe öňe däl, yza gaýdyp hem biler. Hatda ýygyndydaky belli bir ýerdenem döredip bolýar. Thehli ýerine ýetirişleriň arasynda iň köp ulanylýan iki zat bar: we . Ilki bilen, ( ) massiwine esaslanýan sanaw ( ).
Bu elementlere "tötänleýin giriş" gazanmaga mümkinçilik berýär . Tötänleýin giriş, elementi islenýän indeks bilen tapýançak, ähli elementleri gaýtalamazdan, bir elementi derrew indeks boýunça almak ukybydyr. Munuň ýerine ýetirilmegine esas berýän massiwdir. Munuň tersine, Baglanyşyk sanawy. Baglanan sanawdaky her ýazgy , maglumatlary saklaýan görnüşde, şeýle hem indiki (indiki) we öňki (öňki) baglanyşyk görnüşinde görkezilýär . Şeýlelik bilen "Yzygiderli giriş
" amala aşyrylýar . 5-nji elementi tapmak üçin birinji elementden iň soňkusyna geçmelidigimiz düşnüklidir, sebäbi bäşinji elemente göni girip bilmeris. Oňa diňe 4-nji elementden girip bileris. Düşünjesindäki tapawut aşakda berilýär:
addAllremoveListListIteratorArrayListLinkedListArrayListListArrayLinkedListEntryEntryLinkedList
Işde, düşünşiňiz ýaly, tapawut hem bar. Mysal üçin, elementleri goşmak. Elementler
LinkedListdiňe zynjyrdaky baglanyşyklar ýaly birleşdirilýär. Emma
ArrayListelementleri bir hatarda saklaýar. Bilşimiz ýaly bir massiw, ululygyny üýtgedip bilmez. Onda nähili işleýär
ArrayList? Bu gaty ýönekeý işleýär. Toplumdaky boşluk gutaranda 1,5 esse ýokarlanýar. Ine ulaltmak kody:
int newCapacity = oldCapacity + (oldCapacity >> 1); Işleýişdäki başga bir tapawut, elementleriň islendik ofsetidir. Mysal üçin, ortasyna elementler goşulanda ýa-da aýrylanda. Bir elementden aýyrmak üçin
LinkedListbu elemente salgylanmalary aýyryň. Şeýle bolsa,
ArrayListelementleri her gezek ulanyp, üýtgetmäge mejbur bolýarys
System.arraycopy. Şeýlelik bilen, elementler näçe köp bolsa, şonça-da köp hereket edilmeli bolar. Has jikme-jik beýany şu makalalarda tapyp bilersiňiz:
“ArrayList” -i gözden geçirensoň, “öňki” java.util.Vektor synpyny ýatda saklap bolmaz . Theygyndy bilen işlemek (goşmak, pozmak we ş.m.) usullarynyň sinhronlaşdyrylmagy bilen
Vectortapawutlanýar .
ArrayList.Agny, bir sapak (
Thread) element goşsa, beýleki sapaklar birinji sapak işini gutarýança garaşarlar.
ArrayListSapagyň howpsuzlygy köplenç talap edilmeýänligi sebäpli, synp üçin JavaDoc-da aç-açan aýdylyşy ýaly synpy ulanmak maslahat berilýär
Vector. Mundan başga-da,
Vectorululygyny 1,5 esse däl
ArrayList-de, 2 esse ýokarlandyrýar. Otherwiseogsam, özüňi alyp barşyň birmeňzeş -
Vectorelementleriň massiw görnüşinde saklanmagy gizlenýär we elementleri goşmak / aýyrmak öňküsi ýaly netijelere eýe
ArrayList. Aslynda
Vectormuny bir sebäbe görä ýada saldyk.
Javadoc-a göz aýlasak, "Göni belli kiçi klasslarda" java.util.Stack ýaly gurluşy göreris . Ackygyndy LIFO
last-in-first-out(iň soňkusy, ilki bilen) gurluşy bolan gyzykly gurluşdyr. Iňlis dilinden terjime edilen stack (mysal üçin kitaplar ýaly). Ackygyndy goşmaça usullary amala aşyrýar:
peek(seret, seret),
pop(iteklemek),
push(iteklemek). Usul
peekdaş görnüşi hökmünde terjime edilýär (mysal üçin,
sumkanyň içindäki peýkam “
sumkanyň içine seret ”,
açar çukuryna göz aýlamak “ açar çukuryna göz aýlamak ” hökmünde terjime edilýär ). Bu usul, stakanyň “ýokarsyna” seretmäge mümkinçilik berýär. iň soňky elementi stakadan aýyrmazdan (ýagny aýyrmazdan) alyň. Usul
pushtäze elementi stakanyň üstüne itýär (goşýar) we yzyna gaýtarýar, element usuly bolsa
popitekleýär (aýyrýar) we aýyrylan zady yzyna berýär. Üç hadysanyň hemmesinde (meselem, göz aýlamak, açmak we basmak) diňe soňky element bilen işleýäris (meselem, “stakanyň ýokarsy”). Bu stakanyň gurluşynyň esasy aýratynlygy. Theeri gelende aýtsak, “Programmistiň karýerasy” (Cracking Coding Interview) kitabynda beýan edilen staklara düşünmek üçin gyzykly bir mesele bar. “Stack” gurluşyny (LIFO) ulanmak bilen “nobaty” ýerine ýetirmek zerur bolan gyzykly bir mesele bar. Gurluşy (FIFO). Bu şeýle bolmaly:
Bu meseläniň derňewini şu ýerden tapyp bilersiňiz: "
Staklary ulanyp nobaty ýerine ýetiriň - nobat ADT (" LeetCode-da staklary ulanyp nobaty ýerine ýetiriň ") . Şeýlelik bilen biz täze maglumat gurluşyna - nobata geçýäris.
Nobat
Bir nobat, durmuşdan bize tanyş gurluşdyr. Dükanlara, lukmanlara nobatlar. Kim birinji gelen bolsa (Ilkinji giren) nobatdan ilkinji bolup çykar (Ilki bilen).
Java-da nobat java.util.Queue interfeýsi bilen görkezilýär . Nobatyň Javadoc-a görä, nobat aşakdaky usullary goşýar:
Görşüňiz ýaly sargyt usullary bar (olary ýerine ýetirmezlik kadadan çykma bilen baglanyşykly) we haýyş usullary bar (olary ýerine ýetirip bilmezlik ýalňyşlyklara sebäp bolmaýar). Şeýle hem elementi aýyrmazdan almak mümkindir (syn ýa-da element). Nobat interfeýsinde hem peýdaly mirasdüşer -
Deque bar . Bu "iki taraplaýyn nobat" diýilýär. Suchagny, şeýle nobat bu gurluşy başyndanam, ahyryndanam ulanmaga mümkinçilik berýär. Resminamalarda "Deques LIFO (Last-In-First-Out) staklary hökmünde hem ulanylyp bilner. Bu interfeýs miras Stack synpyndan ileri tutulmalydyr" diýilýär, ýagny Deque ýerine ýetirişlerini ýerine ulanmak maslahat berilýär. Stack. Javadoc, Deque interfeýsiniň haýsy usullary suratlandyrýandygyny görkezýär:
Haýsy ýerine ýetirişleriň bardygyny göreliň. We gyzykly bir hakykaty göreris - LinkedList nobat lagerine girdi) Linkagny, LinkedList ikisini hem ýerine ýetirýär
Listwe
Deque. Emma, meselem, “diňe nobatlar” bar
PriorityQueue. Ony köplenç ýada salmaýarlar, ýöne biderek. Ilki bilen, bu nobatda "deňeşdirip bolmaýan zatlary" ulanyp bilmersiňiz, ýagny ýa-da deňeşdiriji görkezilmeli ýa-da ähli obýektler deňeşdirilmeli. Ikinjiden, "bu ýerine ýetiriş, gözlemek we gözlemek usullary üçin O (log (n)) wagt berýär". Logarifmiki çylşyrymlylyk bir sebäp bilen bar. Üýşmek esasynda ýerine ýetirilen PriorityQueue. Javadoc: "Deňagramly ikilik üýşmesi hökmünde ileri tutulýan nobat" diýilýär. Munuň üçin ammar yzygiderli bir massiwdir. Zerur bolanda ösýär. Toprak kiçi bolanda 2 esse köpelýär. Soň bolsa 50% ýokarlanýar. Koddan düşündiriş: "Kiçijik bolsa iki esse ululyk, başga bolsa 50% ösýär". Üstünlik nobaty we Binary Heap aýratyn mowzuk. Has giňişleýin maglumat üçin:
Durmuşa geçirmek
java.util.ArrayDequejava.util.Deque synpy bolup biler . .Agny, sanawlar baglanyşyk sanawy we bir massiw arkaly amala aşyrylyp bilner, nobatlar hem bir massiw ýa-da baglanyşyk sanawy ulanyp amala aşyrylyp bilner. Interfeýslerde "blokirleme nobatyny" görkezýän nesiller bar : we . Ine, yzygiderli nobatlar bilen deňeşdirilende interfeýsiň üýtgemegi:
QueueDequeBlockingQueueBlockingDeque
Geliň, nobatlary petiklemegiň käbir mysallaryna seredeliň. Emma olar gyzykly. Mysal üçin, “BlockingQueue” aşakdakylar tarapyndan amala aşyrylýar:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Theyöne
BlockingDequeolar adaty ýygyndy çarçuwalaryndan hemme zady durmuşa geçirýärler
LinkedBlockingDeque. Her nobat aýratyn gözden geçirilişiň mowzugy. Bu synyň çäginde synp iýerarhiýasyny diňe bir däl
List, eýsem
Queue:
Diagrammadan görnüşi ýaly, Java kolleksiýa çarçuwasynyň interfeýsleri we synplary biri-biri bilen baglanyşyklydyr. Ierarhiýanyň başga bir şahasyny goşalyň -
Set.
Set
Set- “set” hökmünde terjime edildi.
SetElementleriň saklanyşyndan has uly abstraksiýasyndaky nobatdan we sanawdan tapawutlanýar.
Set- obýektleriň sumkasy ýaly, obýektleriň nirede ýerleşýändigi we haýsy tertipde ýerleşýändigi belli däl.
Java-da şeýle toplum java.util.Set interfeýsi bilen görkezilýär . Resminamalaryň aýdyşy ýaly,
Setbu "dublikat elementleri öz içine almaýan ýygyndy". Gyzykly tarapy, interfeýsiň özi
Setinterfeýsde täze usullary goşmaýar
Collection, diňe talaplary aýdyňlaşdyrýar (dublikatlar bolmaly däl zatlar hakda). Mundan başga-da, öňki düşündirişden diňe
Setbir element alyp bolmajakdygy görkezilýär. Iterator elementleri almak üçin ulanylýar.
Setbilen baglanyşykly ýene birnäçe interfeýsi bar. Birinjisi
SortedSet. Adyndan görnüşi ýaly,
SortedSetşeýle toplumyň tertiplenendigini we şonuň üçin elementleriň interfeýsi durmuşa geçirýändigini
Comparableýa-da kesgitlenendigini görkezýär
Comparator. Mundan başga-da,
SortedSetbirnäçe gyzykly usullary hödürleýär:
firstMundan başga-da, usullar (gymmaty boýunça iň kiçi element) we (gymmaty boýunça iň uly element) bar
last. Mirasdar
SortedSetbar -
NavigableSet. Bu interfeýsiň maksady, degişli elementleri has takyk kesgitlemek üçin zerur nawigasiýa usullaryny beýan etmekdir. Gyzykly zat,
NavigableSettersine sargyt üçin adaty iteratoryň (kiçisinden ulusyna gidýär) -
descendingIterator. Mundan başga-da, elementleriň ters tertipde ýerleşýän görnüşini (View) almak üçin
NavigableSetusuly ulanmaga mümkinçilik berýär .
descendingSetBu diýilýär
View, sebäbi emele gelen elementiň üsti bilen asyl elementini üýtgedip bilersiňiz
Set. .Agny, aslynda, asyl nusganyň göçürmesi däl-de, başga bir görnüşde görkezilmegi. Gyzykly
NavigableSettarapy, (minimal) we (maksimal) elementleri
Queuedolandyryp bilýär . .Agny, bu elementi alýar we toplumdan aýyrýar. Ol ýerde nähili durmuşa geçirişler bar?
Ilki bilen, iň meşhur ýerine ýetiriş hash kody - HashSet esaslanýar . Beýleki bir meşhur durmuşa geçiriş, gyzyl-gara agaç -
TreeSet . Diagrammamyzy tamamlalyň:
pollFirstpollLast
Theygyndylaryň içinde iýerarhiýany - germitleri kesgitlemek galýar. Bir seretse bir gapdala dur -
java.util.Map.
Kartalar
Kartalar maglumatlaryň açary bilen saklanýan maglumat gurluşydyr. Mysal üçin, açar şahsyýet ýa-da şäher kody bolup biler. Hut şu açar bilen maglumatlar gözlener. Kartlaryň aýratyn görkezilmegi gyzykly. Işläp düzüjileriň pikiriçe ("
Java Collections API Design FAQ " serediň) açar bahaly kartalaşdyrmak ýygyndy däl. Kartalary has çalt açarlaryň ýygyndysy, gymmatlyklar ýygyndysy, açar gymmaty jübütleriniň ýygyndysy diýip pikir edip bolar. Bu şeýle gyzykly haýwan. Kartlar haýsy usullary üpjün edýär?
Java API interfeýsine java.util.Map seredeliň . Sebäbi Kartalar ýygyndy däldigi sebäpli (Kolleksiýalardan miras almaýarlar), olarda ýok
contains. Bu mantykly. Karta düwmelerden we gymmatlyklardan durýar. Usulyň haýsysyny barlamaly
containswe nädip bulaşdyrmaly däl? Şonuň üçin interfeýsiň
Mapiki dürli wersiýasy bar:
containsKey(açary öz içine alýar) we
containsValue(bahasy bar). Ony ulanmak
keySetsize düwmeler toplumyny (şol bir
Set) almaga mümkinçilik berýär. Usuly ulanyp,
valueskartada gymmatlyklar ýygyndysyny alyp bileris. Kartadaky açarlar maglumatlaryň gurluşy bilen nygtalýan özboluşlydyr
Set. Collectionygyndy maglumat gurluşy bilen nygtalýan gymmatlyklar gaýtalanyp bilner. Mundan başga-da, usuly ulanyp,
entrySetesasy baha jübütleriniň toplumyny alyp bileris. Iň jikme-jik derňewlerde haýsy kartoçkanyň ýerine ýetirilişi barada has köp maglumat alyp bilersiňiz:
HashMapŞeýle hem, nämä meňzeýändigini
HashSetwe
TreeMapnämäni görmek isleýärin
TreeSet. Olaryň hatda meňzeş interfeýsleri bar :
NavigableSetwe . Şeýlelik bilen soňky kartamyz şeýle bolar:
NavigableMapSortedSetSortedMap
Collectionygyndynyň
Setiçerde ulanýan
Map, goşulan bahalar açar bolan we bahasy hemme ýerde birmeňzeş bolan gyzykly hakykat bilen gutaryp bileris. Bu gyzykly, sebäbi
Mapkolleksiýa däl-de
Set, aslynda ýerine ýetirilişi ýaly ýygyndy we girdeji däl
Map. Biraz sýurreal, ýöne şeýle boldy)
Netije
Gowy habar, bu syn şu ýerde tamamlanýar. Erbet habar, bu gaty gözden geçiriş makalasy. Theygyndylaryň hersiniň ýerine ýetirilmegi aýratyn makala, şeýle hem gözümizden gizlenen her algoritm üçin mynasyp. Emma bu synyň maksady, olaryň nämedigini we interfeýsleriň arasyndaky baglanyşyklary ýada salmakdyr. Pikirlenip okanyňyzdan soň ýygyndylaryň diagrammasyny ýatdan çyzyp bilersiňiz diýip umyt edýärin.
Adat bolşy ýaly, käbir baglanyşyklar:
# Wiaçeslaw
GO TO FULL VERSION