Сұхбат кезінде олар не сұрауы мүмкін: Java-дағы деректер құрылымдары. 2-бөлім

1-БӨЛІМ Қазір біз әрбір Java әзірлеушісі білуі керек база туралы айтамыз. Мұның бәрі басталатын классикалық білім туралы. Бүгін мен кез келген сұхбаттың негізгі тақырыптарының біріне тоқталғым келеді - Java тіліндегі деректер құрылымдары . Сонымен, бұтаның айналасында ұрып-соғудың орнына, бастайық. Сұхбат кезінде осы тақырып бойынша сізге қойылуы мүмкін сұрақтар тізімінің жалғасын қараңыз.

6. Тізім туралы айтып беріңіз

Тізім - бұл тізім деп аталатын an objectілердің реттелген құрылымын көрсететін интерфейс. Бұл құрылымның «қулығы» Тізімдегі элементтерді индекс бойынша, яғни Тізімнің ішкі идентификаторы арқылы енгізуге, өзгертуге немесе жоюға болады . Басқаша айтқанда, индекс: «тізімнің басынан қанша элемент бар» дегенді білдіреді. Бірінші Тізім элементінде 0 индексі, екіншісінде 1 индексі бар және т.б. Сонымен, бесінші элемент тізімнің басынан төрт элемент алыс. Жоғарыда айтылғандай, тізімге элементтерді қосу реті маңызды. Сондықтан деректер құрылымы тізім деп аталады . Біз элементтермен индекс бойынша жұмыс істеуге бағытталған осы құрылымға тән әдістерді тізімдейміз:

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

Негізгі іске асырулар ArrayList және LinkedList болып табылады . Олар туралы сәл кейінірек толығырақ айтатын боламыз. Вектор - бұл ағынға қауіпсіз тізім, сондықтан осы сыныптағы әрбір әдіс синхрондалады. Бірақ кейбір тізім әрекеттерін қауіпсіздендіруді қаласаңыз, сіз бүкіл әрекеттер тізбегін синхрондайтыныңызды есте сақтаңыз. Жеке операцияларды синхрондау қауіпсіз әрі әлдеқайда баяуырақ. Әрине, Векторда құлыптау қажет болмаса да, үстіңгі құлыптау мүмкіндігі бар. Сондықтан бұл класс қазір ескірген болып саналады және қолданылмайды. Айтпақшы: ArrayList Vector -ге ұқсас , бірақ құлыптауды пайдаланбайды, сондықтан ол барлық жерде қолданылады. Стек - бір әдепкі конструкторы және Vector класының барлық әдістері, сонымен қатар өзінің бірнеше әдістері бар Vector класының ішкі сыныбы ( олар туралы кейінірек айтатын боламыз). Мысал ретінде сіз процесті құжаттары бар қалталар дестесі ретінде елестете аласыз. Сіз бір қалтаны стектің жоғарғы жағына орналастырасыз және бұл қалталарды тек жоғарыдан бастап кері ретпен алуға болады. Шындығында, бұл LIFO типті механизм , яғни « Соңғы кіріс бірінші шығады» , соңғысы бірінші болып кетеді. Стек өзінің әдістерін жүзеге асырады:

• push - өткізілген элементті стектің жоғарғы жағына қосады;
• peek - стектің жоғарғы жағында орналасқан элементті қайтарады;
• pop - сонымен қатар стектің жоғарғы жағында орналасқан элементті қайтарады, бірақ оны жояды;
• empty - стектің бос екенін тексереді - ақиқат немесе жоқ - жалған ;
• іздеу – берілген элементті стектен іздейді. Егер элемент табылса, оның стектің жоғарғы жағына қатысты реттік нөмірі қайтарылады. Егер элемент табылмаса, -1 мәні қайтарылады.

Қазіргі уақытта Stack қосалқы сыныбы өзінің қарапайымдылығы мен икемсіздігіне байланысты іс жүзінде пайдаланылмайды, бірақ соған қарамастан, сіз оны кездестіруіңіз мүмкін. Мысалы, сіз қандай да бір қатені алған кезде және консольде ол туралы хабарлар дестесін көресіз. Стек және кезек туралы толығырақ осы мақаладан оқи аласыз .

7. Карта туралы айтып беріңіз

Жоғарыда айтылғандай, Карта интерфейстердің және олардың іске асырылуының жеке құрылымы бар жинақ болып табылады. Бұл бөлек, өйткені мұнда мәндер бір уақытта емес, «кілт-мән» жұбында сақталады. Картаның негізгі әдістері :

• put(K пернесі, V мәні) – Картаға элемент қосу;
• get(Object key) – кілт бойынша мәнді іздеу;
• containKey(Object key) — Картада осы кілттің бар-жоғын тексереді;
• containValue(Object value) - бұл мәннің бар-жоғын Картаны тексереді;
• Remove(Object key) – мәнді оның кілті арқылы жою.

Көріп отырғаныңыздай, операциялардың көпшілігі кілт арқылы жұмыс істейді. Әдетте, кілттер ретінде өзгермейтін нысандар таңдалады . Бұл нысанның типтік мысалы String болып табылады . Негізгі картаны іске асыру :

1. HashMap - мәндерді кездейсоқ ретпен сақтауға арналған, бірақ карта элементтерін жылдам іздеуге мүмкіндік береді. null кілт сөзі арқылы кілтті көрсетуге мүмкіндік береді , бірақ бір реттен көп емес, өйткені пернелері бірдей жұптар бірінің үстіне бірі жазылады. Негізгі шарт - пернелердің бірегейлігі: мәндерді қайталауға болады (бірнеше нөлдік мәндер болуы мүмкін).
2. LinkedHashMap - мәндерді қосылған ретпен сақтайтын HashMap аналогы . Тиісінше, LinkedList сияқты оның тақырыбы бар - қосарланған тізімнің басы. Баптандыру кезінде ол өзін көрсетеді.

   LinkedHashMap- те итератор пайдаланылған кезде элементтерге қалай қол жеткізілетінін көрсететін accessOrder бар . AccessOrder қате болса , қатынас элементтер енгізілген ретпен орындалады. Егер шын болса, элементтер соңғы қол жеткізілген тәртіпте болады (соңғы қол жеткізілген элемент соңында орналастырылады).

3. TreeMap — элементтерді негізгі мәндер бойынша сұрыптайтын Карта . TreeSet сияқты , бірақ негізгі мәндерге негізделген жұптар үшін. TreeMap сұрыптау ережелерін орнату үшін пернелер Салыстырмалы интерфейсті орындауы керек . Әйтпесе, кілтке бағытталған компаратор ( TreeMap конструкторында көрсетілген ), TreeSet болуы керек - ішіндегі TreeMap нысанымен жүзеге асырылады, онда шын мәнінде барлық сиқырлар орын алады.

   TreeMap қолданбасында қызыл-қара ағаштарды пайдаланып сұрыптау туралы толығырақ TreeMap мүмкіндіктері туралы мақаладан оқи аласыз .

4. Hashtable HashMap түріне ұқсас , бірақ нөлдерді кілттер немесе мәндер ретінде сақтауға мүмкіндік бермейді . Ол көп ағынды көзқарас тұрғысынан мұқият синхрондалады, бұл өз кезегінде оның көп ағынды көзқарас тұрғысынан қауіпсіз екенін білдіреді. Бірақ бұл іске асыру ескірген және баяу, сондықтан қазір сіз Hashtable-ті жаңа жобаларда көрмейсіз.

8. ArrayList және LinkedList. Қайсысын қолданған дұрыс?

Бұл сұрақ деректер құрылымдарында ең танымал болуы мүмкін және онымен бірге кейбір тұзақтар бар. Оған жауап бермес бұрын, осы деректер құрылымдары туралы көбірек білейік. ArrayList List интерфейсін жүзеге асырады және қажетінше кеңейтілетін ішкі массивте жұмыс істейді. Ішкі массив толығымен толтырылғанда және жаңа элементті енгізу қажет болғанда, өлшемі (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), соңынан - O(1);
• add(int index, Object obj) - жоюға ұқсас жағдай: ортасына қосу кезінде оң жақтағы бір ұяшықтағы элементтерді алға жылжыту керек, сондықтан уақыт O(n/2) болады. Әрине, басынан - O(n), соңынан - O(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) , ал жоюдың өзі іс жүзінде ештеңе алмайды, өйткені ол тек көрші нысандардың көрсеткішін өзгертеді (олар бір-біріне сілтеме жасай бастайды). Егер элемент басында немесе соңында болса, онда қайтадан - O(1) ;
• add(int index, Object obj) және set(int index, Object obj) - әдістердің алу(int index) уақыт күрделілігі бірдей болады , өйткені уақыттың көп бөлігі элементті іздеуге жұмсалады. Сондықтан тізімнің ортасы үшін - O(n/4) , басы үшін - O(1).

LinkedList- пен жұмыс істеу туралы қосымша ақпарат осы мақалада сипатталған . Мұның бәрін кестеде қарастырайық: Сіз түсінген боларсыз, бұл сұраққа біржақты жауап беру мүмкін емес. Өйткені, әртүрлі жағдайларда олар әртүрлі жылдамдықта жұмыс істейді. Сондықтан, сізге осындай сұрақ қойылғанда, бұл тізімнің не нәрсеге назар аударылатынын және қандай операциялардың жиі орындалатынын дереу сұрау керек. Осыдан бастап, жауап беріңіз, бірақ неге бұлай екенін түсіндіріңіз. Салыстыруымызды қорытындылайық: ArrayList:

• ең жиі орындалатын операция элементті іздеу, элементті қайта жазу болса, ең жақсы таңдау;
• ең нашар таңдау, егер операция басында-ортасында кірістіру және жою болса, өйткені оң жақта элементтердің ауысу операциялары орын алады.

Сілтемелер тізімі:

• ең жақсы таңдау, егер біздің жиі операциямыз басынан ортасына кірістіру және жою болса;
• ең көп таралған операция іздеу болса, ең нашар таңдау.

9. HashMap-те элементтер қалай сақталады?

HashMap жинағында ұяшықтары шелек деп аталатын ішкі жиым Node[] кестесі бар . Түйін мыналарды қамтиды:

• кілт - кілтке сілтеме,
• мән — мәнге сілтеме,
• хэш - хэш мәні,
• келесі - келесі түйінге сілтеме .

[] кесте массивінің бір ұяшығында келесі Түйін элементіне сілтемесі бар Түйін нысанына сілтеме болуы мүмкін және оның басқасына сілтеме болуы мүмкін және т.б.... Нәтижесінде, бұл Түйін элементтері келесіге сілтемесі бар элементтері бар жеке байланыстырылған тізім . Бұл жағдайда бір тізбектің элементтерінің хэш мәні бірдей болады. Қысқаша шолудан кейін элементтердің HashMap ішінде қалай сақталатынын қарастырайық :

1. Кілт нөлге тексеріледі . Егер ол null болса, онда кілт кестенің [0] ұяшығында сақталады, себебі null үшін хэш codeы әрқашан 0 болады.
2. Егер кілт null болмаса , онда негізгі нысанның хэшcode() әдісі деп аталады , ол өзінің хэш codeын қайтарады. Бұл хэш codeы Түйін нысаны сақталатын жиым ұяшығын анықтау үшін пайдаланылады.
3. Әрі қарай, бұл хэшcode хэшcodeты есептейтін ішкі hash() әдісіне орналастырылады , бірақ кесте [] массивінің өлшемі ішінде .
4. Әрі қарай, хэш мәніне байланысты Түйін кестенің [] массивіндегі белгілі бір ұяшыққа орналастырылады .
5. Ағымдағы Түйін элементін сақтау үшін пайдаланылатын кесте [] ұяшығы бос болмаса, бірақ әлдеқашан элементі бар болса, Түйін элементтері соңғы элементке жеткенше келесі мәнде қайталанады. Яғни, келесі өрісі null болатын өріс .

   Бұл іздеу кезінде қорғалған Түйін нысанының кілті ізделетіндердің кілттерімен салыстырылады:

   • егер сәйкестік табылса, іздеу аяқталады және жаңа Түйін сәйкестік табылған Түйінді қайта жазады (тек оның мән өрісі қайта жазылады );
   • егер кілт сәйкестіктері табылмаса, жаңа Түйін осы тізімдегі соңғы болады, ал алдыңғысының оған келесі сілтемесі болады.

Сұхбат кезінде жиі сұрақ туындайды: жанжал дегеніміз не ? Кесте[] массивінің ұяшығы бір элементті емес, екі немесе одан да көп тізбекті сақтайтын жағдай соқтығыс деп аталады . Бір кесте[] ұяшығында тек бір элемент сақталған қалыпты жағдайларда , HashMap элементтеріне қатынасу тұрақты O(1) уақыт күрделілігіне ие болады . Бірақ қажет элементі бар ұяшықта элементтер тізбегі болса ( соқтығыс ), онда O(n) , өйткені бұл жағдайда уақыт сұрыпталатын элементтер санына тура пропорционал болады.

10. Итератор туралы түсіндіріңіз

Жоғарыдағы Жинақ иерархиясын салыстыру диаграммасында Жинақ интерфейсі бүкіл иерархияның басталған жері болды, бірақ іс жүзінде олай емес. Коллекция Iterator<E> интерфейсін жүзеге асыратын нысанды қайтаратын iterator() әдісі бар интерфейстен мұра алады . Итератор интерфейсі келесідей көрінеді:

public interface Iterator <E>{

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

next() - осы әдісті шақыру арқылы келесі элементті алуға болады. hasNext() – келесі элементтің бар-жоғын және жинақтың соңына жеткен-жетпегенін білуге ​​мүмкіндік береді. Әлі де элементтер болған кезде hasNext() true мәнін қайтарады . Әдетте, hasNext() келесі() әдісінің алдында шақырылады , өйткені 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());
}

Шындығында, for-her циклі итератор арқылы сорғыштың астында жүзеге асырылады. Бұл туралы толығырақ мына жерден оқи аласыз . List итератордың өз нұсқасын ұсынады, бірақ салқын және күрделірек - ListIterator . Бұл интерфейс Итераторды кеңейтеді және қосымша әдістерге ие:

• жинақта алдыңғы элемент болса, hasPrevious шын мәнін қайтарады, әйтпесе false;
• алдыңғы ағымдағы элементті қайтарады және алдыңғысына ауысады; егер жоқ болса, онда NoSuchElementException жіберіледі;
• add өткен нысанды next() келесі шақыруымен қайтарылатын элементтің алдында кірістіреді ;
• жиын ағымдағы элементке берілген нысанға сілтеме тағайындайды;
• nextIndex келесі элементтің индексін қайтарады. Егер мұндай нәрсе болмаса, онда тізімнің өлшемі қайтарылады;
• previousIndex алдыңғы элементтің индексін қайтарады. Егер жоқ болса, онда -1 саны қайтарылады.

Міне, бүгін мен үшін бәрі осы. Осы мақаланы оқығаннан кейін сіз өзіңіздің арманыңыз - әзірлеуші ​​болуыңызға жақындайсыз деп үміттенемін.