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

Сәлеметсіз бе! Қалай қарасаңыз да, техникалық кіру сұхбатынан сәтті өтпей, әзірлеуші ​​бола алмайсыз. Java-ға қатысты көптеген технологиялар бар және бәрін үйрену мүмкін емес. Әдетте, сұхбат кезінде нақты бір нәрсе сұралады, егер олар жоба үшін маңызды қандай да бір шеңберде жақсы тәжірибесі бар әзірлеушіні іздесе ғана. Егер солай болса, сіз осы шеңбер арқылы толық жылдамдықпен қозғаласыз, сізде күмән жоқ. Бірақ біз қазір әрбір Java әзірлеушісі білуі керек база туралы айтып отырмыз. Мұның бәрі басталатын классикалық білім туралы. Бүгін мен кез келген сұхбаттың негізгі тақырыптарының біріне тоқталғым келеді - Java тіліндегі деректер құрылымдары . Сонымен, бұтаның айналасында ұрып-соғудың орнына, бастайық. Сұхбат кезінде осы тақырып бойынша сізге қойылуы мүмкін сұрақтар тізімін табыңыз.

1. Деректер құрылымдары туралы аздап айтып беріңіз

Деректер құрылымы - белгілі бір жолмен құрылымдалған ақпаратты қамтитын деректер қоймасы. Бұл құрылымдар белгілі бір операцияларды тиімді орындауға арналған. Деректер құрылымдарының типтік мысалдары:

• массивтер,
• стектер,
• кезек,
• байланысты тізімдер,
• графиктер,
• ағаштар,
• префикс ағаштары,
• хэш кестесі.

Олар туралы толығырақ мына жерден және мына жерден біле аласыз . Деректер бағдарламаның негізгі құрамдас бөлігі болып табылады және құрылымдар бұл деректерді нақты, анық құрылымдалған пішінде сақтауға мүмкіндік береді. Қолданбаңыз не істесе де, бұл аспект онда әрқашан болады: егер ол веб-дүкен болса, онда өнімдер туралы ақпарат сақталады, егер ол әлеуметтік желі болса, пайдаланушылар мен файлдар туралы деректер және т.б.

2. Массивтер туралы не білесіз?

Массив – саны алдын ала көрсетілген бір типті мәндерді сақтауға арналған контейнер. Жол мәндері бар массив құру мысалы:

String[] strArray = {"Java","is","the","best","language"};

Массивті құру кезінде оның барлық элементтері үшін жад бөлінеді: бастапқыда элементтерге арналған ұяшықтар неғұрлым көп болса, соғұрлым жады көбірек бөлінеді. Егер ұяшықтардың белгілі бір саны бар бос массив жасалса, онда массивтің барлық элементтеріне әдепкі мәндер тағайындалады. Мысалы:

int[] arr = new int[10];

Сонымен, логикалық түрдегі элементтері бар массив үшін бастапқы ( әдепкі ) мәндер жалған болады , сандық мәндері бар массивтер үшін - 0, char түрінің элементтері бар - \u0000 . Класс типті массив үшін (нысандар) - null (бос жолдар емес - “” бірақ арнайы null ). Яғни, жоғарыдағы мысалда arr массивінің барлық мәндері тікелей көрсетілгенше 0 болады. Жинақтардан айырмашылығы, массивтер динамикалық емес. Белгілі бір өлшемді массив жарияланғаннан кейін өлшемнің өзін өзгерту мүмкін емес. Массивке жаңа элемент қосу үшін жаңа үлкенірек массив жасап, оған ескінің барлық элементтерін көшіру керек (ArrayList осылай жұмыс істейді). Барлығы біле бермейтін және сізді жақсы ұстай алатын бір мәселе бар. Java тілінде айнымалылардың екі түрі бар – қарапайым типтер және толыққанды an objectілерге сілтемелер . Бұлардың қайсысы массивтерге жатады? Мысалы, мұнда:

int[] arr = new int[10];

Барлығы қарапайым сияқты - бұл 10 int элементтері . Сонымен, бұл қарапайым түрі деп айта аламыз ба? Қалай болса да. Java тілінде массивтер an objectілер болып табылады, олар динамикалық түрде жасалады және Object түріндегі айнымалыларға тағайындалуы мүмкін. Object класының барлық әдістерін массивте шақыруға болады. Сонымен, біз тіпті жаза аламыз:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

Консольге шығарған кезде сіз келесідей нәрсені аласыз: Java тіліндегі массивтердің мүмкіндіктері туралы толығырақ Java массиві туралы осы мақаладан оқыңыз . Білімді бекіту үшін осы жинақтағы бірнеше есептерді шығаруға болады .

3. Жинақтардың иерархиясын түсіндіріңіз

Жинақтар деректермен жұмыс істеу кезінде икемділікті қажет ететін жағдайларда пайдаланылады. Коллекциялар элементті қоса алады, элементті жоя алады және көптеген басқа әрекеттерді орындай алады. Java-да көптеген әртүрлі іске асырулар бар және бізге ағымдағы жағдайға дұрыс топтаманы таңдау керек. Әдетте, Коллекция интерфейсі туралы айтқан кезде сізден оның кейбір іске асыруларын және оның Картамен байланысын тізімдеу сұралады . Кәне, анықтап көрейік. Сонымен, Жинақ және Карта деректер құрылымдары үшін екі түрлі иерархия болып табылады. Жинақ иерархиясы қалай көрінеді : Жинақ интерфейсі деректер құрылымдарының үш негізгі түрі пайда болатын негізгі әдістер тізімі бар негізгі жоғарғы сілтеме болып табылады - Орнату , Тізім , Кезек . Set<T> - бұл әрбір нысан бірегей болатын нысандар жиынын көрсететін интерфейс. List<T> - тізім деп аталатын an objectілердің реттелген тізбегін көрсететін интерфейс. Queue<T> - бұл кезек ретінде ұйымдастырылған құрылымдарға жауап беретін интерфейс (элементтерді тізбектей сақтау). Бұрын айтылғандай, Карта жеке иерархия болып табылады: Map<K, V> - элементтері кілт-мән жұбы ретінде қамтылған сөздікті көрсететін интерфейс. Сонымен қатар, барлық пернелер (K) Map нысанында бірегей болып табылады . Коллекцияның бұл түрі an objectінің бірегей идентификаторы - кілтті білсек, элементті табуды жеңілдетеді.

4. Set туралы не білесіңдер?

Жоғарыда айтылғандай, бұл жинақ көптеген бірегей элементтерді қамтиды. Басқаша айтқанда, бір нысан Java жинағында бірнеше рет пайда бола алмайды. Сондай-ақ, біз сан бойынша жиыннан (индекс) элементті шығара алмайтынымызды атап өткім келеді - тек қатаң күшпен. Ең бастысы, әртүрлі Set іске асыруларында деректерді құрылымдаудың әртүрлі тәсілдері бар. Біз нақты іске асыруды әрі қарай қарастырамыз. Сонымен, Set негізгі іске асырулары : HashSet - бұл хэш кестесіне негізделген жиын, ол өз кезегінде іздеуге көмектеседі. Іздеу және кірістіру кезінде өнімділікті жақсартатын хэш функциясын пайдаланады. Элементтердің санына қарамастан, жалпы алғанда кірістіру және іздеу (кейде жою) тұрақты уақытқа жақын - O(1) орындалады. Біз хэш функциясын сәл кейінірек толығырақ қарастырамыз. Сондай-ақ, HashSet құрамында HashMap бар екенін атап өткім келеді , мұнда барлық сиқырлар орын алады. Мұнда Java тіліндегі HashSet туралы егжей-тегжейлі мақала берілген . LinkedHashSet - бұл класс HashSet- ті жаңа әдістерді қоспай-ақ кеңейтеді. LinkedList сияқты , бұл сынып жиын элементтерінің байланыстырылған тізімін олар енгізілген ретпен сақтайды. Бұл берілген жиынды іске асыруда қажетті тәртіпті ұйымдастыруға мүмкіндік береді . TreeSet класы элементтерді сақтау құрылымын ұйымдастыру үшін қызыл-қара ағашқа негізделген жиынды жасайды. Басқаша айтқанда, берілген жиында біз элементтерді өсу ретімен сұрыптай аламыз. Егер біз «қораптағы» кейбір стандартты нысандарды пайдалансақ, мысалы, Integer , онда бүтін сандар жиынын өсу ретімен орналастыру үшін бізге ештеңе істеудің қажеті жоқ:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

Ал консольде біз нәтиже аламыз: Яғни, бұл жиынтықта сандар сұрыпталған түрде сақталады. Егер TreeSet ішінде String элементтерін пайдалансақ , олар сұрыпталады, бірақ алфавит бойынша. Егер бізде стандартты (арнайы) сынып болса ше? Осы сыныптың нысандары TreeSet құрылымын қалай жасайды ? Егер біз осы жиынға ерікті нысанды тағайындауға тырыссақ :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

Біз ClassCastException аламыз , себебі TreeSet осы түрдегі нысандарды қалай сұрыптау керектігін білмейді. Бұл жағдайда Салыстырмалы интерфейсті және оның compareTo әдісін енгізу үшін бізге теңшелетін нысан қажет :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

Байқағаныңыздай, compareTo әдісі int қайтарады :

• 1 егер ағымдағы (осы) an object үлкен деп есептелсе;
• -1 егер ағымдағы нысан аргумент ретінде келгеннен кіші деп есептелсе;
• 0, егер нысандар тең болса (бұл жағдайда біз оны қолданбаймыз).

Бұл жағдайда біздің TreeSet дұрыс жұмыс істейді және нәтижені көрсетеді: Басқа әдіс - компаратор интерфейсін және оның салыстыру әдісін жүзеге асыратын бөлек сұрыптау класын жасау :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

Бұл жағдайда оны пайдалану үшін TreeSet конструкторына осы сыныптың нысанын орнату керек :

TreeSet set = new TreeSet<>(new CatComparator());

Осыдан кейін TreeSet ішіне енгізілген Cat класының барлық нысандары Cat Comparator сыныбы арқылы сұрыпталады . Java тіліндегі Comparator және Comparable туралы осы мақаладан көбірек біле аласыз .

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

Кезек – кезек ретінде ұйымдастырылған құрылымдарға жауапты интерфейс – элементтерді дәйекті түрде сақтайтын деректер құрылымы. Мысалы, кезекте тұрған адамдардың ішінен бірінші болып басқалардан ерте келген адам кіреді, ал ең соңғысы басқалардан кеш келген адам болады. Бұл әдіс FIFO деп аталады , яғни Біріншіден бірінші шығады . Бірегей кезек әдістері бірінші немесе соңғы элементпен жұмыс істеуге бағытталған, мысалы:

• қосу және ұсыну - кезектің соңына элемент енгізеді,
• жою - осы кезектің тақырыбын шығарады және жояды,
• peek - шығарады, бірақ кезек тақырыбын жоймайды.

2-БӨЛІМ