Müsahibədə nə soruşa bilərlər: Java-da məlumat strukturları. 1-ci hissə

Salam! Necə baxsanız da, texniki giriş müsahibəsindən uğurla keçmədən inkişaf etdirici ola bilməzsiniz. Java ilə əlaqəli bir çox texnologiya var və hər şeyi öyrənmək mümkün deyil. Bir qayda olaraq, müsahibələr zamanı konkret bir şey soruşulur ki, onlar layihə üçün vacib olan bəzi çərçivələrdə yaxşı təcrübəsi olan bir tərtibatçı axtarırlar. Əgər belədirsə, siz bu çərçivədən tam sürətlə sürüləcəksiniz, heç bir şübhəniz yoxdur. Ancaq indi hər bir Java tərtibatçısının bilməli olduğu baza haqqında danışırıq. Hər şeyin başladığı klassik bilik haqqında. Bu gün mən istənilən müsahibənin əsas mövzularından birinə - Java-da məlumat strukturlarına toxunmaq istərdim . Beləliklə, kolun ətrafında döyülmək əvəzinə, başlayaq. Müsahibə zamanı bu mövzu ilə bağlı sizə verilə biləcək sualların siyahısını tapın.

1. Məlumat strukturları haqqında bir az məlumat verin

Məlumat strukturu müəyyən bir şəkildə strukturlaşdırılmış məlumatları ehtiva edən məlumat anbarıdır. Bu strukturlar müəyyən əməliyyatların səmərəli icrası üçün nəzərdə tutulmuşdur. Məlumat strukturlarının tipik nümunələri bunlardır:

• massivlər,
• yığınlar,
• növbələr,
• əlaqəli siyahılar,
• qrafiklər,
• ağaclar,
• prefiks ağacları,
• hash cədvəli.

Onlar haqqında daha çox məlumatı burada və burada tapa bilərsiniz . Verilənlər proqramın əsas komponentidir və strukturlar bu verilənləri konkret, aydın strukturlaşdırılmış formada saxlamağa imkan verir. Tətbiqiniz nə edirsə etsin, bu aspekt həmişə orada olacaq: əgər bu veb mağazadırsa, məhsullar haqqında məlumat, sosial şəbəkədirsə, istifadəçilər və fayllar haqqında məlumatlar və s.

2. Massivlər haqqında nə bilirsiniz?

Massiv, sayı əvvəlcədən müəyyən edilmiş eyni tipli dəyərləri saxlamaq üçün bir konteynerdir. Sətir dəyərlərinə malik massiv yaratmağa nümunə:

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

Massiv yaradarkən onun bütün elementləri üçün yaddaş ayrılır: ilkin olaraq elementlər üçün nə qədər çox xana göstərilsə, bir o qədər yaddaş ayrılacaq. Müəyyən sayda xana olan boş massiv yaradılarsa, massivin bütün elementlərinə standart dəyərlər təyin ediləcək. Misal üçün:

int[] arr = new int[10];

Beləliklə, boolean tipli elementləri olan massiv üçün ilkin ( default ) dəyərlər yanlış olacaq , rəqəmli dəyərləri olan massivlər üçün - 0, char tipli elementlər üçün - \u0000 . Sinif tipli massiv (obyektlər) üçün - null (boş sətirlər deyil - “” lakin xüsusi olaraq null ). Yəni yuxarıdakı misalda arr massivinin bütün dəyərləri birbaşa təyin olunana qədər 0 olacaqdır. Kolleksiyalardan fərqli olaraq massivlər dinamik deyil. Müəyyən ölçülü massiv elan edildikdən sonra ölçüsün özü dəyişdirilə bilməz. Massivə yeni element əlavə etmək üçün yeni daha böyük massiv yaratmalı və köhnədən bütün elementləri ona köçürməlisiniz (ArrayList belə işləyir). Hər kəsin bilmədiyi və çox yaxşı tutula biləcəyiniz bir məqam var. Java-da iki növ dəyişən var - sadə növlər və tam hüquqlu obyektlərə istinadlar . Bunlardan hansı massivdir? Məsələn, burada:

int[] arr = new int[10];

Görünür, hər şey sadədir - bunlar 10 int elementidir . Beləliklə, bunun sadə bir növ olduğunu söyləyə bilərik? Necə olursa olsun. Java-da massivlər obyektlərdir, dinamik şəkildə yaradılır və Object tipli dəyişənlərə təyin edilə bilər. Object sinfinin bütün metodları massivdə çağırıla bilər. Beləliklə, hətta yaza bilərik:

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

Konsola çıxararkən belə bir şey əldə edə bilərsiniz: Java-da massivlərin xüsusiyyətləri haqqında Java Array haqqında bu məqalədə ətraflı oxuyun . Biliklərinizi möhkəmləndirmək üçün bu kolleksiyadan bir neçə problemi həll edə bilərsiniz .

3. Kolleksiyaların iyerarxiyasını izah edin

Kolleksiyalar məlumatlarla işləyərkən çevikliyə ehtiyac duyduğunuz hallarda istifadə olunur. Kolleksiyalar element əlavə edə, elementi silə və bir çox başqa əməliyyatları yerinə yetirə bilər. Java-da çoxlu müxtəlif tətbiqlər var və biz sadəcə mövcud vəziyyət üçün düzgün kolleksiya seçməliyik. Tipik olaraq, Kolleksiya interfeysini qeyd edərkən sizdən onun bəzi tətbiqlərini və Xəritə ilə əlaqəsini sadalamağınız xahiş olunur . Yaxşı, gəlin öyrənək. Beləliklə, Kolleksiya və Xəritə məlumat strukturları üçün iki fərqli iyerarxiyadır. Kolleksiya iyerarxiyası nəyə bənzəyir : Kolleksiya interfeysi üç əsas məlumat strukturunun yarandığı əsas metodların siyahısı ilə əsas yuxarı keçiddir - Set , List , Queue . Set<T> hər bir obyektin unikal olduğu obyektlər toplusunu təmsil edən interfeysdir. List<T> siyahı adlanan obyektlərin ardıcıl ardıcıllığını təmsil edən interfeysdir. Queue<T> növbə kimi təşkil edilən strukturlara cavabdeh olan interfeysdir (elementlərin ardıcıl saxlanması). Daha əvvəl qeyd edildiyi kimi, Xəritə ayrıca iyerarxiyadır: Map<K, V> elementlərin açar-dəyər cütləri kimi yerləşdiyi lüğəti təmsil edən interfeysdir. Bundan əlavə, bütün düymələr (K) Map obyekti daxilində unikaldır . Bu cür kolleksiya, açarı - obyektin unikal identifikatorunu bildiyimiz təqdirdə elementi tapmağı asanlaşdırır.

4. Set haqqında nə bilirsiniz?

Daha əvvəl qeyd edildiyi kimi, bu kolleksiya bir çox unikal elementləri ehtiva edir. Başqa sözlə, eyni obyekt Java Setində bir dəfədən çox görünə bilməz. Onu da qeyd etmək istərdim ki, biz bir dəstdən elementi nömrəyə görə (indeks) çıxara bilmərik - yalnız kobud qüvvə ilə. Əhəmiyyətli olan odur ki, müxtəlif Set tətbiqləri məlumatların strukturlaşdırılmasının müxtəlif yollarına malikdir. Daha sonra konkret tətbiqləri nəzərdən keçirəcəyik. Beləliklə, Set : HashSet- in əsas tətbiqləri hash cədvəlinə əsaslanan dəstdir və bu da öz növbəsində axtarışa kömək edir. Axtarışlar və əlavələr zamanı performansı yaxşılaşdıran hash funksiyasından istifadə edir. Elementlərin sayından asılı olmayaraq, ümumiyyətlə, daxiletmə və axtarış (bəzən silinmə) sabit vaxta yaxın - O(1) ərzində yerinə yetirilir. Hash funksiyasına bir az sonra daha ətraflı baxacağıq. Onu da qeyd etmək istərdim ki, HashSet- də bütün sehrlərin baş verdiyi HashMap var . Java-da HashSet haqqında ətraflı məqalə buradadır . LinkedHashSet - bu sinif heç bir yeni metod əlavə etmədən HashSet- i genişləndirir . LinkedList kimi , bu sinif də çoxluğun elementlərinin daxil edildiyi ardıcıllıqla əlaqəli siyahısını saxlayır. Bu, verilmiş Set həyata keçirilməsində lazımi sıranı təşkil etməyə imkan verir . TreeSet sinfi elementlərin saxlanması strukturunu təşkil etmək üçün qırmızı-qara ağaca əsaslanan dəst yaradır. Başqa sözlə, verilmiş çoxluqda biz elementləri artan qaydada sıralaya bilərik. Əgər “qutu”dan bəzi standart obyektlərdən istifadə etsək, məsələn, Tam ədəd , onda tam ədədlər dəstini artan qaydada tənzimləmək üçün heç nə etməyə ehtiyacımız yoxdur:

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

System.out.println(set);

Və konsolda çıxışı alacağıq: Yəni bu dəstdə nömrələr çeşidlənmiş formada saxlanılır. TreeSet -də String elementlərindən istifadə etsək , onlar sıralanacaq, lakin əlifba sırası ilə. Yaxşı, əgər bizim bəzi standart (xüsusi) sinifimiz varsa? Bu sinfin obyektləri TreeSet-i necə strukturlaşdıracaq ? Bu Dəstə ixtiyari obyekt təyin etməyə çalışsaq :

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

Biz ClassCastException alacağıq , çünki TreeSet bu tip obyektlərin necə çeşidlənməsini bilmir. Bu halda, Müqayisə edilə bilən interfeysi və onun compareTo metodunu həyata keçirmək üçün xüsusi obyektimizə ehtiyacımız var :

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 + '\'' +
               '}';
   }
}

Diqqət etdiyiniz kimi, compareTo metodu int qaytarır :

• 1 cari (bu) obyekt böyük hesab edilərsə;
• -1 cari obyekt arqument kimi gələn obyektdən kiçik hesab edilirsə;
• obyektlər bərabərdirsə 0 (biz bundan istifadə etmirik).

Bu halda TreeSet- imiz düzgün işləyəcək və nəticəni göstərəcək: Başqa bir yol, müqayisəedici interfeysi və onun müqayisə metodunu həyata keçirən ayrıca çeşidləmə sinfi yaratmaqdır :

public class CatComparator implements Comparator {

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

Bu halda, ondan istifadə etmək üçün TreeSet konstruktoruna bu sinfin obyektini təyin etməliyik :

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

Bundan sonra TreeSet- ə daxil olan Cat sinifinin bütün obyektləri Cat Comparator sinfindən istifadə edilərək çeşidlənəcək . Bu məqalədən Java-da Comparator və Comparator haqqında daha çox məlumat əldə edə bilərsiniz .

5. Növbə haqqında bizə məlumat verin

Queue , növbə kimi təşkil edilən strukturlara cavabdeh olan interfeysdir - elementləri ardıcıl olaraq saxlayan məlumat strukturu. Məsələn, bir növbə içərisindən birinci daxil olan şəxs digərlərindən tez gələn, sonuncu isə hamıdan gec gələn şəxs olacaq. Bu üsul FİFO adlanır , yəni First in First Out . Unikal növbə metodları ilk və ya sonuncu elementlə işləməyə diqqət yetirir, məsələn:

• əlavə et və təklif et - növbənin sonuna element daxil edir,
• sil - bu növbənin başlığını alır və silir,
• peek - növbə başlığını götürür, lakin silmir.

HİSSƏ 2