Yo'lning boshlanishi
Bugun men " Java Collections Framework " kabi qiziqarli mavzu yoki oddiy qilib aytganda, to'plamlar haqida gaplashmoqchiman . Kod ishlarining aksariyati ma'lumotlarni u yoki bu shaklda qayta ishlashdan iborat. Foydalanuvchilar ro'yxatini oling, manzillar ro'yxatini oling va hokazo. Qandaydir tarzda ularni saralash, qidiruvni amalga oshirish, solishtirish. Shuning uchun kollektsiyalarni bilish asosiy mahorat hisoblanadi. Shuning uchun men bu haqda gapirmoqchiman. Bundan tashqari, Java dasturchilari intervyularida eng ko'p uchraydigan savollardan biri bu to'plamlar. Masalan, "to'plamlar ierarxiyasini chizish". Onlayn kompilyator bizga yo'lda yordam beradi. Masalan, siz " Tutorialspoint
Online Java Compiler " yoki
Repl.it dan foydalanishingiz mumkin. Har qanday ma'lumotlar tuzilmalari bilan tanishish yo'li oddiy o'zgaruvchilardan (O'zgaruvchilar) boshlanadi. Oracle veb-saytida turli mavzular "yo'llar" yoki Trails sifatida taqdim etiladi. Shunday qilib, Java bilan tanishish yo'li "
Trail: Java tilini o'rganish: Mundarija " deb nomlanadi. Va til asoslari (ya'ni, Til asoslari) o'zgaruvchilar bilan boshlanadi. Shuning uchun oddiy kod yozamiz:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Bu hamma narsada yaxshi, faqat bitta o'zgaruvchi uchun bu kod yaxshi va chiroyli ekanligini tushunamiz. Agar ularning bir nechtasi bo'lsa, nima qilish kerak? Massivlar bir turdagi ma'lumotlarni saqlash uchun ixtiro qilingan. Oracle-dan xuddi shu Trail-da massivlarga bag'ishlangan alohida bo'lim mavjud.
Ushbu bo'lim " Masivlar " deb ataladi . Massivlar bilan ishlash ham juda oddiy:
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));
}
}
Massivlar bir nechta qiymatlarni bir joyda saqlash muammosini hal qiladi. Ammo bu cheklovni qo'yadi: massiv hajmi doimiy. Agar misoldagidek o'lcham = 2 deb aytgan bo'lsak, u ikkiga teng bo'ladi. Va tamom. Agar biz kattaroq massivni xohlasak, biz yangi misol yaratishimiz kerak. Bundan tashqari, elementni topish massiv uchun ham qiyin ishdir. Usul mavjud
Arrays.binarySearch, lekin bu qidiruv faqat tartiblangan massivda ishlaydi (tartiblanmagan massiv uchun natija aniqlanmagan yoki shunchaki oldindan aytib bo'lmaydi). Ya'ni, qidiruv bizni har safar saralashga majbur qiladi. O'chirish ham faqat qiymatni o'chiradi. Shuning uchun, biz hali ham massivda qancha ma'lumot borligini bilmaymiz, faqat massivda qancha hujayra borligini bilamiz. Massivlar haqidagi bilimlaringizni yangilash uchun:
Va Java tilining rivojlanishi natijasida Java Collections Framework JDK 1.2 da paydo bo'ldi, biz bugun gaplashamiz.
To'plam
Eng boshidan xarajatlarni boshlang. Nima uchun kolleksiyalar? Bu atamaning o'zi "Tip nazariyasi" va "mavhum ma'lumotlar turlari" kabi narsalardan kelib chiqqan. Ammo agar siz biron bir yuqori mavzuga qaramasangiz, unda bizda bir nechta narsalar mavjud bo'lsa, biz ularni "narsalar to'plami" deb atashimiz mumkin. Elementlarni yig'adiganlar. Umuman olganda, yig'ish so'zining o'zi lotin tilidan olingan. kollektsiya "yig'ish, yig'ish". Ya'ni, kollektsiya - bu biror narsaning to'plami, ba'zi elementlar uchun konteyner. Shunday qilib, bizda elementlar to'plami mavjud. Biz u bilan nima qilishni xohlashimiz mumkin:
Ko'rib turganingizdek, biz juda mantiqiy narsalarni xohlashimiz mumkin. Bundan tashqari, biz bir nechta to'plamlar bilan biror narsa qilishni xohlashimiz mumkinligini tushunamiz:
Shunga ko'ra, Java dasturchilari java.util.Collection interfeysini barcha to'plamlar uchun ushbu umumiy xatti-harakatni tasvirlash uchun yozdilar . To'plam interfeysi barcha to'plamlar paydo bo'ladigan joy. To'plam - bu g'oya, bu barcha to'plamlar qanday harakat qilish kerakligi haqidagi g'oya. Shuning uchun "To'plam" atamasi interfeys sifatida ifodalanadi. Tabiiyki, interfeys ilovalarni talab qiladi. Interfeys
java.util.Collectionmavhum sinfga ega
AbstractCollection, ya'ni ba'zi bir "mavhum to'plam" ga ega bo'lib, u boshqa ilovalar uchun skeletni ifodalaydi (JavaDoc da sinf ustida yozilganidek
java.util.AbstractCollection). To'plamlar haqida gapirganda, keling, orqaga qaytaylik va biz ularni takrorlashni xohlaymiz. Bu shuni anglatadiki, biz elementlarni birma-bir takrorlashni xohlaymiz. Bu juda muhim tushuncha. Shuning uchun interfeys
Collectiondan meros qilib olingan
Iterable. Bu juda muhim, chunki ... birinchidan, Iterable bo'lishi mumkin bo'lgan hamma narsa uning tarkibiga ko'ra Iteratorni qaytarishi kerak. Ikkinchidan, Iterable-ning looplarda ishlatilishi mumkin bo'lgan hamma narsa
for-each-loop. Va aynan iterator yordamida , ,
AbstractCollectionkabi usullar amalga oshiriladi . Va to'plamlarni tushunish yo'li eng keng tarqalgan ma'lumotlar tuzilmalaridan biri bilan boshlanadi - ro'yxat, ya'ni. .
containstoArrayremoveList
Ro'yxatlar
Shunday qilib, ro'yxatlar to'plamlar ierarxiyasida muhim o'rin egallaydi:
Ko'rib turganimizdek, ro'yxatlar
java.util.List interfeysini amalga oshiradi . Ro'yxatlar bizda birin-ketin ketma-ket joylashtirilgan elementlar to'plamiga ega ekanligini bildiradi. Har bir element indeksga ega (massivdagi kabi). Odatda, ro'yxat bir xil qiymatga ega bo'lgan elementlarga ega bo'lishga imkon beradi. Yuqorida aytganimizdek,
Listu element indeksi haqida biladi.
getBu sizga ( ) elementni indeks bo'yicha olish yoki ma'lum bir indeks (
set) uchun qiymat o'rnatish imkonini beradi. Yig'ish usullari
add,
addAll,
removeularni bajarish uchun indeksni belgilash imkonini beradi. Bundan tashqari, y-da
Listiteratorning o'z versiyasi mavjud
ListIterator. Ushbu iterator element indeksi haqida biladi, shuning uchun u nafaqat oldinga, balki orqaga ham takrorlashi mumkin. U hatto to'plamdagi ma'lum bir joydan ham yaratilishi mumkin. Barcha ilovalar orasida eng ko'p ishlatiladigan ikkitasi mavjud:
ArrayListva
LinkedList. Birinchidan, bu ( ) massivga asoslangan
ArrayListro'yxat ( ).
Bu elementlarga "Tasodifiy kirish" ga erishish imkonini beradi . Tasodifiy kirish - kerakli indeksga ega elementni topmagunimizcha, barcha elementlarni takrorlash o'rniga, elementni darhol indeks bo'yicha olish qobiliyati. Bunga erishishga imkon beruvchi asos sifatida massivdir. Aksincha, bu bog'langan ro'yxat. Bog'langan ro'yxatdagi har bir yozuv ma'lumotlarning o'zini saqlaydigan shaklda , shuningdek, keyingi (keyingi) va oldingi (oldingi) ga havola bilan ifodalanadi . Shunday qilib, "Sequential Access
" ni amalga oshiradi . 5-elementni topish uchun birinchi elementdan oxirgi elementga o'tishimiz kerakligi aniq, chunki bizda beshinchi elementga to'g'ridan-to'g'ri kirish imkoni yo'q. Biz unga faqat 4-elementdan kira olamiz. Ularning kontseptsiyasidagi farq quyida keltirilgan:
ListArrayLinkedListEntryEntryLinkedList
Ishda, siz tushunganingizdek, farq ham bor. Masalan, elementlarni qo'shish. Elementlar
LinkedListoddiygina zanjirdagi rishtalar kabi bog'langan. Lekin
ArrayListu elementlarni massivda saqlaydi. Va massiv, biz bilganimizdek, o'z hajmini o'zgartira olmaydi. Keyin qanday ishlaydi
ArrayList? Va bu juda oddiy ishlaydi. Massivdagi bo'sh joy tugagach, u 1,5 barobar ortadi. Mana kattalashtirish kodi:
int newCapacity = oldCapacity + (oldCapacity >> 1); Ishlashdagi yana bir farq elementlarning har qanday ofsetidir. Masalan, o'rtaga elementlarni qo'shish yoki olib tashlashda. Elementdan olib tashlash uchun
LinkedListushbu elementga havolalarni olib tashlash kifoya. dan
ArrayListfoydalanib har safar elementlarni siljitishga majbur bo'lamiz
System.arraycopy. Shunday qilib, qancha elementlar bo'lsa, shuncha ko'p harakatlarni bajarish kerak bo'ladi. Batafsilroq tavsifni ushbu maqolalarda topishingiz mumkin:
ArrayList-ni o'rganib chiqqandan so'ng, uning "oldingi" java.util.Vector sinfini eslay olmaysiz . U to'plam bilan ishlash usullari (qo'shish, o'chirish va hokazo) sinxronlashtirilganligi
Vectorbilan farq qiladi.
ArrayListYa'ni, agar bitta ip (
Thread) elementlarni qo'shsa, u holda boshqa iplar birinchi ip o'z ishini tugatguncha kutadi.
ArrayListMavzu xavfsizligi ko'pincha talab qilinmaganligi sababli, sinf uchun JavaDoc da aniq ko'rsatilgandek, bunday hollarda sinfdan foydalanish tavsiya etiladi
Vector. Bundan tashqari,
Vectoru o'z hajmini 1,5 marta emas,
ArrayListbalki 2 barobar oshiradi. Aks holda, xatti-harakatlar bir xil -
Vectorelementlarni massiv ko'rinishida saqlash yashirin va elementlarni qo'shish/o'chirish dagi kabi oqibatlarga olib keladi
ArrayList. Aslida,
Vectorbiz buni bir sababga ko'ra esladik.
Agar biz Javadoc-ga qarasak, "To'g'ridan-to'g'ri ma'lum bo'lgan pastki sinflar" da java.util.Stack kabi tuzilmani ko'ramiz . Stack - bu LIFO
last-in-first-out(oxirgi kiruvchi, birinchi chiqadi) strukturasi bo'lgan qiziqarli tuzilma. Ingliz tilidan tarjima qilingan stek - bu stek (masalan, kitoblar to'plami kabi). Stack qo'shimcha usullarni amalga oshiradi:
peek(qarash, qarash),
pop(surish),
push(surish). Usul
peekko'rinish deb tarjima qilinadi (masalan,
sumkaning ichiga qarash " sumka ichiga qarash " deb tarjima qilinadi va
kalit teshigidan ko'rish " kalit teshigidan ko'rish " deb tarjima qilinadi ). Ushbu usul sizga stackning "tepagi" ga qarashga imkon beradi, ya'ni. oxirgi elementni stekdan olib tashlamasdan (ya'ni olib tashlamasdan) oling. Usul
pushyangi elementni stekga suradi (qo'shadi) va uni qaytaradi, element usuli esa
popo'chirilgan elementni itaradi (o'chiradi) va qaytaradi. Barcha uchta holatda (ya'ni, ko'zdan kechirish, pop va surish) biz faqat oxirgi element bilan ishlaymiz (ya'ni, "stackning yuqori qismi"). Bu stek tuzilishining asosiy xususiyati. Aytgancha, “Dasturchining kasbi” (Cracking Coding Interview) kitobida tasvirlangan steklarni tushunish uchun qiziqarli vazifa bor, “stek” strukturasidan (LIFO) foydalanib, “navbat”ni amalga oshirish kerak bo'lgan qiziqarli vazifa bor. ” tuzilmasi (FIFO). Bu shunday ko'rinishi kerak:
Ushbu topshiriqning tahlilini bu yerda topishingiz mumkin: "
Stacks yordamida navbatni amalga oshirish - The Queue ADT ("LeetCode'da "Stacks yordamida navbatni amalga oshirish") ". Shunday qilib, biz muammosiz yangi ma'lumotlar tuzilmasi - navbatga o'tamiz.
Navbat
Navbat - bu bizga hayotdan tanish bo'lgan tuzilma. Do‘konlarga, shifokorlarga navbatlar. Kim birinchi bo'lib kelgan bo'lsa (First In) navbatdan birinchi chiqadi (First Out). Java'da navbat
java.util.Queue interfeysi bilan ifodalanadi . Navbatning Javadoc-ga ko'ra, navbat quyidagi usullarni qo'shadi:
Ko'rib turganingizdek, buyurtma usullari mavjud (ularni bajarmaslik istisnolar bilan to'la) va so'rov usullari mavjud (ularni bajara olmaslik xatolarga olib kelmaydi). Elementni olib tashlamasdan ham olish mumkin (peek yoki element). Navbat interfeysi ham foydali vorisi bor -
Deque . Bu "ikki tomonlama navbat" deb ataladi. Ya'ni, bunday navbat bu tuzilmani boshidan ham, oxiridan ham ishlatishga imkon beradi. Hujjatlarda aytilishicha, "Deques-dan LIFO (Last-In-First-Out) steklari sifatida ham foydalanish mumkin. Bu interfeys eski Stack sinfiga ustunlik bilan qo'llanilishi kerak.", ya'ni Deque ilovalari o'rniga foydalanish tavsiya etiladi. Stak. Javadoc Deque interfeysi qanday usullarni tavsiflashini ko'rsatadi:
Keling, qanday ilovalar mavjudligini ko'rib chiqaylik. Va biz qiziqarli faktni ko'ramiz - LinkedList navbat lageriga kirdi) Ya'ni, LinkedList ikkalasini ham
List, ni ham amalga oshiradi
Deque. Ammo "faqat navbatlar" ham bor, masalan
PriorityQueue. U tez-tez eslanmaydi, lekin behuda. Birinchidan, siz ushbu navbatda "taqqoslanmaydigan ob'ektlar" dan foydalana olmaysiz, ya'ni. yoki Comparator ko'rsatilishi kerak yoki barcha ob'ektlar solishtirilishi kerak. Ikkinchidan, "bu dastur navbatga qo'yish va o'chirish usullari uchun O(log(n)) vaqtini beradi". Logarifmik murakkablikning sababi bor. Uyumga asoslangan PriorityQueue amalga oshirildi. Javadoc shunday deydi: "Ustuvor navbat muvozanatli ikkilik to'p sifatida taqdim etilgan". Buning uchun saqlashning o'zi oddiy massivdir. Bu kerak bo'lganda o'sadi. Uyum kichik bo'lsa, u 2 barobar ortadi. Va keyin 50% ga. Koddan sharh: "Kichik bo'lsa, ikki baravar katta; aks holda 50% ga o'sadi". Prioritet navbat va Binary Heap alohida mavzu. Shunday qilib, qo'shimcha ma'lumot uchun:
Amalga oshirish sifatida
java.util.ArrayDequejava.util.Deque sinfidan foydalanishingiz mumkin . Ya'ni, ro'yxatlar bog'langan ro'yxat va massiv yordamida, navbatlar esa massiv yoki bog'langan ro'yxat yordamida ham amalga oshirilishi mumkin. va interfeyslarida "bloklash navbatini" ifodalovchi avlodlar mavjud: va . Oddiy navbatlar bilan solishtirganda interfeys o'zgarishi:
QueueDequeBlockingQueueBlockingDeque
Keling, navbatlarni blokirovka qilishning ba'zi misollarini ko'rib chiqaylik. Lekin ular qiziq. Misol uchun, BlockingQueue tomonidan amalga oshiriladi:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue ,
DelayQueue ,
LinkedBlockingQueue . Lekin
BlockingDequeular standart Collection Frameworks dan hamma narsani amalga oshiradilar
LinkedBlockingDeque. Har bir navbat alohida ko'rib chiqish mavzusidir. Va ushbu ko'rib chiqish doirasida biz sinf ierarxiyasini nafaqat bilan
List, balki quyidagi bilan ham tasvirlaymiz
Queue:
Diagrammada ko'rib turganimizdek, Java Collections Framework interfeyslari va sinflari bir-biriga juda bog'langan. Keling, ierarxiyaning yana bir tarmog'ini qo'shamiz -
Set.
Oʻrnatish
Set- "to'plam" deb tarjima qilingan. U navbat va ro'yxatdan
Setelementlarni saqlash bo'yicha ko'proq mavhumligi bilan farq qiladi.
Set- predmetlar qopiga o'xshab, u erda ob'ektlar qanday joylashganligi va qanday tartibda yotqizilganligi noma'lum.
Java-da bunday to'plam java.util.Set interfeysi bilan ifodalanadi . Hujjatlarda aytilganidek,
Setbu "takroriy elementlarni o'z ichiga olmaydigan to'plam". Qizig'i shundaki, interfeysning o'zi
Setinterfeysga yangi usullar qo'shmaydi
Collection, lekin faqat talablarni aniqlaydi (nima dublikat bo'lmasligi kerakligi haqida). Bundan tashqari, oldingi tavsifdan shuni ko'rsatadiki, siz
Setundan oddiygina elementni ololmaysiz. Iterator elementlarni olish uchun ishlatiladi.
Setu bilan bog'langan yana bir nechta interfeyslarga ega. Birinchisi
SortedSet. Nomidan ko'rinib turibdiki,
SortedSetbunday to'plam tartiblanganligini ko'rsatadi va shuning uchun elementlar interfeysni amalga oshiradi
Comparableyoki ko'rsatiladi
Comparator. Bundan tashqari,
SortedSetu bir nechta qiziqarli usullarni taklif qiladi:
firstBundan tashqari, usullar (qiymat bo'yicha eng kichik element) va (qiymat bo'yicha eng katta element) mavjud
last. Voris
SortedSetbor -
NavigableSet. Ushbu interfeysning maqsadi tegishli elementlarni aniqroq aniqlash uchun zarur bo'lgan navigatsiya usullarini tavsiflashdir. Qizig'i shundaki
NavigableSet, u odatdagi iteratorga (eng kichikdan kattagacha) teskari tartib uchun iteratorni qo'shadi -
descendingIterator. Bunga qo'shimcha ravishda, elementlar teskari tartibda joylashgan o'zingiz (View) ko'rinishini olish
NavigableSetusulidan foydalanishga imkon beradi .
descendingSetBu shunday deyiladi
View, chunki olingan element orqali siz asl elementning elementlarini o'zgartirishingiz mumkin
Set. Ya'ni, mohiyatiga ko'ra, u asl ma'lumotlarning nusxasi emas, balki boshqacha tarzda ifodasidir. Qizig'i shundaki,
NavigableSet, kabi , (minimal) va (maksimal) elementlarni
Queueishlay oladi . Ya'ni, bu elementni oladi va uni to'plamdan olib tashlaydi. Qanday turdagi ilovalar mavjud? Birinchidan, eng mashhur dastur hash-kodga asoslangan -
HashSet . Yana bir teng darajada taniqli dastur qizil-qora daraxtga asoslangan -
TreeSet . Keling, diagrammamizni to'ldiramiz:
pollFirstpollLast
To'plamlar ichida ierarxiyani - hermitlarni saralash qoladi. Qaysi bir qarashda chetda turadi -
java.util.Map.
Xaritalar
Xaritalar bu ma'lumotlar tuzilmasi bo'lib, unda ma'lumotlar kalit yordamida saqlanadi. Masalan, kalit ID yoki shahar kodi bo'lishi mumkin. Va bu kalit orqali ma'lumotlar qidiriladi. Qizig'i shundaki, kartalar alohida ko'rsatiladi. Ishlab chiquvchilarga ko'ra ("
Java Collections API Design FAQ "ga qarang), kalit-qiymat xaritasi to'plam emas. Xaritalar esa tezroq kalitlar to'plami, qiymatlar to'plami, kalit-qiymat juftliklari to'plami sifatida ko'rib chiqilishi mumkin. Bu juda qiziq hayvon. Kartalar qanday usullarni taqdim etadi? Keling, Java API interfeysini ko'rib chiqaylik
java.util.Map . Chunki Xaritalar to'plam bo'lmagani uchun (ular Collections'dan meros bo'lmaydi), ular tarkibida
contains. Va bu mantiqiy. Xarita kalitlar va qiymatlardan iborat. Usullardan qaysi birini tekshirish kerak
containsva qanday qilib chalkashmaslik kerak? Shuning uchun interfeys
Mapikki xil versiyaga ega:
containsKey(kalitni o'z ichiga oladi) va
containsValue(qiymatni o'z ichiga oladi). Undan foydalanish
keySetsizga kalitlar to'plamini olish imkonini beradi (xuddi shu
Set). Va usul yordamida
valuesbiz xaritadagi qiymatlar to'plamini olishimiz mumkin. Xaritadagi kalitlar noyobdir, bu ma'lumotlar tuzilishi bilan ta'kidlangan
Set. Qiymatlar takrorlanishi mumkin, bu To'plam ma'lumotlar tuzilmasi tomonidan ta'kidlangan. Bundan tashqari, usul yordamida
entrySetbiz kalit-qiymat juftliklari to'plamini olishimiz mumkin. Siz eng batafsil tahlillarda qanday karta ilovalari borligi haqida ko'proq o'qishingiz mumkin:
HashMapMen ham juda o'xshash nima ko'rishni istardim
HashSet,
TreeMapva
TreeSet. Ular hatto o'xshash interfeyslarga ega:
NavigableSetva
NavigableMap,
SortedSetva
SortedMap. Shunday qilib, bizning yakuniy xaritamiz quyidagicha ko'rinadi:
Biz qiziqarli fakt bilan yakunlashimiz mumkinki, to'plam
Setichki foydalanadi
Map, bu erda qo'shilgan qiymatlar kalitlar va qiymat hamma joyda bir xil. Bu qiziqarli, chunki u
Mapto'plam emas va qaytaradi
Set, bu to'plamdir, lekin aslida sifatida amalga oshiriladi
Map. Bir oz surreal, lekin shunday bo'ldi)
Xulosa
Yaxshi xabar shundaki, ushbu sharh shu erda tugaydi. Yomon xabar shundaki, bu juda ko'rib chiqilgan maqola. Har bir to'plamning har bir amalga oshirilishi alohida maqolaga loyiqdir, shuningdek, bizning ko'zimizdan yashiringan har bir algoritm uchun. Ammo bu ko'rib chiqishning maqsadi ular nima ekanligini va interfeyslar o'rtasida qanday aloqalar borligini eslab qolishdir. Umid qilamanki, diqqat bilan o'qiganingizdan so'ng siz xotiradan to'plamlarning diagrammasini chizishingiz mumkin.
Odatdagidek, ba'zi havolalar:
#Viacheslav
GO TO FULL VERSION