Алар интервьюда эмнени сурашы мүмкүн: Javaдагы маалымат структуралары. 2 бөлүк

1-БӨЛҮМ Азыр биз ар бир Java иштеп чыгуучусу бorши керек болгон база жөнүндө сөз болуп жатат. Баары башталат ошол классикалык бorм жөнүндө. Бүгүн мен ар кандай интервьюнун негизги темаларынын бирине токтолгум келет - Javaдагы маалымат структуралары . Ошентип, бадалдын айланасында ургандын ордуна, баштайлы. Маектешүү учурунда сизге ушул тема боюнча берorши мүмкүн болгон суроолордун тизмесинин уландысын көрүңүз.

6. Тизме жөнүндө айтып бериңиз

Тизме – тизме деп аталган an objectтердин иреттелген структурасын билдирген интерфейс. Бул түзүмдүн "куулугу" Тизмедеги элементтерди индекс, башкача айтканда, Тизменин ички идентификатору боюнча киргизүүгө, өзгөртүүгө же жок кылууга болот . Башка сөз менен айтканда, индекс: "тизменин башынан канча элемент бар" дегенди билдирет. Биринчи Тизме элементинде индекс 0, экинчисинде индекс 1 жана башкалар бар. Ошентип, бешинчи элемент тизменин башынан төрт элемент алыс. Жогоруда айтылгандай, тизмеге элементтердин кошулуу тартиби маанилүү. Мына ошондуктан маалымат структурасы тизме деп аталат . Биз индекс боюнча элементтер менен иштөөгө багытталган ушул структурага уникалдуу методдорду тизмектеп жатабыз:

• алуу - элементти көрсөтүлгөн позицияга кайтарат (индекс мааниси боюнча),
• алып салуу - элементти көрсөтүлгөн позицияда жок кылат,
• set - көрсөтүлгөн позициядагы элементти методдо көрсөтүлгөн элемент менен алмаштырат.

Негизги ишке ашыруулар ArrayList жана LinkedList болуп саналат . Биз алар жөнүндө бир аздан кийин көбүрөөк сүйлөшөбүз. Вектор жиптен коопсуз болгон тизме, андыктан бул класстагы ар бир ыкма синхрондоштурулган. Бирок эсиңизде болсун, эгер сиз тизмедеги кээ бир аракеттерди камсыз кылууну кааласаңыз, анда сиз бүтүндөй операциялар ырааттуулугун синхронизациялайсыз. Жана жеке операцияларды синхрондоштуруу коопсузураак жана бир топ жайыраак. Албетте, Vector да кулпуга муктаж болбосо да, үстүнкү кулпуга ээ. Ошондуктан, бул класс азыр эскирген деп эсептелет жана колдонулbyte. Айтмакчы: ArrayList Векторго окшош , бирок кулпулоону колдонбойт, ошондуктан ал бардык жерде колдонулат. Стек - бул Вектор классынын бир демейки конструктору жана Vector классынын бардык методдору, ошондой эле өзүнүн бир нече методдору бар подкласс (алар жөнүндө кийинчерээк сүйлөшөбүз). Мисал катары, сиз процессти documentтер менен папкалардын топтому катары элестете аласыз. Сиз бир папканы стектин жогору жагына жайгаштырасыз жана бул папкаларды өйдөдөн баштап тескери тартипте гана ала аласыз. Чынында, бул LIFO тибиндеги механизм , башкача айтканда, Last In First Out , акыркы келген биринчи кетет. Стек өзүнүн ыкмаларын ишке ашырат:

• push - өткөн элементти стектин башына кошот;
• peek - стектин башында турган элементти кайтарат;
• pop - ошондой эле стектин башында турган элементти кайтарат, бирок аны жок кылат;
• empty - стектин бош экенин текшерет - чын же туура эмес - жалган ;
• издөө - берилген элемент үчүн стек издейт. Эгерде элемент табылса, анын стектин жогору жагына карата катар номери кайтарылат. Эгерде элемент табылбаса, анда -1 мааниси кайтарылат.

Учурда Stack субклассы анын жөнөкөйлүгүнөн жана ийкемсиздигинен улам колдонулbyte, бирок, ошентсе да, сиз ага туш болушуңуз мүмкүн. Мисалы, сиз кандайдыр бир катаны алганыңызда жана консолдо бул тууралуу билдирүүлөрдүн топтомун көрөсүз. Стек жана кезек жөнүндө кененирээк бул макаладан окуй аласыз .

7. Карта жөнүндө айтып бериңиз

Жогоруда айтылгандай, Карта интерфейстердин жана аларды ишке ашыруунун өзүнчө структурасы бар жыйнак. Бул өзүнчө, анткени бул жерде баалуулуктар бирден эмес, "ачкыч-баа" жупта сакталат. Негизги карта ыкмалары :

• put(K ачкычы, V мааниси) - картага элемент кошуу;
• get(Object key) - ачкыч боюнча маанини издөө;
• containKey(Object key) — бул ачкычтын бар экендигин Картаны текшерет;
• containValue(Object value) - бул маанинин бар экендигин Картаны текшерет;
• remove(Object key) - анын ачкычы менен маанини алып салуу.

Көрүнүп тургандай, көпчүлүк операциялар ачкычты колдонуу менен иштейт. Эреже катары, өзгөрүлгүс an objectтер ачкыч катары тандалат . Бул an objectтин типтүү мисалы - String . Негизги картаны ишке ашыруу :

1. HashMap - баалуулуктарды туш келди тартипте сактоо үчүн иштелип чыккан, бирок картанын элементтерин тез издөөгө мүмкүндүк берет. null ачкыч сөзүн колдонуу менен ачкычты көрсөтүүгө мүмкүндүк берет , бирок бир жолудан ашык эмес, анткени бирдей баскычтар менен жуптар бири-биринин үстүнө жазылган. Негизги шарт - ачкычтардын уникалдуулугу: баалуулуктар кайталанышы мүмкүн (бир нече нөлдүк маанилер болушу мүмкүн).
2. LinkedHashMap - HashMapтын аналогу , ал баалуулуктарды кошулган тартипте сактайт. Демек, LinkedList сыяктуу , анын баш аты бар - кош байланышкан тизменин башчысы. инициализацияланганда, ал өзүн көрсөтөт.

   LinkedHashMap дагы accessOrder'ге ээ , ал итератор колдонулганда элементтерге кантип жетүүнү көрсөтөт. accessOrder жалган болсо , кирүү элементтер киргизилген тартипте аткарылат. Эгер чын болсо, элементтер акыркы кирилген тартипте болот (акыркы кирген элемент аягында жайгаштырылат).

3. TreeMap - бул элементтерди негизги маанилер боюнча сорттоочу карта . TreeSet менен окшош , бирок негизги баалуулуктарга негизделген жуптар үчүн. TreeMap сорттоо эрежелерин коюу үчүн , баскычтар Comparable интерфейсин ишке ашыруусу керек . Болбосо, ачкычка багытталган компаратор болушу керек ( TreeMap конструкторунда көрсөтүлгөн ), TreeSet - ичинде TreeMap an objectиси менен ишке ашырылган, анда бардык сыйкырлар болот.

   TreeMap'те кызыл-кара дарактарды колдонуу менен сорттоо жөнүндө кененирээк TreeMap өзгөчөлүктөрү жөнүндө макаладан окуй аласыз .

4. Hashtable HashMapга окшош , бирок нөлдөрдү ачкыч же маани катары сактоого жол бербейт . Ал көп жиптүү көз караштан кылдат синхрондоштуруу, бул өз кезегинде ал көп жиптүү көз караштан коопсуз экенин билдирет. Бирок бул ишке ашыруу эскирген жана жай, ошондуктан азыр аздыр-көптүр жаңы долбоорлордо Hashtable көрө албайсыз .

8. ArrayList vs LinkedList. Кайсынысын колдонуу артык?

Бул суроо, балким, маалымат структураларында эң популярдуу жана аны менен бирге кээ бир тузактарды камтыйт. Ага жооп берүүдөн мурун, келгиле, бул маалымат структуралары жөнүндө көбүрөөк билели. ArrayList List интерфейсин ишке ашырат жана зарылчылыкка жараша кеңейтилген ички массивде иштейт. Ички массив толугу менен толтурулганда жана жаңы элементти киргизүү керек болгондо, (oldSize * 1.5) +1 өлчөмү менен жаңы массив түзүлөт. Андан кийин, эски массивдеги бардык маалыматтар жаңы + жаңы элементке көчүрүлөт, ал эми эскиси таштанды жыйноочу тарабынан жок кылынат . Add методу элементти массивдин акыркы бош уячасына кошот. Башкача айтканда, бизде 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 бир эле учурда эки интерфейсти ишке ашырат - List жана Queue , ошондуктан эки маалымат структурасына тең мүнөздүү касиеттерге жана ыкмаларга ээ. Тизмеден ал индекс боюнча элементке мүмкүнчүлүк алды, Кезектен - "баштын" жана "куйруктун" болушу. Ички, ал эки эселенген тизмени билдирген маалымат структурасы катары ишке ашырылат. Башкача айтканда, ар бир элементтин "куйругу" жана "башын" кошпогондо, кийинки жана мурункуга шилтемеси бар.

• 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) , ал эми жок кылуунун өзү эч нерсе талап кылbyte, анткени ал коңшу an objectтердин көрсөткүчүн гана өзгөртөт (алар бири-бирине кайрыла башташат). Эгерде элемент башында же аягында болсо, анда кайра - O(1) ;
• add(int index, Object obj) жана set(int index, Object obj) - методдор (int index) алуу үчүн бирдей убакыт татаалдыгына ээ болот , анткени көп убакыт элементти издөөгө жумшалат. Демек, тизменин ортосу үчүн - O(n/4) , башталышы үчүн - O(1).

LinkedList менен иштөө тууралуу көбүрөөк маалымат бул макалада баяндалат . Мунун баарын tableда карап көрөлү: Сиз, балким, буга чейин эле түшүнгөн, бул суроого так жооп берүү мүмкүн эмес. Анткени, ар кандай кырдаалдарда алар ар кандай ылдамдыкта иштешет. Ошондуктан, сизге ушундай суроо берилгенде, бул тизме эмнеге басым жасалаарын жана кайсы операциялар көп жасалаарын дароо сурашыңыз керек. Ушундан баштап, жооп бериңиз, бирок эмне үчүн мындай болгонун түшүндүрүп бериңиз. Салыштыруубузду жыйынтыктайлы: ArrayList:

• эң көп операция элементти издөө, элементтин үстүнө жазуу болсо, эң жакшы тандоо;
• Эң начар тандоо, эгерде операция башында-ортодо кыстаруу жана жок кылуу болсо, анткени оң жактагы элементтердин жылдыруу операциялары ишке ашат.

LinkedList:

• эң жакшы тандоо, эгерде биздин тез-тез операция башталышынын ортосуна киргизүү жана жок кылуу болсо;
• эң кеңири таралган операция издөө болсо, эң начар тандоо.

9. Элементтер HashMapта кантип сакталат?

HashMap коллекциясы ички массив Node[] tableсын камтыйт , анын клеткалары чака деп да аталат . Түйүн төмөнкүлөрдү камтыйт:

• ачкыч - ачкычка шилтеме,
• баалуулук - мааниге шилтеме,
• хэш - хэш мааниси,
• кийинки - кийинки түйүнгө шилтеме .

Таблица[] массивинин бир уячасында кийинки Түйүн элементине шилтемеси бар Түйүн an objectисине шилтеме болушу мүмкүн жана ал башкасына шилтеме болушу мүмкүн жана башкалар... Натыйжада, бул Түйүн элементтери кийинкиге шилтемеси бар элементтер менен жалгыз байланышкан тизме . Бул учурда, бир чынжырдын элементтеринин хэш мааниси бирдей. Кыскача четтөөдөн кийин, элементтердин HashMapта кантип сакталаарын карап көрөлү :

1. Ачкыч null үчүн текшерилет . Эгерде ал null болсо, анда ачкыч [0] tableда сакталат , анткени null үчүн хэш codeу дайыма 0 болот.
2. Эгерде ачкыч null болбосо , анда негизги an objectтин hashcode() ыкмасы деп аталат , ал өзүнүн хэш codeун кайтарат. Бул хэш-code Node an objectи сактала турган массив уячасын аныктоо үчүн колдонулат.
3. Андан кийин, бул хэшcode хэшcodeду эсептеген ички hash() методуна жайгаштырылат , бирок tableнын [] массивинин өлчөмүндө .
4. Андан кийин, хэш маанисине жараша Түйүн table[] массивиндеги белгилүү бир уячага жайгаштырылат .
5. Эгерде учурдагы Түйүн элементин сактоо үчүн колдонулган table[] уячасы бош болбосо, бирок кандайдыр бир элементи бар болсо, анда Түйүндүн элементтери акыркы элементке жеткенге чейин кийинки мааниде кайталанат. Башкача айтканда, кийинки талаа null болгон .

   Бул издөө учурунда корголгон Node an objectинин ачкычы изделип жаткандардын ачкычтары менен салыштырылат:

   • эгерде дал келүү табылса, издөө аяктайт, ал эми жаңы Түйүн дал келген Түйүндүн үстүнөн жазат (анын гана маани талаасы кайра жазылат );
   • эч кандай ачкыч дал келүү табылбаса, анда жаңы Түйүн бул тизмедеги акыркы болуп калат, ал эми мурунку ага кийинки шилтеме болот.

Суроо көбүнчө интервью учурунда келип чыгат: чыр-чатак деген эмне ? Таблица[] массивинин клеткасы бир эле элементти эмес, эки же андан көп чынжырды сактаган жагдай кагылышуу деп аталат . Кадимки учурларда, бир tableда[] бир гана элемент сакталган уячада, HashMap элементтерине жетүү туруктуу O(1) убакыт татаалдыгына ээ болот . Бирок каалаган элементи бар уячада элементтердин тизмеги ( кагылышуу ), анда O(n) болот , анткени бул учурда убакыт иргелип жаткан элементтердин санына түз пропорционалдуу.

10. Итератор жөнүндө түшүндүргүлө

Жогорудагы Жыйнак иерархиясын картага түшүрүү диаграммасында Коллекция интерфейси бүт иерархия башталган жерде болгон, бирок иш жүзүндө андай эмес. Коллекция Iterator<E> интерфейсин ишке ашырган an objectти кайтарган iterator() ыкмасы менен интерфейстен мураска алат . Iterator интерфейси төмөнкүдөй көрүнөт:

public interface Iterator <E>{

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

next() - бул ыкманы чакыруу менен кийинки элементти ала аласыз. hasNext() - кийинки элементтин бар же жок экендигин жана коллекциянын аягына жеткендигин билүүгө мүмкүндүк берет. Жана дагы эле элементтер бар болгондо, hasNext() true кайтарып берет . Адатта, hasNext() кийинки() методунан мурун чакырылат , анткени next() коллекциянын аягына жеткенде NoSuchElementException ыргытат . remove() - Кийинкиге() акыркы чалуу аркылуу алынган элементти жок кылат . Итератордун максаты - элементтерди кайталоо. Мисалы:

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());
}

Чынында, ар бир цикл итератордун жардамы менен капоттун астында ишке ашырылат. Бул тууралуу кененирээк бул жерден окуй аласыз . List итератордун өзүнүн versionсын камсыз кылат, бирок муздак жана татаалыраак - ListIterator . Бул интерфейс Итераторду кеңейтет жана кошумча ыкмалары бар:

• hasPrevious эгерде коллекцияда мурунку элемент бар болсо, чындыкты кайтарат, болбосо false;
• мурунку учурдагы элементти кайтарып, мурункуга өтөт; эгерде жок болсо, анда NoSuchElementException ыргытылат;
• add өткөн an objectти кийинки() ге кийинки чакыруу менен кайтарыла турган элементтин алдына киргизет ;
• set учурдагы элементке өткөн an objectке шилтеме берет;
• nextIndex кийинки элементтин индексин кайтарат. Эгерде мындай нерсе жок болсо, анда тизменин өлчөмү кайтарылат;
• previousIndex мурунку элементтин индексин кайтарат. Эгерде жок болсо, анда -1 саны кайтарылат.

Ооба, бүгүн мен үчүн баары ушул. Бул макаланы окугандан кийин, сиз өзүңүздүн эң сонун кыялыңызга - иштеп чыгуучу болууга дагы да жакындайсыз деп ишенем.