Жолдың басы
Бүгін мен « Java Collections Framework » сияқты қызықты тақырып немесе қарапайым тілмен айтқанда, жинақтар туралы сөйлескім келеді . Код жұмысының көпшілігі деректерді бір немесе басқа пішінде өңдеу болып табылады. Пайдаланушылар тізімін алыңыз, мекенжайлар тізімін алыңыз және т.б. Қандай да бір жолмен оларды сұрыптаңыз, іздеңіз, салыстырыңыз. Сондықтан жинақтарды білу негізгі дағды болып саналады. Сондықтан мен бұл туралы айтқым келеді. Сонымен қатар, Java әзірлеушілерінің сұхбаттарында жиі кездесетін сұрақтардың бірі - жинақтар. Мысалы, «жинақтар иерархиясын сызу». Біздің жолымызда онлайн компилятор көмектеседі. Мысалы, сіз « Tutorialspoint
Online Java Compiler » немесе
Repl.it пайдалана аласыз. Кез келген деректер құрылымдарымен танысу жолы қарапайым айнымалылардан (Айнымалылар) басталады. Oracle веб-сайтында әртүрлі тақырыптар "жолдар" немесе Trails ретінде ұсынылған. Сонымен, Java тілімен танысу жолы «
Trail: Java тілін үйрену: Мазмұны » деп аталады. Ал тілдің негіздері (яғни Тіл негіздері) Айнымалылардан басталады. Сондықтан қарапайым codeты жазайық:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Бұл барлық нәрседе жақсы, тек бір айнымалы үшін бұл code жақсы және әдемі екенін түсінеміз. Егер олардың бірнешеуі болса, не істеу керек? Массивтер бір типтегі деректерді сақтау үшін ойлап табылды. Сол Oracle Trail бағдарламасында массивтерге арналған бөлек бөлім бар.
Бұл бөлім: « Массивтер » деп аталады . Массивтермен жұмыс істеу де өте қарапайым:
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));
}
}
Массивтер бірнеше мәндерді бір жерде сақтау мәселесін шешеді. Бірақ ол шектеу қояды: массив өлшемі тұрақты. Егер мысалдағыдай өлшем = 2 деп айтқан болсақ, онда ол екіге тең болады. Болды. Егер біз үлкен массив алғымыз келсе, жаңа дананы жасауымыз керек. Сондай-ақ, элементті табу массив үшін қиын нәрсе. Әдісі бар
Arrays.binarySearch, бірақ бұл іздеу тек сұрыпталған массивте жұмыс істейді (сұрыпталмаған массив үшін нәтиже анықталмаған немесе жай ғана болжау мүмкін емес). Яғни, ізденіс бізді әр жолы сұрыптауға міндеттейді. Жою тек мәнді ғана тазартады. Сондықтан, біз әлі де массивте қанша деректер бар екенін білмейміз, тек массивте қанша ұяшық бар екенін білеміз. Массивтер туралы біліміңізді жаңарту үшін:
Java тілінің дамуының нәтижесінде JDK 1.2-де Java Collections Framework пайда болды, ол туралы біз бүгін айтатын боламыз.
Жинақ
Ең басынан бастап шығындарды бастаңыз. Неліктен коллекциялар? Терминнің өзі «Тип теориясы» және «Деректердің дерексіз түрлері» сияқты нәрселерден шыққан. Бірақ егер сіз қандай да бір жоғары нәрселерді қарастырмасаңыз, онда бізде бірнеше нәрсе болғанда, біз оларды «заттардың жинағы» деп атауға болады. Заттарды жинайтындар. Жалпы, жинау деген сөздің өзі лат тілінен шыққан. коллекция «жинау, жинау». Яғни коллекция – бір нәрсенің жиынтығы, кейбір элементтерге арналған контейнер. Сонымен, бізде элементтер жиынтығы бар. Біз онымен не істегіміз келеді:
Көріп отырғаныңыздай, біз қисынды нәрселерді қалауымыз мүмкін. Сондай-ақ біз бірнеше жинақтармен бірдеңе жасағымыз келетінін түсінеміз:
Тиісінше, Java әзірлеушілері java.util.Collection интерфейсін барлық жинақтар үшін осы жалпы әрекетті сипаттау үшін жазды . Коллекция интерфейсі барлық жинақтардың пайда болған жері. Коллекция - бұл идея, бұл барлық жинақтардың өзін қалай ұстау керектігі туралы идея. Сондықтан «Жинақ» термині интерфейс ретінде көрсетіледі. Әрине, интерфейс іске асыруды қажет етеді. Интерфейстің
java.util.Collectionдерексіз класы бар
AbstractCollection, яғни басқа іске асырулар үшін қаңқаны білдіретін кейбір «дерексіз жинақ» (JavaDoc-та класс үстінде жазылғандай
java.util.AbstractCollection). Жинақтар туралы айтатын болсақ, біз оларды қайталағымыз келетінін еске түсірейік. Бұл элементтерді бір-бірлеп қайталағымыз келетінін білдіреді. Бұл өте маңызды тұжырымдама. Сондықтан интерфейс
Collectionмұраға алынған
Iterable. Бұл өте маңызды, өйткені... біріншіден, Iterable барлығы оның мазмұнына негізделген Итераторды қайтара алуы керек. Екіншіден, циклдерде қайталанатын барлық нәрселерді қолдануға болады
for-each-loop. Ал , , сияқты
AbstractCollectionәдістер итератордың көмегімен жүзеге асады . Ал жинақтарды түсіну жолы ең көп таралған деректер құрылымдарының бірі – тізімнен басталады, яғни. .
containstoArrayremoveList
Тізімдер
Сонымен, тізімдер жинақтар иерархиясында маңызды орын алады:
Көріп отырғанымыздай, тізімдер
java.util.List интерфейсін жүзеге асырады . Тізімдер бізде бірінен соң бірі белгілі бір ретпен орналасқан элементтер жиынтығы бар екенін білдіреді. Әрбір элементтің индексі бар (массивтегі сияқты). Әдетте, тізім бірдей мәнге ие элементтерді алуға мүмкіндік береді. Жоғарыда айтқанымыздай,
Listол элементтің индексі туралы біледі.
getБұл индекс бойынша элементті алуға ( ) немесе белгілі бір индекс (
set) үшін мән орнатуға мүмкіндік береді. Жинау әдістері
add,
addAll,
removeоларды орындайтын индексті көрсетуге мүмкіндік береді. Бұған қоса, y-де
Listитератордың деп аталатын өз нұсқасы бар
ListIterator. Бұл итератор элементтің индексі туралы біледі, сондықтан ол алға ғана емес, артқа да қайталай алады. Оны тіпті коллекциядағы белгілі бір жерден жасауға болады. Барлық іске асырулардың ішінде ең жиі қолданылатын екі түрі бар:
ArrayListжәне
LinkedList. Біріншіден,
ArrayListбұл (
List) массивіне негізделген тізім (
Array).
Бұл элементтерге «кездейсоқ қол жеткізуге» қол жеткізуге мүмкіндік береді . Кездейсоқ қол жеткізу - қажетті индексі бар элементті тапқанша барлық элементтерді қайталаудың орнына, бірден индекс бойынша элементті алу мүмкіндігі. Бұл қол жеткізуге мүмкіндік беретін негіз ретінде массив. Керісінше,
LinkedListбұл байланыстырылған тізім.
EntryБайланыстырылған тізімдегі әрбір жазба деректердің өзін, сондай-ақ келесі (келесі) және алдыңғы (алдыңғы) сілтемесін сақтайтын пішінде ұсынылған
Entry. Осылайша
LinkedListжүзеге асырады «Тізбекті қол жеткізу
» . 5-ші элементті табу үшін бірінші элементтен соңғысына өтуіміз керек екені анық, өйткені бесінші элементке тікелей қол жеткізе алмаймыз. Біз оған тек 4-ші элементтен қол жеткізе аламыз. Олардың тұжырымдамасындағы айырмашылық төменде келтірілген:
Жұмыста, сіз түсінгендей, айырмашылық бар. Мысалы, элементтерді қосу. Элементтер
LinkedListтізбектегі сілтемелер сияқты жай біріктірілген. Бірақ
ArrayListол элементтерді массивте сақтайды. Ал массив, біз білетіндей, оның өлшемін өзгерте алмайды. Сонда ол қалай жұмыс істейді
ArrayList? Және бұл өте қарапайым жұмыс істейді. Массивтегі бос орын таусылғанда, ол 1,5 есе артады. Міне масштабтау codeы:
int newCapacity = oldCapacity + (oldCapacity >> 1); Жұмыстағы тағы бір айырмашылық элементтердің кез келген ығысуы болып табылады. Мысалы, ортасына элементтерді қосқанда немесе алып тастағанда. Элементтен жою үшін
LinkedListосы элементке сілтемелерді алып тастаңыз. Жағдайда
ArrayListбіз элементтерді әр жолы арқылы ауыстыруға мәжбүр боламыз
System.arraycopy. Осылайша, элементтер неғұрлым көп болса, соғұрлым көп әрекеттерді орындау керек болады. Толығырақ сипаттаманы мына мақалалардан табуға болады:
ArrayList-ті зерттей отырып, оның «алдыңғысы» java.util.Vector сыныбын еске түсіруге болмайды . Ол жинақпен жұмыс істеу әдістерінің (қосу, жою және т.б.) синхрондалуымен ерекшеленеді
Vector.
ArrayListЯғни, егер бір ағын (
Thread) элементтерді қосса, онда басқа ағындар бірінші ағын жұмысын аяқтағанша күтеді.
ArrayListЖіп қауіпсіздігі жиі талап етілмейтіндіктен, сыныпқа арналған JavaDoc құжатында нақты көрсетілгендей мұндай жағдайларда сыныпты пайдалану ұсынылады
Vector. Сонымен қатар,
Vectorол оның көлемін 1,5 есе емес,
ArrayList2 есе арттырады. Әйтпесе, мінез-құлық бірдей -
Vectorэлементтерді массив түрінде сақтау жасырылады және элементтерді қосу/алып тастау -дағы сияқты салдарға әкеледі
ArrayList. Шындығында,
Vectorмұның есімізге түсуінің бір себебі бар.
Егер Javadoc ішіне қарасақ, «Тікелей белгілі ішкі сыныптарда» java.util.Stack сияқты құрылымды көреміз . Стек LIFO
last-in-first-out(соңғы кірген, бірінші шығатын) құрылымы болып табылатын қызықты құрылым. Ағылшын тілінен аударылған стек - стек (мысалы, кітаптар дестесі сияқты). Стек қосымша әдістерді жүзеге асырады:
peek(қарау, қарау),
pop(итеру),
push(итеру). Әдіс
peekқарау деп аударылады (мысалы,
сөмкенің ішіне қарау « сөмкенің ішіне қарау » деп аударылады , ал
кілт тесігінен қарау « кілт тесігінен қарау » деп аударылады ). Бұл әдіс стектің «жоғарғы жағын» қарауға мүмкіндік береді, яғни. соңғы элементті стектен алып тастамай (яғни алып тастамай) алыңыз. Әдіс
pushжаңа элементті стекке итеріп (қосады) және оны қайтарады, ал элемент әдісі
popжойылған элементті итереді (жоюды) және қайтарады. Барлық үш жағдайда (мысалы, қарау, поп және итеру) біз тек соңғы элементпен жұмыс істейміз (яғни, «стектің жоғарғы жағы»). Бұл стек құрылымының негізгі ерекшелігі. Айтпақшы, «Бағдарламашының мансабы» (Cracking Coding Interview) кітабында сипатталған стектерді түсінуге арналған қызықты тапсырма бар.Қызықты тапсырма бар, онда «стек» құрылымын (LIFO) пайдалану арқылы «кезекті» іске асыру қажет. құрылымы (FIFO). Ол келесідей болуы керек:
Бұл тапсырманың талдауын мына жерден табуға болады: "
Стектерді пайдалану арқылы кезекті енгізу - ADT кезегі (LeetCode жүйесінде "Стектерді пайдалану арқылы кезекті орындау") ". Осылайша, біз жаңа деректер құрылымына - кезекке біртіндеп көшеміз.
Кезек
Кезек – бізге өмірден таныс құрылым. Дүкендерге, дәрігерлерге кезек. Кім бірінші келсе (Бірінші кірген) кезектен бірінші шығады (Бірінші шыққан).
Java тілінде кезек java.util.Queue интерфейсімен ұсынылған . Кезектің Javadoc нұсқасына сәйкес кезек келесі әдістерді қосады:
Көріп отырғаныңыздай, тапсырыс әдістері бар (оларды орындамау ерекше жағдайларға толы) және сұрау әдістері бар (оларды орындау мүмкін еместігі қателерге әкелмейді). Сондай-ақ элементті алып тастамай-ақ алуға болады (пик немесе элемент). Кезек интерфейсінің де пайдалы мұрагері бар -
Deque . Бұл «екі жақты кезек» деп аталады. Яғни, мұндай кезек бұл құрылымды басынан да, аяғынан да пайдалануға мүмкіндік береді. Құжаттамада "Deques LIFO (Last-In-First-Out) стектері ретінде де пайдаланылуы мүмкін. Бұл интерфейс бұрынғы Stack сыныбына артықшылықпен пайдаланылуы керек.", яғни Deque іске асыруды пайдалану ұсынылады. Стек. Javadoc Deque интерфейсі қандай әдістерді сипаттайтынын көрсетеді:
Қандай іске асыру бар екенін көрейік. Біз қызықты фактіні көреміз - LinkedList кезек лагеріне кірді) Яғни, LinkedList
List, және екеуін де жүзеге асырады
Deque. Бірақ «тек қана кезек» бар, мысалы
PriorityQueue. Оны жиі еске алмайды, бірақ бекер. Біріншіден, сіз бұл кезекте «салыстырмайтын нысандарды» пайдалана алмайсыз, яғни. не Comparator көрсетілуі керек немесе барлық нысандар салыстырмалы болуы керек. Екіншіден, «бұл іске асыру кезекке қою және кезекке қою әдістері үшін O(log(n)) уақытын қамтамасыз етеді». Логарифмдік күрделіліктің себебі бар. Үймеге негізделген PriorityQueue енгізілді. Javadoc былай дейді: «Басымдылық кезегі теңдестірілген екілік үйме ретінде ұсынылған». Бұл үшін жадтың өзі кәдімгі массив. Ол қажет кезде өседі. Үйінді аз болған кезде ол 2 есе артады. Содан кейін 50%. Кодтан түсініктеме: «Егер кішкентай болса, екі еселенген өлшем; әйтпесе 50% өседі». Приоритетті кезек және екілік үйме бөлек тақырып болып табылады. Сонымен, қосымша ақпарат алу үшін:
Іске асыру
java.util.ArrayDequejava.util.Deque сыныбы болуы мүмкін . Яғни, тізімдерді байланыстырылған тізім мен массивтің көмегімен жүзеге асыруға болады, ал кезектерді массив немесе байланыстырылған тізім арқылы да жүзеге асыруға болады. және интерфейстерінің «блоктау кезегін» білдіретін ұрпақтары бар: және . Кәдімгі кезектермен салыстырғанда интерфейстің өзгеруі мынада:
QueueDequeBlockingQueueBlockingDeque
Кезектерді блоктаудың кейбір мысалдарын қарастырайық. Бірақ олар қызықты. Мысалы, BlockingQueue келесілер арқылы жүзеге асырылады:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Бірақ
BlockingDequeолар стандартты Collection Frameworks барлығын жүзеге асырады
LinkedBlockingDeque. Әрбір кезек жеке шолудың тақырыбы болып табылады. Осы шолу аясында біз класс иерархиясын тек -мен ғана емес
List, сонымен бірге -мен де бейнелейміз
Queue:
Диаграммадан көріп отырғанымыздай, Java Collections Framework интерфейстері мен сыныптары бір-бірімен тығыз байланысты. Иерархияның тағы бір тармағын қосайық -
Set.
Орнату
Set— «жиынтық» деп аударылады. Ол кезек пен тізімнен
Setэлементтерді сақтау бойынша үлкен абстракцияда ерекшеленеді.
Set- заттардың қалай орналасқаны және қандай ретпен жатқаны белгісіз заттар салынған қап сияқты.
Java тілінде мұндай жиын java.util.Set интерфейсімен ұсынылған . Құжаттамада айтылғандай,
Setбұл «қайталанатын элементтері жоқ жинақ». Бір қызығы, интерфейстің өзі
Setинтерфейске жаңа әдістерді қоспайды
Collection, бірақ тек талаптарды нақтылайды (қайталанбауы керек туралы). Бұған қоса, алдыңғы сипаттамадан сіз
Setодан элементті ала алмайсыз. Итератор элементтерді алу үшін қолданылады.
Setонымен байланысты тағы бірнеше интерфейстер бар. Біріншісі -
SortedSet. Атауынан көрініп тұрғандай,
SortedSetмұндай жиын сұрыпталғанын көрсетеді, сондықтан элементтер интерфейсті жүзеге асырады
Comparableнемесе көрсетіледі
Comparator. Сонымен қатар,
SortedSetол бірнеше қызықты әдістерді ұсынады:
firstСонымен қатар, әдістер (мәні бойынша ең кіші элемент) және (мәні бойынша ең үлкен элемент) бар
last.
SortedSetМұрагер бар -
NavigableSet. Бұл интерфейстің мақсаты сәйкес элементтерді дәлірек анықтау үшін қажет шарлау әдістерін сипаттау болып табылады. Бір қызығы,
NavigableSetол кәдімгі итераторға (ең кішіден үлкенге қарай жүреді) кері ретті итераторды қосады -
descendingIterator. Сонымен қатар, ол элементтер кері тәртіпте орналасқан өзіңіздің көрінісіңізді (Көру) алу
NavigableSetәдісін пайдалануға мүмкіндік береді .
descendingSetБұл деп аталады
View, себебі алынған элемент арқылы түпнұсқаның элементтерін өзгертуге болады
Set. Яғни, мәні бойынша, бұл түпнұсқа деректердің көшірмесі емес, басқаша түрде бейнеленуі. Бір қызығы,
NavigableSet, сияқты , (минималды) және (максималды) элементтерді
Queueөңдей алады . Яғни, ол осы элементті алады және оны жиынтықтан алып тастайды. Қандай іске асыру түрлері бар? Біріншіден, ең танымал іске асыру хэш-codeқа негізделген -
HashSet . Тағы бір бірдей танымал іске асыру қызыл-қара ағашқа негізделген -
TreeSet . Диаграммамызды толтырайық:
pollFirstpollLast
Жинақтардың ішінде иерархияны - гермиттерді сұрыптау қалады. Бір қарағанда шетте тұрған -
java.util.Map.
Карталар
Карталар - бұл деректер кілт арқылы сақталатын деректер құрылымы. Мысалы, кілт ID немесе қала codeы болуы мүмкін. Дәл осы кілт арқылы деректер іздеуге болады. Бір қызығы, карталар бөлек көрсетіледі. Әзірлеушілердің айтуынша («
Java Collections API Design FAQ » бөлімін қараңыз), кілттер-мәнді салыстыру жинақ емес. Ал карталарды жылдамырақ кілттер жинағы, мәндер жинағы, кілт-мән жұптарының жинағы ретінде қарастыруға болады. Бұл өте қызықты жануар. Карталар қандай әдістерді ұсынады? Java API интерфейсін қарастырайық
java.util.Map . Өйткені Карталар жинақтар болмағандықтан (олар Жинақтардан мұраланбайды), оларда
contains. Және бұл логикалық. Карта кілттер мен мәндерден тұрады. Осы әдістердің қайсысын тексеру керек
containsжәне қалай шатастырмау керек? Сондықтан интерфейстің
Mapекі түрлі нұсқасы бар:
containsKey(кілт бар) және
containsValue(мәні бар). Оны пайдалану
keySetкілттер жинағын алуға мүмкіндік береді (бірдей
Set). Ал әдісті қолдана отырып,
valuesкартадағы мәндер жинағын алуға болады. Картадағы кілттер бірегей, бұл деректер құрылымымен ерекшеленеді
Set. Мәндерді қайталауға болады, бұл коллекция деректер құрылымымен ерекшеленеді. Сонымен қатар, әдісті пайдалана отырып,
entrySetкілт-мән жұптарының жиынтығын алуға болады. Карточкалардың қандай іске асырылуы бар екенін егжей-тегжейлі талдаулардан оқи аласыз:
HashMapМен сондай-ақ ненің өте ұқсас екенін көргім келеді
HashSetжәне
TreeMap.
TreeSetОлардың тіпті ұқсас интерфейстері бар:
NavigableSetжәне
NavigableMap,
SortedSetжәне
SortedMap. Сонымен, біздің соңғы картамыз келесідей болады:
SetБіз жинақта ішкі қолданатын қызықты фактімен аяқтай аламыз
Map, мұнда қосылған мәндер кілттер болып табылады және мән барлық жерде бірдей. Бұл қызықты, өйткені бұл
Mapколлекция емес және қайтарылады
Set, ол жинақ болып табылады, бірақ іс жүзінде ретінде жүзеге асырылады
Map. Сәл сюрреалист, бірақ солай болды)
Қорытынды
Жақсы жаңалық - бұл шолуды аяқтайды. Жаман жаңалық - бұл өте шолу мақаласы. Әрбір жинақтың әрбір орындалуы жеке мақалаға лайық, сонымен қатар біздің көзімізден жасырылған әрбір алгоритм үшін. Бірақ бұл шолудың мақсаты - олардың не екенін және интерфейстер арасындағы байланыстардың қандай екенін есте сақтау. Ойланып оқығаннан кейін сіз жинақтардың сызбасын жадыңыздан сыза аласыз деп үміттенемін.
Әдеттегідей, кейбір сілтемелер:
#Вячеслав
GO TO FULL VERSION