Онҳо дар мусоҳиба чӣ мепурсанд: Сохторҳои маълумот дар Java. Қисми 2

ҚИСМИ 1 Ҳоло мо дар бораи базае гап мезанем, ки ҳар як таҳиягари Java бояд донад. Дар бораи он дониши классикӣ, ки ҳамааш аз он оғоз мешавад. Имрӯз ман мехоҳам ба яке аз мавзӯъҳои асосии ҳама гуна мусоҳиба - сохторҳои додаҳо дар Java дахл кунам . Пас, ба ҷои он ки дар атрофи бутта задан, биёед оғоз кунем. Идомаи рӯйхати саволҳоеро, ки ҳангоми мусоҳиба ба шумо дар ин мавзӯъ дода мешаванд, хонед.

6. Дар бораи Рӯйхат ба мо бигӯед

Рӯйхат интерфейсест, ки сохтори тартибёфтаи an objectҳоро ифода мекунад, ки онро рӯйхат меноманд. "Ҳилла"-и ин сохтор дар он аст, ки унсурҳои дар Рӯйхат мавҷудбуда метавонанд аз рӯи индекс, яъне идентификатори дохorи Рӯйхат дохил карда шаванд, тағир дода ё нест карда шаванд . Ба ибораи дигар, индекс маънои: "чанд элемент аз аввали рӯйхат аст." Унсури якуми Рӯйхат дорои индекси 0, дуюмаш индекси 1 ва ғайра мебошад. Ҳамин тавр, унсури панҷум аз аввали рӯйхат чор унсур дур аст. Тавре ки дар боло зикр гардид, тартиби илова кардани ашё ба рӯйхат муҳим аст. Барои ҳамин сохтори додаҳо рӯйхат номида мешавад . Мо усулҳои хоси ин сохторро номбар мекунем, ки барои кор бо элементҳо аз рӯи индекс нигаронида шудаанд:

• get - элементро дар мавқеи муқарраршуда бармегардонад (аз рӯи арзиши индекс),
• хориҷ кардан - элементро дар мавқеи муқарраршуда хориҷ мекунад,
• маҷмӯа - элементро дар мавқеъи муайяншуда бо унсури дар метод нишондодашуда иваз мекунад.

Амалисозии асосӣ ArrayList ва LinkedList мебошанд . Мо каме дертар дар бораи онҳо бештар сӯҳбат хоҳем кард. Вектор рӯйхатест, ки барои ришта бехатар аст, бинобар ин ҳар як усул дар ин синф ҳамоҳанг карда мешавад. Аммо дар хотир доред, ки агар шумо хоҳед, ки баъзе амалҳои рӯйхатро таъмин кунед, шумо пайдарпайии тамоми амалиётҳоро ҳамоҳанг хоҳед кард. Ва ҳамоҳангсозии амалиёти инфиродӣ ҳам камтар бехатар ва хеле сусттар аст. Албатта, Вектор инчунин дорои болои қулф аст, ҳатто агар ба шумо қулф лозим набошад. Аз ин рӯ, ин синф ҳоло кӯҳна ҳисобида мешавад ва истифода намешавад. Дар омади гап: ArrayList ба Vector монанд аст , аммо қулфкуниро истифода намебарад, аз ин рӯ дар ҳама ҷо истифода мешавад. Стек як зерсинфи синфи Vector мебошад , ки як созандаи пешфарз ва тамоми усулҳои синфи Vector , илова бар он чанде аз худи он (мо дар бораи онҳо баъдтар сӯҳбат хоҳем кард). Ҳамчун мисол, шумо метавонед ин равандро ҳамчун як папкаи ҷузвдонҳо бо ҳуҷҷатҳо тасаввур кунед. Шумо як ҷузвдонро дар болои стек ҷойгир мекунед ва шумо метавонед ин ҷузвдонҳоро танҳо бо тартиби баръакс, аз боло сар карда гиред. Воқеан, ин як механизми навъи LIFO аст , яъне Last In First Out , охирин касе меояд, ки аввалин мешавад. Стек усулҳои худро амалӣ мекунад:

• push - элементи гузаштаро ба болои стек илова мекунад;
• peek - элементеро, ки дар болои стек ҷойгир аст, бармегардонад;
• pop - инчунин элементеро, ки дар болои стек ҷойгир аст, бармегардонад, аммо онро нест мекунад;
• empty - тафтиш мекунад, ки оё холӣ будани стек - ҳақиқӣ ё не - бардурӯғ ;
• ҷустуҷӯ - стекро барои элементи додашуда ҷустуҷӯ мекунад. Агар элемент ёфт шавад, рақами пайдарпайии он нисбат ба болои стек баргардонида мешавад. Агар элемент ёфт нашавад, арзиши -1 баргардонида мешавад.

Дар айни замон, зеркласси Stack аз сабаби соддагӣ ва чандирнопазирии он воқеан истифода намешавад, аммо, бо вуҷуди ин, шумо метавонед бо он дучор шавед. Масалан, вақте ки шумо ягон хатогиро мегиред ва дар консол шумо маҷмӯи паёмҳоро дар бораи он мебинед. Шумо метавонед дар бораи стек ва навбат бештар дар ин мақола хонед .

7. Дар бораи Харита ба мо нақл кунед

Тавре ки дар боло зикр гардид, Харита маҷмӯаест, ки дорои сохтори алоҳидаи интерфейсҳо ва татбиқи онҳо мебошад. Ин алоҳида аст, зеро дар ин ҷо арзишҳо на як-як, балки дар ҷуфти "калид-арзиш" нигоҳ дошта мешаванд. Усулҳои асосии харита :

• put(К калиди, арзиши V) - илова кардани элемент ба Харита;
• get(Калиди Объект) - ҷустуҷӯи арзиш аз рӯи калид;
• containKey(Калиди Объект) — мавҷудияти ин калидро Харитаро тафтиш мекунад;
• containValue(Арзиши an object) - мавҷудияти ин арзишро Харитаро тафтиш мекунад;
• хориҷ кардан(Калиди an object) - хориҷ кардани арзиш бо калиди он.

Тавре ки шумо мебинед, аксари амалиётҳо бо истифода аз калид кор мекунанд. Чун қоида, an objectҳои тағирнопазир ҳамчун калид интихоб карда мешаванд . Намунаи маъмулии ин an object String аст . Татбиқи асосии Харитаҳо :

1. HashMap - барои нигоҳ доштани арзишҳо бо тартиби тасодуфӣ тарҳрезӣ шудааст, аммо ба шумо имкон медиҳад, ки унсурҳои харитаро зуд ҷустуҷӯ кунед. Ба шумо имкон медиҳад, ки калидро бо истифода аз калимаи калидии null муайян кунед , аммо на бештар аз як маротиба, зеро ҷуфтҳои дорои як калидҳо дар болои якдигар навишта мешаванд. Шарти асосӣ ин ягонагии калидҳо мебошад: арзишҳоро метавон такрор кард (мумкин аст, ки якчанд арзишҳои нул вуҷуд дошта бошанд).
2. LinkedHashMap як аналоги HashMap мебошад , ки арзишҳоро бо тартиби иловашуда нигоҳ медорад. Мувофиқи он, ба монанди LinkedList , он дорои сарлавҳа - сари рӯйхати дукарата алоқаманд аст. Ҳангоми оғозёбӣ, он ба худ ишора мекунад.

   LinkedHashMap инчунин дорои accessOrder мебошад , ки муайян мекунад, ки ҳангоми истифодабарии итератор ба унсурҳо чӣ гуна дастрасӣ пайдо мешавад. Агар accessOrder бардурӯғ бошад, дастрасӣ бо тартиби ворид кардани унсурҳо иҷро карда мешавад. Агар дуруст бошад, унсурҳо бо тартиби охирин дастрас хоҳанд буд (унсури охирини дастрасшуда дар охири он ҷойгир карда мешавад).

3. TreeMap харитаест , ки унсурҳоро аз рӯи арзишҳои калидӣ ҷудо мекунад. Монанд ба TreeSet , аммо барои ҷуфтҳо дар асоси арзишҳои калидӣ. Барои муқаррар кардани қоидаҳои ҷудокунии TreeMap , калидҳо бояд интерфейси муқоисашавандаро татбиқ кунанд . Дар акси ҳол, бояд Муқоисакунандаи ба Калид нигаронидашуда (оне, ки дар созандаи TreeMap муайян шудааст) мавҷуд бошад , TreeSet - бо an objectи TreeMap дар дохor он амалӣ карда мешавад, ки дар он воқеан тамоми ҷодугарӣ рӯй медиҳад.

   Шумо метавонед бештар дар бораи навъбандӣ дар TreeMap бо истифода аз дарахтони сурх-сиёҳ дар мақола дар бораи хусусиятҳои TreeMap хонед .

4. Hashtable ба HashMap монанд аст , аммо имкон намедиҳад, ки нулҳо ҳамчун калид ё арзишҳо нигоҳ дошта шаванд. Он аз нуқтаи назари бисёрсоҳавӣ бодиққат ҳамоҳанг карда мешавад, ки ин дар навбати худ маънои онро дорад, ки он аз нуқтаи назари бисёр ришта бехатар аст. Аммо ин татбиқ кӯҳна ва суст аст, аз ин рӯ ҳоло шумо Hashtable-ро дар лоиҳаҳои нав ё камтар нахоҳед дид .

8. ArrayList против LinkedList. Кадомаш барои истифода афзалтар аст?

Ин савол шояд маъмултарин дар сохторҳои додаҳо бошад ва бо худ баъзе домҳо дорад. Пеш аз он ки ба он ҷавоб диҳед, биёед дар бораи ин сохторҳои додаҳо бештар маълумот гирем. ArrayList интерфейси Рӯйхатро амалӣ мекунад ва дар массиви дохилӣ амал мекунад, ки ҳангоми зарурат васеъ карда мешавад. Вақте ки массиви дохилӣ пурра пур мешавад ва элементи нав бояд ворид карда шавад, массиви нав бо андозаи (oldSize * 1.5) +1 сохта мешавад. Пас аз ин, ҳама маълумот аз массиви кӯҳна ба элементи нав + нав нусхабардорӣ карда мешавад ва кӯҳна аз ҷониби коллектори ахлот нест карда мешавад . Усули илова элементро ба ячейкаи холии охирини массив илова мекунад. Яъне, агар мо дар он ҷо аллакай 3 элемент дошта бошем, он унсури навбатиро ба чашмаки 4-ум илова мекунад. Биёед аз иҷрои усулҳои асосӣ гузарам:

• get(int index) - гирифтани элемент дар массив аз рӯи индекс зудтарин дар O(1) аст ;
• add(Object obj) - агар дар массиви дохилӣ барои элементи нав фазои кофӣ мавҷуд бошад, пас бо воридкунии муқаррарии O(1) вақт сарф мешавад , зеро илова ба ячейкаи охирин нигаронида шудааст.

  Агар ба мо лозим ояд, ки массиви нав созем ва мундариҷаро ба он нусхабардорӣ кунем, он гоҳ вақти мо ба миқдори элементҳои массиви O(n) мутаносиб хоҳад буд ;

• remove(int index) - ҳангоми хориҷ кардани элемент, масалан, аз мобайн, мо вақти O(n/2) мегирем, зеро ба мо лозим меояд, ки элементҳоро ба тарафи рости он як ячейка қафо гузаронем. Мутаносибан, агар аз аввали рӯйхат ҳазф карда шавад, пас O(n), аз охири рӯйхат - О(1);
• add(int index, Object obj) - вазъияте, ки ба ҳазф монанд аст: ҳангоми илова кардан ба мобайн, ба мо лозим меояд, ки элементҳои дар тарафи рост бударо ба пеш ҳаракат кунем, аз ин рӯ вақт O(n/2) аст. Албатта, аз аввал - О(н), аз охир - О(1);
• set(int index, Object obj) - дар ин ҷо вазъият дигар аст, зеро ба шумо танҳо лозим аст, ки элементи дилхоҳро пайдо кунед ва бе ҳаракати боқимонда ба болои он нависед, бинобар ин O(1).

Дар ин мақола дар бораи ArrayList бештар хонед . LinkedList якбора ду интерфейсро амалӣ мекунад - Рӯйхат ва Навбат ва аз ин рӯ дорои хосиятҳо ва усулҳои хоси ҳарду сохтори додаҳо мебошад. Аз Рӯйхат ӯ ба унсур аз рӯи индекс дастрасӣ пайдо кард, аз Queue - мавҷудияти "сар" ва "дум". Дар дохor он, он ҳамчун сохтори додаҳо амалӣ карда мешавад, ки рӯйхати дукарата алоқамандро намояндагӣ мекунад. Яъне ҳар як унсур ба ҷузъҳои дигар ва қаблӣ пайванде дорад, ба истиснои “дум” ва “сар”.

• get(int index) - ҳангоми ҷустуҷӯи элементе, ки дар мобайни рӯйхат ҷойгир аст, он ба ҷустуҷӯи ҳама элементҳо бо тартиб то пайдо шудани элементи дилхоҳ оғоз мекунад. Мантиқан, ҷустуҷӯ бояд O(n/2) -ро гирад , аммо LinkedList низ дум дорад, аз ин рӯ ҷустуҷӯ ҳамзамон аз ҳарду ҷониб сурат мегирад. Мутаносибан, вақт ба O(n/4) кам карда мешавад .

  Агар элемент ба аввали рӯйхат ё охири рӯйхат наздик бошад, пас вақт O(1) мешавад ;

• add(Object obj) - ҳангоми илова кардани элементи нав, элементи "дум" ба унсури навбатии иловашуда пайванде хоҳад дошт ва элементи нав ба ин элементи қаблӣ истинод гирифта, "дум"-и нав мешавад. Мувофиқи он вақт O(1) мешавад ;
• remove(int index) - мантиқи монанд ба усули get(int index) . Барои нест кардани элемент аз миёнаи рӯйхат, шумо бояд аввал онро пайдо кунед. Ин боз O(n/4) аст , дар ҳоле ки худи ҳазф воқеан ҳеҷ чизро намегирад, зеро он танҳо нишоннамои an objectҳои ҳамсояро иваз мекунад (онҳо ба ҳамдигар муроҷиат мекунанд). Агар элемент дар аввал ё дар охир бошад, пас боз - O(1) ;
• add(int index, Object obj) ва set(int index, Object obj) - усулҳо мураккабии вақт барои гирифтани (int index) якхела хоҳанд буд , зеро бештари вақт барои ҷустуҷӯи элемент сарф мешавад. Аз ин рӯ, барои миёнаи рӯйхат - O(n/4) , барои ибтидо - O(1).

Маълумоти бештар дар бораи кор бо LinkedList дар ин мақола тасвир шудааст . Биёед ҳамаи инро дар ҷадвал дида бароем: Тавре ки шумо аллакай фаҳмидед, ба ин савол ҷавоб додан ғайриимкон аст. Охир, дар вазъиятхои гуногун онхо бо суръати гуногун кор мекунанд. Аз ин рӯ, вақте ки ба шумо чунин савол дода мешавад, шумо бояд фавран бипурсед, ки ин рӯйхат ба чӣ нигаронида шудааст ва кадом амалиётҳо бештар иҷро карда мешаванд. Аз ин сар карда, ҷавоб диҳед, аммо бо шарҳи он ки чаро ин тавр аст. Биёед муқоисаи худро ҷамъбаст кунем: ArrayList:

• интихоби беҳтарин, агар амалиёти маъмултарин ҷустуҷӯи як элемент, аз нав навиштани элемент бошад;
• интихоби бадтарин, агар амалиёт воридкунӣ ва несткунӣ дар ибтидо-миёна бошад, зеро амалиёти ивазкунии элементҳо дар тарафи рост сурат мегирад.

Рӯйхати пайвандшуда:

• беҳтарин интихоб, агар амалиёти зуд-зуд мо ворид кардан ва нест кардан дар ибтидо-миёна бошад;
• интихоби бадтарин, агар амалиёти маъмултарин ҷустуҷӯ бошад.

9. Элементҳо дар HashMap чӣ гуна нигоҳ дошта мешаванд?

Маҷмӯаи HashMap дорои массиви дохorи Node[] ҷадвал аст , ки чашмакҳои онро сатил низ меноманд . Гиреҳ дорои:

• калид - пайванд ба калид,
• арзиш — истинод ба арзиш,
• hash - арзиши hash,
• оянда - пайванд ба гиреҳи навбатӣ .

Як чашмаки массив[] метавонад истинодро ба an objectи гиреҳ бо истинод ба унсури навбатии гиреҳ дошта бошад ва он метавонад ба дигараш пайванд дошта бошад ва ғайра... Дар натиҷа, ин унсурҳои гиреҳ метавонанд рӯйхати ягонаи алоқаманд бо унсурҳо бо истинод ба оянда. Дар ин ҳолат, арзиши хэш- и элементҳои як занҷир якхела аст. Пас аз баррасии кӯтоҳ, биёед бубинем, ки чӣ гуна элементҳо дар HashMap нигоҳ дошта мешаванд :

1. Калид барои null санҷида мешавад . Агар он null бошад, он гоҳ калид дар чашмаки ҷадвал [0] нигоҳ дошта мешавад , зеро codeи хэш барои null ҳамеша 0 аст.
2. Агар калид null набошад, он гоҳ усули hashcode() an objectи калидӣ номида мешавад , ки он рамзи хеши худро бармегардонад. Ин рамзи хэш барои муайян кардани ячейкаи массив, ки дар он an objectи Node нигоҳ дошта мешавад, истифода мешавад.
3. Баъдан, ин хэшcode дар усули hash() дохor ҷойгир карда мешавад , ки он codeро ҳисоб мекунад, аммо дар доираи андозаи массиви [] .
4. Минбаъд, вобаста ба арзиши ҳаш, Node дар ячейкаи мушаххаси массиви ҷадвал ҷойгир карда мешавад .
5. Агар чашмаки ҷадвал[] , ки барои нигоҳ доштани унсури ҷории гиреҳ истифода шудааст , холӣ набошад, вале аллакай дорои баъзе элементҳо бошад, он гоҳ унсурҳои гиреҳ то расидан ба элементи охирин дар болои арзиши навбатӣ такрор карда мешаванд. Яъне майдони навбатии он нул аст .

   Ҳангоми ин ҷустуҷӯ калиди an objectи Node ҳифзшуда бо калидҳои ҷустуҷӯшаванда муқоиса карда мешавад:

   • агар мувофиқат пайдо шавад, ҷустуҷӯ ба итмом мерасад ва гиреҳи нав гиреҳеро , ки дар он мувофиқат ёфт шудааст, барҳам менависад (танҳо майдони арзиши он аз нав навишта мешавад );
   • агар ягон мувофиқати калидӣ пайдо нашавад, гиреҳи нав дар ин рӯйхат охирин мешавад ва қаблӣ пайванди навбатӣ ба он хоҳад дошт.

Савол аксар вақт ҳангоми мусоҳиба ба миён меояд: муноқиша чист ? Ҳолате, ки дар ячейкаи массиви ҷадвал на як элемент, балки занҷири ду ё зиёда аз он нигоҳ дошта мешавад, бархӯрд номида мешавад . Дар ҳолатҳои муқаррарӣ, ки танҳо як элемент дар як чашмаки ҷадвал[] нигоҳ дошта мешавад , дастрасӣ ба унсурҳои HashMap мураккабии доимии O(1) -ро дорад . Аммо вақте ки чашмаки дорои элементи дилхоҳ занҷири элементҳоро дар бар мегирад ( бархӯрд ), пас O(n) , зеро дар ин ҳолат вақт ба шумораи элементҳои мураттабшаванда мутаносиб аст.

10. Дар бораи итератор фаҳмонед

Дар диаграммаи харитасозии иерархияи Коллексия , интерфейси Коллексия дар он ҷое буд, ки тамоми иерархия оғоз ёфт, аммо дар амал ин тавр нест. Коллексия аз интерфейс бо усули iterator() мерос мегирад , ки an objectеро бармегардонад, ки интерфейси Iterator<E> -ро амалӣ мекунад . Интерфейси Iterator чунин менамояд:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - бо даъвати ин усул, шумо метавонед элементи навбатӣ гиред. hasNext () - ба шумо имкон медиҳад, ки фаҳмед, ки оё унсури навбатӣ вуҷуд дорад ва оё ба охири ҷамъоварӣ расидааст. Ва ҳангоме ки элементҳо мавҷуданд, hasNext() true -ро бармегардонад . Одатан, hasNext() пеш аз усули next() даъват мешавад , зеро next() вақте ки он ба охири коллексия мерасад, NoSuchElementException- ро мепартояд . remove() - Элементеро, ки бо занги охирин ба next() гирифта шуда буд, хориҷ мекунад . Мақсади Итератор такрор кардани элементҳост. Барои намуна:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

Дар асл, барои ҳар як ҳалқа дар зери сарпӯш бо истифода аз итератор амалӣ карда мешавад. Шумо метавонед бештар дар бораи ин дар ин ҷо бихонед . Рӯйхат versionи шахсии итераторро пешниҳод мекунад, аммо versionи сардтар ва мураккабтар - ListIterator . Ин интерфейс Iterator-ро васеъ мекунад ва дорои усулҳои иловагӣ мебошад:

• hasPrevious, агар дар коллексия унсури қаблӣ мавҷуд бошад, ҳақиқиро бармегардонад, дар акси ҳол false;
• қаблӣ элементи ҷорӣро бармегардонад ва ба пешина мегузарад; агар вуҷуд надошта бошад, пас NoSuchElementException партофта мешавад;
• add an objectи гузаштаро пеш аз элементе, ки бо занги навбатӣ ба next() бармегардонад, дохил мекунад ;
• set ба элементи ҷорӣ истинод ба an objectи гузаштаро таъин мекунад;
• nextIndex индекси элементи навбатиро бармегардонад. Агар чунин чизе набошад, он гоҳ андозаи рӯйхат баргардонида мешавад;
• previousIndex индекси элементи қаблиро бармегардонад. Агар вуҷуд надошта бошад, рақами -1 баргардонида мешавад.

Бале, ин ҳама барои ман имрӯз аст. Умедворам, ки пас аз хондани ин мақола шумо ба орзуи гаронбаҳои худ - таҳиягар шудан боз ҳам наздиктар мешавед.