Wiwitane dalan
Dina iki aku pengin ngomong babagan topik sing menarik kaya "
Java Collections Framework " utawa, kanthi prasaja, babagan koleksi. Umume karya kode kasebut ngolah data ing siji utawa liyane. Entuk dhaptar pangguna, entuk dhaptar alamat, lsp. Piye carane ngurutake, nindakake telusuran, mbandhingake. Mulane kawruh babagan koleksi dianggep minangka skill inti. Mulane aku arep ngomong babagan iki. Kajaba iku, salah sawijining pitakonan sing paling umum ing wawancara pangembang Jawa yaiku koleksi. Contone, "gambar hirarki koleksi." Compiler online bakal mbantu kita ing dalan. Contone, sampeyan bisa nggunakake " Tutorialspoint
Online Java Compiler " utawa
Repl.it. Path kanggo ngerteni struktur data apa wae diwiwiti kanthi variabel biasa (Variabel). Ing situs web Oracle, macem-macem topik dituduhake minangka "paths" utawa Trails. Dadi, dalan kanggo ngerti basa Jawa diarani "
Jejak: Sinau Basa Jawa: Daftar Isi ". Lan dhasar-dhasar basa (yaiku Dasar-dasar Basa) diwiwiti karo Variabel. Mulane, ayo nulis kode prasaja:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Iku apik ing kabeh, kajaba sing kita ngerti sing kode iki apik lan ayu mung kanggo siji variabel. Apa sing kudu ditindakake yen ana sawetara? Arrays diciptakake kanggo nyimpen data saka siji jinis. Ing Trail padha saka Oracle ana bagean kapisah darmabakti kanggo susunan. Bagean iki diarani: "
Arrays ". Nggarap array uga cukup prasaja:
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));
}
}
Arrays ngrampungake masalah nyimpen macem-macem nilai ing sak panggonan. Nanging nemtokke watesan: ukuran Uploaded punika pancet. Yen, kaya ing conto, kita ngomong yen ukuran = 2, banjur padha karo loro. Mekaten. Yen kita pengin array sing luwih gedhe, kita kudu nggawe conto anyar. Uga, nemokake unsur uga angel kanggo array. Ana cara
Arrays.binarySearch, nanging telusuran iki mung bisa digunakake ing larik sing diurutake (kanggo larik sing ora diurutake, asile ora ditemtokake utawa ora bisa ditebak). Tegese, telusuran bakal mewajibake kita ngurutake saben wektu. Mbusak uga mung mbusak nilai. Mulane, kita isih ora ngerti carane akeh data bener ing Uploaded, kita mung ngerti carane akeh sel ing Uploaded. Kanggo refresh kawruh babagan array:
Lan minangka akibat saka pangembangan basa Jawa, Java Collections Framework muncul ing JDK 1.2, sing bakal kita bahas saiki.
Koleksi
Miwiti biaya saka wiwitan. Kenapa Koleksi? Istilah kasebut asale saka perkara kaya "Teori Tipe" lan "Jinis Data Abstrak". Nanging yen sampeyan ora ndeleng prakara sing dhuwur, mula yen kita duwe sawetara perkara, kita bisa kasebut "koleksi barang". Sing ngumpulake barang. Umumé, tembung kumpul dhewe asalé saka Lat. koleksi "kumpul, ngumpulake." Tegese, koleksi yaiku kumpulan barang, wadhah kanggo sawetara unsur. Dadi kita duwe koleksi unsur. Apa sing bisa kita lakoni karo:
Nalika sampeyan bisa ndeleng, kita bisa uga pengin cukup logis. Kita uga ngerti manawa kita pengin nindakake sawetara koleksi:
Mulane, pangembang Jawa nulis antarmuka java.util.Collection kanggo njlèntrèhaké prilaku umum iki kanggo kabeh koleksi . Antarmuka Koleksi yaiku asale kabeh koleksi. Koleksi minangka ide, yaiku ide babagan carane kabeh koleksi kudu tumindak. Mulane, istilah "Koleksi" ditulis minangka antarmuka. Mesthi, antarmuka mbutuhake implementasine. Antarmuka
java.util.Collectionnduweni kelas abstrak
AbstractCollection, yaiku, sawetara "koleksi abstrak", sing nggambarake kerangka kanggo implementasi liyane (kaya sing ditulis ing JavaDoc ing ndhuwur kelas
java.util.AbstractCollection). Ngomong babagan koleksi, ayo bali lan elinga yen kita pengin ngulang. Iki tegese kita arep kanggo iterate liwat unsur siji. Iki minangka konsep sing penting banget. Mulane, antarmuka
Collectiondiwarisake saka
Iterable. Iki penting banget amarga ... pisanan, kabeh Iterable kudu bisa ngasilake Iterator adhedhasar isine. Lan kapindho, kabeh sing bisa digunakake Iterable ing puteran
for-each-loop. Lan iku karo bantuan saka iterator
AbstractCollectionsing cara kayata
contains,
toArray, dileksanakake
remove. Lan path kanggo mangerteni koleksi diwiwiti karo salah siji saka struktur data paling umum - dhaftar, i.e.
List.
Dhaptar
Dadi, dhaptar nduwe papan sing penting ing hirarki koleksi:
Minangka kita bisa ndeleng, dhaptar ngleksanakake antarmuka
java.util.List . Dhaptar nyatakake yen kita duwe koleksi unsur sing disusun ing sawetara urutan siji-sijine. Saben unsur duwe indeks (kaya ing array). Biasane, dhaptar ngidini sampeyan duwe unsur kanthi nilai sing padha. Kaya sing kasebut ing ndhuwur,
Listngerti babagan indeks unsur kasebut. Iki ngidini sampeyan entuk (
get) unsur kanthi indeks utawa nyetel nilai kanggo indeks tartamtu (
set). Cara koleksi
add,
addAll,
removengijini sampeyan kanggo nemtokake indeks saka kang nglakokaké mau. Kajaba iku, y
Listduwe versi iterator dhewe sing diarani
ListIterator. iterator iki ngerti bab indeks saka unsur, supaya bisa iterate ora mung maju, nanging uga mundur. Malah bisa digawe saka panggonan tartamtu ing koleksi. Ing antarane kabeh implementasine, ana loro sing paling umum digunakake:
ArrayListlan
LinkedList. Pisanan,
ArrayListiku dhaftar (
List) adhedhasar larik (
Array). Iki ngidini sampeyan entuk "Akses Acak"
menyang unsur. Akses acak yaiku kemampuan kanggo langsung njupuk unsur kanthi indeks, tinimbang ngulang kabeh unsur nganti kita nemokake unsur kanthi indeks sing dikarepake. Iku array minangka basis sing ngidini iki kanggo entuk. Ing nalisir,
LinkedListiku Linked List. Saben entri ing dhaptar sing disambung diwakili ing wangun
Entry, sing nyimpen data kasebut dhewe, uga minangka tautan menyang sabanjure (sabanjure) lan sadurunge (sadurunge)
Entry. Mangkono
LinkedListngleksanakake "Akses Sequential
" . Cetha yen kanggo nemokake unsur 5 kita kudu pindhah saka unsur pisanan menyang pungkasan, amarga kita ora duwe akses langsung menyang unsur kalima. Kita mung bisa ngakses saka unsur 4. Bedane konsep kasebut diwenehi ing ngisor iki:
Ing karya, sampeyan ngerti, ana uga beda. Contone, nambah unsur. Unsur kasebut
LinkedListmung disambungake kaya tautan ing ranté. Nanging
ArrayListnyimpen unsur ing array. Lan larik, kaya sing kita ngerti, ora bisa ngganti ukurane. Kepiye cara kerjane
ArrayList? Lan kerjane gampang banget. Nalika papan ing Uploaded entek, mundhak 1,5 kaping. Iki kode zoom:
int newCapacity = oldCapacity + (oldCapacity >> 1); Bedane liyane ing operasi yaiku ngimbangi unsur. Contone, nalika nambah utawa mbusak unsur ing tengah. Kanggo mbusak saka
LinkedListunsur, mung mbusak referensi kanggo unsur iki. Ing kasus ,
ArrayListkita dipeksa kanggo mindhah unsur saben wektu nggunakake
System.arraycopy. Mangkono, luwih akeh unsur, luwih akeh tumindak sing kudu ditindakake. Katrangan sing luwih rinci bisa ditemokake ing artikel iki:
Sawise mriksa ArrayList, siji ora bisa bantuan nanging ngelingi sawijining "pendahulu", kelas
java.util.Vector . Beda
Vectoramarga
ArrayListcara kanggo nggarap koleksi (nambah, mbusak, lsp) disinkronake. Yaiku, yen siji utas (
Thread) nambahake unsur, banjur utas liyane bakal ngenteni nganti utas pisanan rampung. Wiwit safety thread asring ora dibutuhake, dianjurake kanggo nggunakake kelas ing kasus kaya mengkono
ArrayList, minangka tegas nyatakake ing JavaDoc kanggo kelas
Vector. Kajaba iku,
Vectornambah ukuran ora 1,5 kaping,
ArrayListnanging 2 kaping. Yen ora, prilaku padha -
Vectorpanyimpenan saka unsur ing wangun Uploaded didhelikake lan nambah / mbusak unsur duwe jalaran padha ing
ArrayList. Nyatane,
Vectorkita ngelingi iki kanthi alesan. Yen kita katon ing Javadoc, kita bakal weruh ing "Direct Dikenal Subclasses" struktur kayata
java.util.Stack . Tumpukan minangka struktur sing menarik yaiku
last-in-first-outstruktur LIFO (last in, first out). Stack sing diterjemahake saka basa Inggris yaiku tumpukan (kaya tumpukan buku, contone). Tumpukan nindakake cara tambahan:
peek(katon, katon),
pop(push),
push(push). Cara kasebut
peekditerjemahake minangka katon (contone,
ngintip ing njero tas diterjemahake minangka "
deleng ing njero tas ", lan
ngintip liwat bolongan tombol diterjemahake minangka "
Ngintip liwat bolongan tombol "). Cara iki ngidini sampeyan ndeleng ing "ndhuwur" tumpukan, i.e. entuk unsur pungkasan tanpa njabut (i.e. tanpa njabut) saka tumpukan. Cara kasebut
pushnyurung (nambah) unsur anyar menyang tumpukan lan ngasilake, lan metode unsur
popnyurung (nyopot) lan ngasilake sing dibusak. Ing kabeh telung kasus (i.e. Ndeleng, pop lan push), kita mung bisa karo unsur pungkasan (yaiku "ndhuwur tumpukan"). Iki minangka fitur utama saka struktur tumpukan. Miturut cara, ana tugas sing menarik kanggo mangerteni tumpukan, sing diterangake ing buku "A Programmer's Career" (Cracking Coding Interview). Ana tugas sing menarik ing ngendi nggunakake struktur "tumpukan" (LIFO) sampeyan kudu ngetrapake "antrean". struktur (FIFO). Iku kudu katon kaya iki:
Analisis tugas iki bisa ditemokake ing kene: "
Ngleksanakake Antrian Nggunakake Tumpukan - ADT Antrian ("Ngimplementasikan Antrian Nggunakake Tumpukan" ing LeetCode) ". Dadi kanthi lancar pindhah menyang struktur data anyar - antrian.
antri
Antrian minangka struktur sing kita kenal saka urip. Antrian menyang toko, menyang dokter. Sapa sing teka luwih dhisik (Mbok Pisanan) bakal dadi sing pertama metu saka antrian (First Out). Ing Jawa, antrian diwakili dening antarmuka
java.util.Queue . Miturut Javadoc antrian, antrian nambahake cara ing ngisor iki:
Nalika sampeyan bisa ndeleng, ana cara pesenan (gagal kanggo nglakokaké iku fraught karo pangecualian) lan ana cara panyuwunan (ora bisa kanggo nglakokaké ora mimpin kanggo kasalahan). Sampeyan uga bisa njaluk unsur tanpa njabut (Nintip utawa unsur). Antarmuka antrian uga nduweni penerus sing migunani -
Deque . Iki sing diarani "antrian loro-lorone". Yaiku, antrian kasebut ngidini sampeyan nggunakake struktur iki saka wiwitan lan pungkasan. Dokumentasi nyatakake yen "Deques uga bisa digunakake minangka tumpukan LIFO (Last-In-First-Out). Antarmuka iki kudu digunakake ing preferensi kanggo kelas Stack warisan. tumpukan. Javadoc nuduhake metode apa sing diterangake antarmuka Deque:
Ayo ndeleng apa implementasine ana. Lan kita bakal weruh kasunyatan sing menarik - LinkedList wis mlebu kamp antrian) Yaiku, LinkedList ngetrapake loro
List, lan
Deque. Nanging ana uga "mung antrian", contone
PriorityQueue. Dheweke ora asring eling, nanging muspra. Kaping pisanan, sampeyan ora bisa nggunakake "obyek sing ora bisa dibandhingake" ing antrian iki, yaiku. salah siji Comparator kudu kasebut utawa kabeh obyek kudu iso dibandhingke. Kapindho, "implementasi iki nyedhiyakake wektu O(log(n)) kanggo metode enqueuing lan dequeuing". Kerumitan logaritma ana alesan. Dilaksanakake PriorityQueue adhedhasar tumpukan. Javadoc ujar: "Antrian prioritas diwakili minangka tumpukan biner sing seimbang." Panyimpenan dhewe kanggo iki minangka susunan biasa. Kang mundak akeh yen perlu. Nalika tumpukan cilik, mundhak 2 kali. Lan banjur kanthi 50%. Komentar saka kode: "Ukuran pindho yen cilik; liyane tuwuh 50%". Antrian prioritas lan Binary Heap minangka topik sing kapisah. Dadi kanggo informasi luwih lengkap:
Minangka implementasine,
java.util.Dequesampeyan bisa nggunakake kelas
java.util.ArrayDeque . Tegese, dhaptar bisa dileksanakake nggunakake dhaptar sing disambung lan array, lan antrian uga bisa dileksanakake nggunakake array utawa nggunakake dhaptar sing disambung. Antarmuka
Queuelan
Dequeduwe turunan sing makili "antrian pamblokiran":
BlockingQueuelan
BlockingDeque. Mangkene owah-owahan antarmuka dibandhingake karo antrian biasa:
Ayo katon ing sawetara conto pamblokiran antrian. Nanging padha menarik. Contone, BlockingQueue dileksanakake dening:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Nanging
BlockingDequedheweke nindakake kabeh saka Kerangka Koleksi standar
LinkedBlockingDeque. Saben antrian minangka topik review sing kapisah. Lan ing kerangka review iki, kita bakal nggambarake hirarki kelas ora mung karo
List, nanging uga karo
Queue:
Minangka kita bisa ndeleng saka diagram, antarmuka lan kelas saka Java Collections Framework banget intertwined. Ayo dadi nambah cabang liyane saka hirarki -
Set.
Set
Set- diterjemahake minangka "set." Beda karo antrian lan dhaptar
Seting abstraksi sing luwih gedhe babagan panyimpenan unsur.
Set- kaya tas saka obyek, ngendi iku ora dingerteni carane obyek dumunung lan ing urutan apa padha lay. Ing Jawa, set kasebut diwakili dening antarmuka
java.util.Set . Minangka dokumentasi ngandika,
Setiki minangka "koleksi sing ora ngemot unsur duplikat". Apike, antarmuka dhewe
Setora nambah cara anyar kanggo antarmuka
Collection, nanging mung njlentrehake syarat (babagan apa ora kudu ngemot duplikat). Kajaba iku, saka katrangan sadurunge, sampeyan ora bisa
Setnjupuk unsur kasebut. Iterator digunakake kanggo njupuk unsur.
Setwis sawetara antarmuka liyane sing digandhengake karo. Sing pertama yaiku
SortedSet. Minangka jeneng tabet,
SortedSetnuduhake yen pesawat kuwi wis diurutake, lan mulane unsur ngleksanakake antarmuka
Comparableutawa kasebut
Comparator. Kajaba iku,
SortedSetnawakake sawetara cara sing menarik:
Kajaba iku, ana metode
first(elemen paling cilik miturut nilai) lan
last(elemen paling gedhe miturut nilai). Ana
SortedSetahli waris -
NavigableSet. Tujuan antarmuka iki kanggo njlèntrèhaké cara pandhu arah sing dibutuhake kanggo ngenali unsur sing cocog kanthi luwih akurat. Sing menarik iku
NavigableSetnambah iterator biasanipun (sing dadi saka cilik kanggo paling gedhe) iterator kanggo urutan mbalikke -
descendingIterator. Kajaba iku,
NavigableSetiku ngijini sampeyan kanggo nggunakake cara
descendingSetkanggo njupuk tampilan saka dhewe (View), kang unsur ing urutan mbalikke. Iki diarani
Viewamarga liwat unsur asil sampeyan bisa ngganti unsur asli
Set. Sing, ing intine, iki minangka perwakilan saka data asli kanthi cara sing beda, lan dudu salinan. Apike,
NavigableSet, kaya
Queue, bisa nangani unsur
pollFirst(minimal) lan
pollLast(maksimal). Sing, iku nemu unsur iki lan mbusak saka pesawat. Apa jenis implementasine? Kaping pisanan, implementasine sing paling misuwur adhedhasar kode hash -
HashSet . Implementasi liyane sing padha kondhang adhedhasar wit abang-ireng -
TreeSet . Ayo ngrampungake diagram kita:
Ing koleksi, tetep kanggo ngurutake hirarki - para pertapa. Kang ing kawitan marketing stands aside -
java.util.Map.
Peta
Peta minangka struktur data ing ngendi data disimpen kanthi kunci. Contone, kunci bisa dadi ID utawa kode kutha. Lan kanthi tombol iki data bakal digoleki. Iku menarik yen kertu ditampilake kanthi kapisah. Miturut pangembang (ndeleng "
FAQ Desain API Koleksi Java "), pemetaan nilai kunci dudu koleksi. Lan peta bisa luwih cepet dianggep minangka koleksi kunci, koleksi nilai, koleksi pasangan kunci-nilai. Iki minangka kewan sing menarik. Cara apa kertu nyedhiyakake? Ayo katon ing antarmuka Java API
java.util.Map . Amarga Wiwit maps ora koleksi (padha ora oleh warisan saka Collections), padha ora ngemot a
contains. Lan iki logis. Peta kasusun saka kunci lan nilai. Endi sing kudu dipriksa metode kasebut
containslan kepiye supaya ora bingung? Mulane, antarmuka
Mapduwe rong versi beda:
containsKey(ngemot tombol) lan
containsValue(ngemot nilai). Nggunakake
keySetngidini sampeyan entuk set tombol (sing padha
Set). Lan nggunakake metode kasebut,
valueskita bisa entuk koleksi nilai ing peta. Tombol ing peta unik, sing ditekanake dening struktur data
Set. Nilai bisa diulang, sing ditekanake dening struktur data Koleksi. Kajaba iku, kanthi nggunakake metode kasebut,
entrySetkita bisa entuk set pasangan kunci-nilai. Sampeyan bisa maca liyane babagan implementasi kertu sing ana ing analisis sing paling rinci:
Aku uga kepengin weruh apa sing
HashMapmeh padha karo
HashSet,
TreeMaplan
TreeSet. Padha malah duwe antarmuka sing padha:
NavigableSetlan
NavigableMap,
SortedSetlan
SortedMap. Dadi peta pungkasan kita bakal katon kaya iki:
Kita bisa mungkasi kanthi kasunyatan sing menarik sing
Setdigunakake ing koleksi kasebut
Map, ing ngendi nilai tambah minangka kunci, lan regane padha ing endi wae. Iki menarik amarga
Mapdudu koleksi lan bali
Set, yaiku koleksi nanging nyatane ditindakake minangka
Map. Sithik surealis, nanging kaya ngono iku)
Kesimpulan
Kabar apik yaiku review iki rampung ing kene. Kabar ala yaiku iki minangka artikel review banget. Saben implementasine saben koleksi pantes artikel sing kapisah, lan uga kanggo saben algoritma sing didhelikake saka mripat kita. Nanging tujuan saka review iki kanggo ngelingi apa iku lan apa sambungan antarane antarmuka. Muga-muga sawise maca kanthi ati-ati, sampeyan bisa nggambar diagram koleksi saka memori.
Inggih, kaya biasane, sawetara pranala:
#Viacheslav
GO TO FULL VERSION