Yolun başlanğıcı
Bu gün mən “ Java Collections Framework ” kimi maraqlı bir mövzu haqqında və ya sadə dillə desək, kolleksiyalar haqqında danışmaq istərdim . Kodun işinin çox hissəsi məlumatların bu və ya digər formada işlənməsidir. İstifadəçilərin siyahısını əldə edin, ünvanların siyahısını əldə edin və s. Birtəhər onları çeşidləyin, axtarış aparın, müqayisə edin. Bu səbəbdən kolleksiyalar haqqında bilik əsas bacarıq hesab olunur. Ona görə də bu haqda danışmaq istəyirəm. Bundan əlavə, Java tərtibatçılarının müsahibələrində ən çox yayılmış suallardan biri kolleksiyalardır. Məsələn, "kolleksiyaların iyerarxiyasını çəkin". Onlayn tərtibçi yolumuzda bizə kömək edəcək. Məsələn, siz " Tutorialspoint
Online Java Compiler " və ya
Repl.it istifadə edə bilərsiniz. İstənilən məlumat strukturları ilə tanış olmaq yolu adi dəyişənlərdən (Dəyişənlər) başlayır. Oracle veb saytında müxtəlif mövzular "yollar" və ya Trails kimi təqdim olunur. Beləliklə, Java ilə tanış olmağın yolu “
Trail: Java Dilini Öyrənmək: Mündəricat ” adlanır. Və dilin əsasları (yəni Dil Əsasları) Dəyişənlərlə başlayır. Beləliklə, sadə bir kod yazaq:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Bu kodun yalnız bir dəyişən üçün yaxşı və gözəl olduğunu başa düşməkdən başqa, hər şey yaxşıdır. Onlardan bir neçəsi varsa nə etməli? Massivlər bir növ məlumatları saxlamaq üçün icad edilmişdir. Oracle-dan eyni Trail-də massivlərə həsr olunmuş ayrıca bölmə var. Bu bölmə belə adlanır: "
Massivlər ". Massivlərlə işləmək də olduqca sadədir:
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));
}
}
Massivlər bir neçə dəyərin bir yerdə saxlanması problemini həll edir. Lakin bu, bir məhdudiyyət qoyur: massiv ölçüsü sabitdir. Əgər misaldakı kimi ölçü = 2 dediksə, onda ikiyə bərabərdir. Hamısı budur. Daha böyük massiv istəyiriksə, yeni bir nümunə yaratmalıyıq. Həmçinin, element tapmaq da massiv üçün çətin məsələdir. Bir üsul var
Arrays.binarySearch, lakin bu axtarış yalnız çeşidlənmiş massivdə işləyir (çeşidlənməmiş massiv üçün nəticə qeyri-müəyyəndir və ya sadəcə gözlənilməzdir). Yəni axtarış bizi hər dəfə çeşidləməyə məcbur edəcək. Silinmə də yalnız dəyəri təmizləyir. Buna görə də, biz hələ də massivdə nə qədər məlumat olduğunu bilmirik, yalnız massivdə neçə hüceyrə olduğunu bilirik. Massivlər haqqında biliklərinizi yeniləmək üçün:
Java dilinin inkişafı nəticəsində bu gün haqqında danışacağımız JDK 1.2-də Java Collections Framework meydana çıxdı.
Kolleksiya
Ən əvvəldən xərcləməyə başlayın. Niyə Kolleksiyalar? Termin özü "Tip nəzəriyyəsi" və "Mücərrəd məlumat növləri" kimi şeylərdən gəlir. Ancaq hər hansı yüksək məsələlərə baxmırsınızsa, onda bir neçə şeyimiz olduqda, onları "əşyaların toplusu" adlandıra bilərik. Əşyaları toplayanlar. Ümumiyyətlə, toplama sözünün özü lat dilindəndir. kolleksiya "toplama, toplama". Yəni kolleksiya nəyinsə toplusudur, bəzi elementlər üçün konteynerdir. Beləliklə, elementlər toplusumuz var. Bununla nə etmək istəyə bilərik:
Gördüyünüz kimi, biz olduqca məntiqli şeylər istəyə bilərik. Həmçinin başa düşürük ki, bir neçə kolleksiya ilə nəsə etmək istəyə bilərik:
Müvafiq olaraq, Java tərtibatçıları bütün kolleksiyalar üçün bu ümumi davranışı təsvir etmək üçün
java.util.Collection interfeysini yazdılar . Kolleksiya interfeysi bütün kolleksiyaların yarandığı yerdir. Kolleksiya bir fikirdir, bütün kolleksiyaların necə davranması barədə fikirdir. Buna görə də "Kolleksiya" termini interfeys kimi ifadə edilir. Təbii ki, interfeysin həyata keçirilməsi lazımdır. İnterfeys
java.util.Collectionmücərrəd bir sinifə
AbstractCollection, yəni digər tətbiqlər üçün skeleti təmsil edən bəzi "mücərrəd kolleksiyaya" malikdir (JavaDoc-da sinifin üstündə yazıldığı kimi
java.util.AbstractCollection). Kolleksiyalar haqqında danışarkən, geri qayıdıb xatırlayaq ki, biz onları təkrarlamaq istəyirik. Bu o deməkdir ki, biz elementləri bir-bir təkrarlamaq istəyirik. Bu çox vacib bir anlayışdır. Buna görə də, interfeys
Collectionmiras alınır
Iterable. Bu çox vacibdir, çünki... birincisi, Iterable hər şey məzmununa əsaslanaraq İteratoru qaytara bilməlidir. İkincisi, İterable olan hər şey döngələrdə istifadə edilə bilər
for-each-loop. Və məhz iteratorun köməyi ilə , , kimi
AbstractCollectionüsullar həyata keçirilir . Və kolleksiyaları başa düşmək yolu ən çox yayılmış məlumat strukturlarından biri ilə başlayır - siyahı, yəni. .
containstoArrayremoveList
Siyahılar
Beləliklə, siyahılar kolleksiyaların iyerarxiyasında mühüm yer tutur:
Gördüyümüz kimi siyahılar
java.util.List interfeysini həyata keçirir . Siyahılar bir-birinin ardınca müəyyən ardıcıllıqla düzülmüş elementlər toplusunun olduğunu ifadə edir. Hər bir elementin bir indeksi var (massivdəki kimi). Tipik olaraq, siyahı eyni dəyərə malik elementlərə sahib olmağa imkan verir. Yuxarıda dediyimiz kimi,
Listelementin indeksi haqqında bilir. Bu, indeks üzrə elementi əldə etməyə (
get) və ya müəyyən indeks ( ) üçün dəyər təyin etməyə imkan verir
set. Yığım üsulları
add,
addAll,
removeonların icra olunacağı indeksi təyin etməyə imkan verir. Bundan əlavə, y
Listadlı iteratorun öz versiyası var
ListIterator. Bu iterator elementin indeksini bilir, ona görə də o, təkcə irəli deyil, həm də geriyə doğru təkrarlaya bilər. Hətta kolleksiyanın müəyyən yerindən də yaradıla bilər. Bütün tətbiqlər arasında ən çox istifadə olunan ikisi var:
ArrayListvə
LinkedList. Birincisi, bu , massiv ( ) əsasında
ArrayListbir siyahıdır ( ).
Bu elementlərə "Təsadüfi giriş" əldə etməyə imkan verir . Təsadüfi giriş istənilən indeksə malik elementi tapana qədər bütün elementləri təkrarlamaqdansa, dərhal bir elementi indeks üzrə əldə etmək imkanıdır. Buna nail olmağa imkan verən əsas kimi massivdir. Əksinə, bu, Əlaqəli Siyahıdır. Əlaqədar siyahıdakı hər bir giriş məlumatın özünü saxlayan formada , həmçinin növbəti (növbəti) və əvvəlki (əvvəlki) keçidlə təmsil olunur . Beləliklə, "Ardıcıl giriş
" həyata keçirilir . Aydındır ki, 5-ci elementi tapmaq üçün birinci elementdən sonuncuya keçməliyik, çünki bizim beşinci elementə birbaşa çıxışımız yoxdur. Biz ona yalnız 4-cü elementdən daxil ola bilərik. Onların konsepsiyasındakı fərq aşağıda verilmişdir:
ListArrayLinkedListEntryEntryLinkedList
İşdə, başa düşdüyünüz kimi, bir fərq də var. Məsələn, elementlərin əlavə edilməsi. Elementlər
LinkedListsadəcə zəncirin halqaları kimi bağlanır. Lakin
ArrayListo, elementləri massivdə saxlayır. Və massiv, bildiyimiz kimi, ölçüsünü dəyişə bilməz. O zaman necə işləyir
ArrayList? Və çox sadə işləyir. Massivdəki boşluq bitdikdə 1,5 dəfə artır. Böyütmə kodu budur:
int newCapacity = oldCapacity + (oldCapacity >> 1); Əməliyyatdakı digər fərq elementlərin hər hansı ofsetidir. Məsələn, elementləri ortasına əlavə edərkən və ya çıxararkən. Elementdən silmək üçün
LinkedListsadəcə bu elementə istinadları silin. vəziyyətində,
ArrayListbiz elementləri hər dəfə istifadə edərək dəyişdirməyə məcbur oluruq
System.arraycopy. Beləliklə, elementlər nə qədər çox olsa, bir o qədər çox hərəkət etməli olacaqsınız. Daha ətraflı təsviri bu məqalələrdə tapa bilərsiniz:
ArrayList-i araşdırdıqdan sonra onun "sələfi" olan java.util.Vector sinfini xatırlamaya bilməzsiniz . Kolleksiya ilə işləmək üsullarının (əlavə etmək, silmək və s.) sinxronlaşdırılması
Vectorilə fərqlənir .
ArrayListYəni bir iplik (
Thread) elementlər əlavə edərsə, o zaman digər iplər birinci ip öz işini bitirənə qədər gözləyəcək. Mövzu təhlükəsizliyi çox vaxt tələb olunmadığından,
ArrayListsinif üçün JavaDoc-da açıq şəkildə qeyd edildiyi kimi, belə hallarda sinifdən istifadə etmək tövsiyə olunur
Vector. Bundan əlavə,
Vectorölçüsünü 1,5 dəfə deyil,
ArrayList2 dəfə artırır. Əks halda, davranış eynidir -
Vectorelementlərin massiv şəklində saxlanması gizlənir və elementlərin əlavə edilməsi/çıxarılması ilə eyni nəticələr var
ArrayList. Əslində
Vectorbunu bir səbəblə xatırladıq.
Javadoc-a baxsaq, "Birbaşa Bilinən Alt Siniflər"də java.util.Stack kimi bir struktur görəcəyik . Yığın LIFO
last-in-first-out(son girən, ilk çıxan) strukturu olan maraqlı bir quruluşdur. İngilis dilindən tərcümə edilmiş yığın yığındır (məsələn, kitab yığını kimi). Yığın əlavə üsulları həyata keçirir:
peek(baxın, baxın),
pop(itələyin),
push(itələyin). Metod
peekbaxmaq kimi tərcümə olunur (məsələn,
çantanın içərisinə baxmaq “
torbanın içərisinə baxmaq ”,
açar dəliyindən baxmaq isə “ açar dəliyindən baxmaq ” kimi tərcümə olunur ). Bu üsul yığının "üst hissəsinə" baxmağa imkan verir, yəni. sonuncu elementi yığından çıxarmadan (yəni çıxarmadan) əldə edin. Metod
pushyeni elementi yığına itələyir (əlavə edir) və onu qaytarır, element metodu isə
popsilinmiş elementi itələyir (çıxarır) və qaytarır. Hər üç halda (yəni gözdən keçirmə, pop və itələmə) biz yalnız sonuncu elementlə (yəni “yığın üstü”) işləyirik. Bu yığın strukturunun əsas xüsusiyyətidir. Yeri gəlmişkən, “Proqramçının karyerası” (Cracking Coding Interview) kitabında təsvir edilən stekləri başa düşmək üçün maraqlı bir tapşırıq var. ” strukturu (FIFO). Bu belə görünməlidir:
Bu tapşırığın təhlili burada tapıla bilər: "
Yığınlardan istifadə edərək növbə həyata keçirin - The Queue ADT ("LeetCode-da "Yığınlardan istifadə edərək növbə həyata keçirin") ". Beləliklə, biz rəvan şəkildə yeni məlumat strukturuna - növbəyə keçirik.
Növbə
Növbə bizə həyatdan tanış olan bir quruluşdur. Mağazalara, həkimlərə növbələr. İlk gələn (First In) növbəni ilk tərk edən olacaq (First Out). Java-da növbə
java.util.Queue interfeysi ilə təmsil olunur . Növbənin Javadoc-a görə, növbə aşağıdakı üsulları əlavə edir:
Gördüyünüz kimi, sifariş üsulları var (onların icra edilməməsi istisnalarla doludur) və sorğu üsulları var (onları icra edə bilməmək səhvlərə səbəb olmur). Elementi çıxarmadan da əldə etmək mümkündür (peek və ya element). Növbə interfeysinin də faydalı davamçısı var -
Deque . Bu, "ikitərəfli növbə" adlanan növbədir. Yəni, belə bir növbə bu strukturdan həm əvvəldən, həm də sondan istifadə etməyə imkan verir. Sənədlərdə deyilir ki, "Deques həm də LIFO (Last-In-First-Out) stekləri kimi istifadə edilə bilər. Bu interfeys köhnə Stack sinfinə üstünlük verməklə istifadə edilməlidir.", yəni Deque tətbiqetmələrindən istifadə etmək tövsiyə olunur. Yığın. Javadoc Deque interfeysinin hansı üsulları təsvir etdiyini göstərir:
Gəlin görək hansı tətbiqlər var. Və maraqlı bir fakt görəcəyik - LinkedList növbə düşərgəsinə daxil oldu) Yəni, LinkedList həm
List, həm də tətbiq edir
Deque. Ancaq "yalnız növbələr" də var, məsələn
PriorityQueue. O, tez-tez xatırlanmır, amma boş yerə. Birincisi, bu növbədə "müqayisə olunmayan obyektləri" istifadə edə bilməzsiniz, yəni. ya Comparator göstərilməlidir, ya da bütün obyektlər müqayisə edilə bilən olmalıdır. İkincisi, "bu tətbiq sıralama və sıradan çıxarma üsulları üçün O(log(n)) vaxtını təmin edir". Loqarifmik mürəkkəbliyin bir səbəbi var. Yığın əsasında həyata keçirilən PriorityQueue. Javadoc deyir: "Prioritet növbəsi balanslaşdırılmış ikili yığın kimi təqdim olunur." Bunun üçün saxlama özü adi bir massivdir. Hansı ki, lazım olanda böyüyür. Yığın kiçik olduqda, 2 dəfə artır. Və sonra 50%. Koddan şərh: "Əgər kiçikdirsə, ikiqat ölçü; əks halda 50% böyüyür". Prioritet növbəsi və Binary Heap ayrı bir mövzudur. Beləliklə, daha çox məlumat üçün:
Tətbiq olaraq
java.util.ArrayDequejava.util.Deque sinifindən istifadə edə bilərsiniz . Yəni siyahılar əlaqəli siyahı və massivdən istifadə etməklə həyata keçirilə bilər və növbələr də massivdən və ya əlaqəli siyahıdan istifadə etməklə həyata keçirilə bilər. və interfeyslərində "bloklama növbəsini" təmsil edən nəsillər var: və . Budur, adi növbələrlə müqayisədə interfeys dəyişikliyi:
QueueDequeBlockingQueueBlockingDeque
Növbələrin bloklanmasına dair bəzi nümunələrə baxaq. Amma maraqlıdırlar. Məsələn, BlockingQueue aşağıdakılar tərəfindən həyata keçirilir:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Lakin
BlockingDequeonlar standart Kolleksiya Çərçivələrindən tutmuş hər şeyi həyata keçirirlər
LinkedBlockingDeque. Hər növbə ayrı bir baxışın mövzusudur. Və bu baxış çərçivəsində biz sinif iyerarxiyasını təkcə ilə deyil
List, həm də ilə təsvir edəcəyik
Queue:
Diaqramdan da gördüyümüz kimi, Java Collections Framework-in interfeysləri və sinifləri bir-birinə çox bağlıdır. İyerarxiyanın daha bir qolunu əlavə edək -
Set.
Set
Set— “dəst” kimi tərcümə olunur. O , növbə və siyahıdan
Setelementlərin saxlanması üzərində daha çox abstraksiyasına görə fərqlənir.
Set- cisimlərin necə yerləşdiyi və hansı ardıcıllıqla düzüldüyü məlum olmayan əşyalar torbası kimi. Java-da belə dəst
java.util.Set interfeysi ilə təmsil olunur . Sənədlərdə deyildiyi kimi,
Setbu, "dublikat elementləri olmayan kolleksiyadır". Maraqlıdır ki, interfeysin özü
Setinterfeysə yeni üsullar əlavə etmir
Collection, ancaq tələbləri aydınlaşdırır (nəyin dublikatları olmamalıdır). Bundan əlavə, əvvəlki təsvirdən belə çıxır ki,
Setondan sadəcə element əldə edə bilməzsiniz. İterator elementləri əldə etmək üçün istifadə olunur.
Setonunla əlaqəli daha bir neçə interfeys var. Birincisi
SortedSet. Adından göründüyü kimi,
SortedSetbu, belə bir çoxluğun çeşidləndiyini göstərir və buna görə də elementlər interfeysi həyata keçirir
Comparablevə ya müəyyən edilir
Comparator. Bundan əlavə,
SortedSetbir neçə maraqlı üsul təklif edir:
firstBundan əlavə, üsullar (qiymətinə görə ən kiçik element) və (qiymətinə görə ən böyük element) var
last.
SortedSetVarisi var -
NavigableSet. Bu interfeysin məqsədi müvafiq elementləri daha dəqiq müəyyən etmək üçün lazım olan naviqasiya üsullarını təsvir etməkdir. Maraqlısı odur
NavigableSetki, o, adi iteratora (kiçikdən böyüyə doğru gedir) əks sıra üçün bir iterator əlavə edir -
descendingIterator. Bundan əlavə, elementlərin tərs qaydada olduğu özünüzün görünüşünü (View) əldə etmək üçün
NavigableSetmetoddan istifadə etməyə imkan verir . Bu , yaranan element vasitəsilə orijinal elementin elementlərini dəyişdirə biləcəyiniz üçün
descendingSetdeyilir . Yəni mahiyyət etibarı ilə o, ilkin verilənlərin surəti deyil, fərqli şəkildə təqdim edilməsidir. Maraqlıdır ki, , kimi , (minimal) və (maksimal) elementləri idarə edə bilir. Yəni bu elementi alır və onu dəstdən çıxarır. Hansı növ tətbiqlər var? Birincisi, ən məşhur tətbiq hash koduna əsaslanır -
HashSet . Digər eyni dərəcədə tanınmış bir tətbiq qırmızı-qara ağaca əsaslanır -
TreeSet . Diaqramımızı tamamlayaq:
ViewSetNavigableSetQueuepollFirstpollLast
Kolleksiyalarda iyerarxiyanı - hermitləri sıralamaq qalır. Hansı ki, ilk baxışdan kənarda dayanır -
java.util.Map.
Xəritələr
Xəritələr məlumatların açar tərəfindən saxlanıldığı məlumat strukturudur. Məsələn, açar ID və ya şəhər kodu ola bilər. Məhz bu açarla məlumatlar axtarılacaq. Maraqlıdır ki, kartların ayrı-ayrılıqda göstərilməsidir. Tərtibatçıların fikrincə (bax "
Java Collections API Design FAQ "), açar-dəyər xəritəsi kolleksiya deyil. Və xəritələri daha tez açarlar toplusu, dəyərlər toplusu, açar-dəyər cütləri toplusu kimi düşünmək olar. Bu çox maraqlı heyvandır. Kartlar hansı üsulları təmin edir? Java API interfeysinə baxaq
java.util.Map . Çünki Xəritələr kolleksiya olmadığı üçün (Onlar Kolleksiyalardan miras qalmır), onlarda
contains. Və bu məntiqlidir. Xəritə açarlar və dəyərlərdən ibarətdir. Metod bunlardan hansını yoxlamalıdır
containsvə necə çaşdırılmamalı? Buna görə də, interfeys
Mapiki fərqli versiyaya malikdir:
containsKey(açar ehtiva edir) və
containsValue(dəyər ehtiva edir). Onun istifadəsi
keySetsizə bir sıra açarlar əldə etməyə imkan verir (eynisi
Set). Və metoddan istifadə edərək
valuesxəritədə dəyərlər toplusunu əldə edə bilərik. Xəritədəki düymələr unikaldır və bu, məlumat strukturu ilə vurğulanır
Set. Kolleksiya məlumat strukturu ilə vurğulanan dəyərlər təkrarlana bilər. Bundan əlavə, metoddan istifadə edərək
entrySetbir sıra açar-dəyər cütlərini əldə edə bilərik. Ən ətraflı təhlillərdə hansı kart tətbiqləri haqqında daha çox oxuya bilərsiniz:
Mən də nəyə
HashMapçox bənzədiyini görmək istərdim
HashSetvə
TreeMap.
TreeSetOnların hətta oxşar interfeysləri var:
NavigableSetvə
NavigableMap,
SortedSetvə
SortedMap. Beləliklə, son xəritəmiz belə görünəcək:
SetKolleksiyanın daxili istifadə etdiyi maraqlı faktla bitirə bilərik ki
Map, burada əlavə dəyərlər açardır və dəyər hər yerdə eynidir. Bu maraqlıdır, çünki o,
Mapkolleksiya deyil və geri qaytarılır
Set, kolleksiyadır, lakin əslində kimi həyata keçirilir
Map. Bir az sürreal, amma belə çıxdı)
Nəticə
Yaxşı xəbər budur ki, bu baxış burada başa çatır. Pis xəbər budur ki, bu çox nəzərdən keçirilən məqalədir. Kolleksiyaların hər birinin hər bir tətbiqi ayrıca bir məqaləyə layiqdir, həmçinin hər bir alqoritm üçün gözümüzdən gizlədilib. Lakin bu baxışın məqsədi onların nə olduğunu və interfeyslər arasında hansı əlaqələrin olduğunu xatırlamaqdır. Ümid edirəm ki, diqqətlə oxuduqdan sonra yaddaşdan kolleksiyaların diaqramını çəkə biləcəksiniz.
Həmişə olduğu kimi, bəzi bağlantılar:
#Viaçeslav
GO TO FULL VERSION