Жолдун башталышы
Бүгүн мен “ Java Collections Framework ” сыяктуу кызыктуу тема же жөнөкөй сөз менен айтканда коллекциялар жөнүндө сүйлөшкүм келет . Коддун ишинин көбү маалыматтарды тигил же бул формада иштетүү. Колдонуучулардын тизмесин алуу, даректердин тизмесин алуу ж.б. Кандайдыр бир жол менен аларды сорттоп, издөө жүргүзүңүз, салыштырыңыз. Ошондуктан коллекцияларды билүү негизги көндүм болуп эсептелет. Ошон үчүн бул тууралуу айткым келет. Кошумчалай кетсек, Java иштеп чыгуучуларынын маектериндеги эң кеңири таралган суроолордун бири бул жыйнактар. Мисалы, "жыйнактардын иерархиясын тартыңыз." Онлайн компилятор биздин жолубузга жардам берет. Мисалы, сиз " Tutorialspoint
Online Java Compiler " же
Repl.it колдоно аласыз. Ар кандай маалымат структуралары менен таанышуунун жолу кадимки өзгөрмөлөрдөн (Variables) башталат. Oracle веб-сайтында ар кандай темалар "жолдор" же трассалар катары көрсөтүлөт. Ошентип, Java менен таанышуунун жолу "
Из: Java тorн үйрөнүү: Мазмуну " деп аталат. Ал эми тилдин негиздери (б.а. Тил негиздери) Variables менен башталат. Ошондуктан, жөнөкөй code жазалы:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Бул бардык нерседе жакшы, бирок биз бул code бир өзгөрмө үчүн гана жакшы жана сулуу экенин түшүнөбүз. Алардын бир нечеси болсо, эмне кылуу керек? Массивдер бир типтеги маалыматтарды сактоо үчүн ойлоп табылган. Ошол эле Oracle изинде массивдерге арналган өзүнчө бөлүм бар.
Бул бөлүм: " Массивдер " деп аталат . Массивдер менен иштөө да абдан жөнөкөй:
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, бирок бул издөө сорттолгон массивде гана иштейт (сорттолбогон массив үчүн натыйжа аныкталбаган же жөн эле күтүүсүз). Башкача айтканда, издөө ар бир жолу сорттоого милдеттендирет. Жок кылуу да жөн гана маанини тазалайт. Ошондуктан, биз дагы эле массивде канча маалымат бар экенин билбейбиз, массивде канча клетка бар экенин гана билебиз. Массивдер жөнүндө бorмиңизди жаңылоо үчүн:
Жана Java тorнин өнүгүшүнүн натыйжасында Java Collections Framework JDK 1.2де пайда болду, ал жөнүндө биз бүгүн сүйлөшөбүз.
Коллекция
Эң башынан баштап чыгымдоону баштаңыз. Эмне үчүн жыйнактар? Термин өзү "Тип теориясы" жана "Абстракттуу маалымат түрлөрү" сыяктуу нерселерден келип чыккан. Бирок, эгер сиз кандайдыр бир жогорку нерселерди карабасаңыз, анда бизде бир нече нерселер болгондо, биз аларды "заттардын жыйындысы" деп атай алабыз. Буюмдарды чогулткандар. Жалпысынан чогултуу деген сөздүн өзү лат тorнен келип чыккан. коллекция "жыйноо, жыйноо." Башкача айтканда, коллекция бир нерсенин жыйындысы, кээ бир элементтер үчүн контейнер. Ошентип, биз элементтердин жыйындысы бар. Аны менен эмне кылгыбыз келет:
Көрүнүп тургандай, биз логикалык нерселерди каалайбыз. Ошондой эле биз бир нече коллекциялар менен бир нерсе кылгыбыз келиши мүмкүн экенин түшүнөбүз:
Демек, Java иштеп чыгуучулары бардык коллекциялар үчүн бул жалпы жүрүм-турумду сүрөттөө үчүн
java.util.Collection интерфейсин жазышкан . Коллекция интерфейси бардык коллекциялар келип чыккан жер. Коллекция - бул идея, бул бардык коллекциялар өзүн кандай алып жүрүшү керектиги жөнүндө идея. Демек, «Жыйнак» термини интерфейс катары туюнтулган. Албетте, интерфейс ишке ашырууну талап кылат. Интерфейс
java.util.Collectionабстракттуу класска ээ
AbstractCollection, башкача айтканда, башка ишке ашыруулар үчүн скелетти билдирген кээ бир "абстрактуу жыйнак" бар (JavaDocта класстын үстүндө жазылгандай
java.util.AbstractCollection). Коллекциялар жөнүндө сөз кыла турган болсок, келгиле, артка кайрылып, аларды кайталагыбыз келет. Бул элементтерди бир-бирден кайталагыбыз келет дегенди билдирет. Бул абдан маанилүү түшүнүк. Демек, интерфейстен
Collectionмураска алынган
Iterable. Бул абдан маанилүү, анткени ... биринчиден, бардык Iterable анын мазмунуна негизделген Iterator кайтара алгыдай болушу керек. Экинчиден, Iterable болгон нерселердин бардыгы циклдерде колдонулушу мүмкүн
for-each-loop. Итератордун жардамы менен, , ,
AbstractCollectionсыяктуу ыкмалар ишке ашырылат . Ал эми жыйнактарды түшүнүүгө жол эң кеңири таралган маалымат структураларынын бири менен башталат - тизме, б.а. .
containstoArrayremoveList
Тизмелер
Ошентип, тизмелер коллекциялардын иерархиясында маанилүү орунду ээлейт:
Көрүнүп тургандай, тизмелер
java.util.List интерфейсин ишке ашырат . Тизмелер бизде кандайдыр бир ырааттуулукта биринин артынан бири тизилген элементтердин жыйындысы бар экенин билдирет. Ар бир элементтин индекси бар (массивдегидей). Адатта, тизме бирдей мааниге ээ элементтерге ээ болууга мүмкүндүк берет. Жогоруда айтылгандай,
Listал элементтин индекси жөнүндө билет. Бул ( ) элементти индекс боюнча алууга
getже белгилүү бир индекске (
set) маани коюуга мүмкүндүк берет. Чогултуу ыкмалары
add,
addAll,
removeаларды аткаруу үчүн индексти көрсөтүүгө мүмкүндүк берет. Кошумчалай кетсек, y
Listитератордун өзүнүн versionсына ээ
ListIterator. Бул итератор элементтин индекси жөнүндө билет, ошондуктан ал алдыга гана эмес, артка дагы кайталай алат. Ал тургай, коллекциянын белгилүү бир жеринен түзүлүшү мүмкүн. Бардык ишке ашыруулардын арасында эң көп колдонулган экиси бар:
ArrayListжана
LinkedList. Биринчиден,
ArrayListбул (
List) массивге негизделген тизме (
Array).
Бул элементтерге "кокустукка" жетүүгө мүмкүндүк берет . Кокус жетүү – бул керектүү индекси бар элементти тапканга чейин бардык элементтерди кайталоонун ордуна, дароо эле индекс боюнча элементти алуу мүмкүнчүлүгү. Бул жетишүүгө мүмкүндүк берет негиз катары массив болуп саналат. Тескерисинче,
LinkedListбул шилтемеленген тизме. Шилтемеленген тизмедеги ар бир жазуу формада көрсөтүлөт
Entry, анда маалыматтардын өзү сакталат, ошондой эле кийинки (кийинки) жана мурунку (мурунку) шилтемелер
Entry. Ошентип,
LinkedList"Кезектүү мүмкүндүк
" ишке ашырат . 5-элементти табуу үчүн биринчи элементтен акыркысына өтүшүбүз керек экендиги түшүнүктүү, анткени биздин бешинчи элементке түздөн-түз жетүү мүмкүнчүлүгүбүз жок. Биз ага 4-элементтен гана кире алабыз. Алардын концепциясындагы айырма төмөндө келтирилген:
Жумушта, сиз түшүнгөндөй, айырмачылык да бар. Мисалы, элементтерди кошуу. Элементтер
LinkedListчынжырдагы шилтемелер сыяктуу эле туташып турат. Бирок
ArrayListал элементтерди массивде сактайт. Ал эми массив, биз билгендей, анын өлчөмүн өзгөртө алbyte. Анан кантип иштейт
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(акыркы кирген, биринчи чыккан) структурасы болгон кызыктуу структура. Англис тorнен которулган стек - бул стек (мисалы, китептер стек сыяктуу). Стек кошумча ыкмаларды ишке ашырат:
peek(кара, карап),
pop(түрт),
push(түрт). Метод
peekкарап деп которулат (мисалы,
баштыктын ичине көз салуу “
баштыктын ичине кароо ”, ал эми
ачкычтын тешигинен көз салуу “ ачкыч тешигинен көз салуу ” деп которулат ). Бул ыкма стектин "жогорку жагын" кароого мүмкүндүк берет, б.а. акыркы элементти стектен чыгарбастан (б.а. алып салбастан) алыңыз. Метод
pushжаңы элементти стекке түртөт (кошот) жана аны кайтарат, ал эми элемент ыкмасы
popтүртөт (чыгарат) жана алынып салынганын кайтарат. Үч учурда тең (мисалы, карап чыгуу, поп жана түртүү) биз акыркы элемент менен гана иштейбиз (б.а. "стектин үстү"). Бул стек структурасынын негизги өзгөчөлүгү болуп саналат. Айтмакчы, "Программисттин карьерасы" (Cracking Coding Interview) китебинде сүрөттөлгөн стектерди түшүнүү үчүн кызыктуу тапшырма бар, анда "стек" структурасын (LIFO) колдонуу менен "кезекти" ишке ашыруу керек болгон кызыктуу тапшырма бар. түзүмү (FIFO). Бул төмөнкүдөй болушу керек:
Бул тапшырманын анализин бул жерден тапса болот: "
Стектерди колдонуу менен кезекти ишке ашыруу - The Queue ADT ("Implement Queue using Stacks" LeetCode боюнча) ". Ошентип, биз жаңы маалымат түзүмүнө - кезекке акырындык менен өтөбүз.
Кезек
Кезек – бул бизге жашоодон тааныш структура. Дүкөндөргө, дарыгерлерге кезектер. Ким биринчи келсе (Биринчи кирген) кезектен биринчи чыгат (Биринчи чыгып).
Java тorнде кезек java.util.Queue интерфейси менен көрсөтүлөт . Кезектин Javadoc айтымында, кезек төмөнкү ыкмаларды кошот:
Көрүнүп тургандай, буйрутма ыкмалары бар (аларды аткарбоо өзгөчө жагдайлар менен коштолот) жана суроо-талап ыкмалары бар (аларды аткарууга жөндөмсүздүк каталарга алып келбейт). Ошондой эле элементти алып салбай туруп алууга болот (пик же элемент). Кезек интерфейсинин пайдалуу мураскери да бар -
Deque . Бул "эки тараптуу кезек" деп аталат. Башкача айтканда, мындай кезек бул структураны башынан да, аягында да колдонууга мүмкүндүк берет. Документте "Deques LIFO (Last-In-First-Out) стектери катары да колдонулушу мүмкүн. Бул интерфейс эски Stack классына караганда колдонулушу керек.", башкача айтканда, Deque ишке ашыруунун ордуна колдонуу сунушталат деп айтылат. Стек. Javadoc Deque интерфейси кандай ыкмаларды сүрөттөгөнүн көрсөтөт:
Келгиле, кандай ишке ашыруулар бар экенин карап көрөлү. Жана биз кызыктуу фактыны көрөбүз - LinkedList кезек лагерине кирди) Башкача айтканда, LinkedList
List, жана экөөнү тең ишке ашырат
Deque. Бирок, мисалы, "кезектер гана" бар
PriorityQueue. Аны көп эстебейт, бирок бекер. Биринчиден, бул кезекте "салыштырылбаган an objectтерди" колдоно албайсыз, б.а. же Comparator көрсөтүлүшү керек же бардык an objectтер салыштырылышы керек. Экинчиден, "бул ишке ашыруу O(log(n)) кезекке коюу жана кезексиз коюу ыкмаларын камсыз кылат". Логарифмдик татаалдыктын бир себеби бар. Үймөктүн негизинде PriorityQueue ишке ашырылды. Javadoc мындай дейт: "Приоритеттүү кезек балансталган экorк үймөк катары көрсөтүлгөн". Бул үчүн сактагычтын өзү кадимки массив. Керек болгондо өсөт. Үймөк кичине болгондо 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- предметтердин баштыкчасы сыяктуу, ал жерде an objectтер кандай жайгашканы жана кандай тартипте жатканы белгисиз.
Java тorнде мындай топтом 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 . Анткени Карталар коллекция болбогондуктан (алар Коллекциялардан мурастаbyte), аларда
contains. Жана бул логикалуу. Карта ачкычтардан жана баалуулуктардан турат. Бул ыкманын кайсынысын текшерүү керек
containsжана кантип чаташтырбоо керек? Демек, интерфейстин
Mapэки башка versionсы бар:
containsKey(ачкычты камтыйт) жана
containsValue(бааны камтыйт). Аны колдонуу
keySetсизге баскычтардын топтомун алууга мүмкүндүк берет (ошол эле
Set). Жана ыкманы колдонуу менен
valuesбиз картада баалуулуктардын жыйнагын ала алабыз. Картадагы ачкычтар уникалдуу болуп саналат, аны маалымат структурасы баса белгилейт
Set. Маанилер кайталанышы мүмкүн, бул Коллекциянын маалымат түзүмү тарабынан баса белгиленет. Мындан тышкары, ыкманы колдонуу менен
entrySetбиз ачкыч-нарк жуптарынын топтомун ала алабыз. Карталарды кандай ишке ашыруулар бар экендиги жөнүндө кененирээк талдоодон окуй аласыз:
Мен дагы эмнеге
HashMapабдан окшош экенин көргүм келет
HashSetжана
TreeMap.
TreeSetАлардын да окшош интерфейстери бар:
NavigableSetжана
NavigableMap,
SortedSetжана
SortedMap. Ошентип, биздин акыркы карта мындай болот:
Биз коллекциянын
Setички колдоно турганы кызыктуу факты менен аяктайбыз
Map, мында кошумча баалуулуктар ачкыч болуп саналат, ал эми баалуулук бардык жерде бирдей. Бул кызыктуу, анткени ал
Mapколлекция эмес жана кайтарып берет
Set, ал коллекция болуп саналат, бирок чындыгында катары ишке ашырылат
Map. Бир аз сюрреалдуу, бирок ушундай болуп калды)
Корутунду
Жакшы кабар бул карап чыгуу ушул жерде аяктайт. Жаман кабар - бул абдан сын макала. Ар бир жыйнактын ар бир аткарылышы өзүнчө макалага татыктуу, ошондой эле биздин көзүбүздөн жашырылган ар бир алгоритм үчүн. Бирок бул карап чыгуунун максаты - алар эмне экенин жана интерфейстердин ортосунда кандай байланыштар бар экенин эстеп калуу. Ойлонуп окуп чыккандан кийин сиз жыйнактардын схемасын эсиңизден тарта аласыз деп ишенем.
Ооба, адаттагыдай эле, кээ бир шилтемелер:
#Вячеслав
GO TO FULL VERSION