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

HİSSƏ 1 İndi hər bir Java tərtibatçısının bilməli olduğu bazadan 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övzuda sizə verilə biləcək sualların siyahısının davamını izləyin.

6. Siyahı haqqında bizə məlumat verin

Siyahı, siyahı adlanan obyektlərin nizamlı strukturunu təmsil edən interfeysdir. Bu strukturun “hiyləsi” ondan ibarətdir ki , Siyahıya daxil olan elementlər indekslə, yəni Siyahının daxili identifikatoru ilə daxil edilə, dəyişdirilə və ya silinə bilər . Başqa sözlə, indeks: "siyahının əvvəlindən neçə element var" deməkdir. Birinci Siyahı elementinin indeksi 0, ikincinin indeksi 1 və s. Beləliklə, beşinci element siyahının əvvəlindən dörd element uzaqdadır. Yuxarıda qeyd edildiyi kimi, siyahıya maddələrin əlavə olunma ardıcıllığı vacibdir. Buna görə məlumat strukturu siyahı adlanır . Elementlərlə indekslə işləməyə yönəlmiş bu struktura xas olan metodları sadalayırıq:

• get - elementi göstərilən mövqeyə qaytarır (indeks dəyərinə görə),
• sil - elementi göstərilən mövqedən çıxarır,
• set - göstərilən mövqedəki elementi metodda göstərilən elementlə əvəz edir.

Əsas tətbiqlər ArrayList və LinkedList- dir . Onlar haqqında bir az sonra daha ətraflı danışacağıq. Vektor mövzu üçün təhlükəsiz olan siyahıdır, ona görə də bu sinifdəki hər bir metod sinxronlaşdırılır. Ancaq unutmayın ki, bəzi siyahı hərəkətlərini təmin etmək istəyirsinizsə, bütün əməliyyatlar ardıcıllığını sinxronlaşdıracaqsınız. Fərdi əməliyyatları sinxronlaşdırmaq həm daha az təhlükəsizdir, həm də daha yavaşdır. Əlbəttə ki, Vektorun kilidləmə yükü də var, hətta kilidə ehtiyacınız olmasa belə. Buna görə də bu sinif indi köhnəlmiş hesab olunur və istifadə edilmir. Yeri gəlmişkən: ArrayList Vector- ə bənzəyir , lakin kilidləmədən istifadə etmir, ona görə də hər yerdə istifadə olunur. Stack bir defolt konstruktoru və Vector sinfinin bütün üsulları , üstəlik bir neçə özünəməxsus metodu olan Vector sinfinin alt sinfidir (onlar haqqında daha sonra danışacağıq). Məsələn, prosesi sənədləri olan qovluqlar yığını kimi təsəvvür edə bilərsiniz. Siz yığının yuxarı hissəsində bir qovluq yerləşdirirsiniz və siz bu qovluqları yuxarıdan başlayaraq yalnız tərs qaydada götürə bilərsiniz. Əslində, bu, LIFO tipli mexanizmdir , yəni Last In First Out , sonuncu gələn ilk çıxandır. Stack öz üsullarını həyata keçirir:

• push - ötürülən elementi yığının yuxarı hissəsinə əlavə edir;
• peek - yığının yuxarı hissəsində olan elementi qaytarır;
• pop - həmçinin yığının yuxarı hissəsində olan elementi qaytarır, lakin onu çıxarır;
• empty - yığının boş olub olmadığını yoxlayır - doğru və ya yanlış - yalan ;
• axtarış - verilmiş element üçün yığını axtarır. Element tapılarsa, onun yığının yuxarı hissəsinə nisbətən sıra nömrəsi qaytarılır. Element tapılmazsa, -1 dəyəri qaytarılır.

Hal-hazırda, Stack alt sinifi sadəliyi və çevikliyi səbəbindən əslində istifadə edilmir, lakin buna baxmayaraq, onunla qarşılaşa bilərsiniz. Məsələn, bir səhv aldığınız zaman və konsolda bu barədə bir yığın mesaj görürsünüz. Bu məqalədə yığın və növbə haqqında daha çox oxuya bilərsiniz .

7. Xəritə haqqında bizə məlumat verin

Yuxarıda qeyd edildiyi kimi, Xəritə interfeyslərin və onların həyata keçirilməsinin ayrıca strukturuna malik kolleksiyadır. Bu ayrıdır, çünki burada dəyərlər bir-bir deyil, "açar-dəyər" cütlüyündə saxlanılır. Əsas xəritə üsulları :

• put(K düyməsi, V dəyəri) - Xəritəyə element əlavə etmək;
• get(Obyekt açarı) - açarla dəyəri axtarın;
• containKey(Obyekt açarı) — Xəritədə bu açarın mövcudluğunu yoxlayır;
• containValue(Obyekt dəyəri) - Xəritədə bu dəyərin mövcudluğunu yoxlayır;
• sil(Obyekt açarı) - dəyərin açarı ilə silinməsi.

Gördüyünüz kimi əksər əməliyyatlar açardan istifadə etməklə işləyir. Bir qayda olaraq, dəyişməz obyektlər açar kimi seçilir . Bu obyektin tipik nümunəsi Stringdir . Əsas xəritə tətbiqləri :

1. HashMap - dəyərləri təsadüfi qaydada saxlamaq üçün nəzərdə tutulmuşdur, lakin xəritə elementlərini tez bir zamanda axtarmağa imkan verir. Null açar sözündən istifadə edərək açarı təyin etməyə imkan verir , lakin bir dəfədən çox deyil, çünki eyni düymələri olan cütlər üst-üstə yazılır. Əsas şərt açarların unikallığıdır: dəyərlər təkrarlana bilər (bir neçə sıfır dəyər ola bilər).
2. LinkedHashMap, dəyərləri əlavə olunduğu ardıcıllıqla saxlayan HashMap-ın analoqudur . Müvafiq olaraq, LinkedList kimi , onun başlığı var - ikiqat əlaqəli siyahının başı. Başlandıqda, o, özünə işarə edir.

   LinkedHashMap həmçinin iterator istifadə edildikdə elementlərə necə daxil olacağını müəyyən edən accessOrder-ə malikdir . accessOrder yanlışdırsa , giriş elementlərin daxil edildiyi ardıcıllıqla həyata keçiriləcək. Əgər doğrudursa, elementlər son əldə edilmiş qaydada olacaq (sonuncu əldə edilmiş element sonunda yerləşdiriləcək).

3. TreeMap elementləri əsas dəyərlərə görə çeşidləyən Xəritədir . TreeSet -ə bənzəyir , lakin əsas dəyərlərə əsaslanan cütlər üçün. TreeMap çeşidləmə qaydalarını təyin etmək üçün düymələr Müqayisəli interfeysi həyata keçirməlidir . Əks halda, Açar yönümlü Müqayisəçi ( TreeMap konstruktorunda göstərilən ), TreeSet olmalıdır - içərisində TreeMap obyekti ilə həyata keçirilir və əslində bütün sehrlər orada baş verir.

   Qırmızı-qara ağaclardan istifadə edərək TreeMap-da çeşidləmə haqqında daha çox TreeMap-in xüsusiyyətləri haqqında məqalədə oxuya bilərsiniz .

4. Hashtable HashMap- a bənzəyir , lakin nullların açar və ya dəyər kimi saxlanmasına icazə vermir . O, çox yivli nöqteyi-nəzərdən diqqətlə sinxronlaşdırılır, bu da öz növbəsində çox yivli nöqteyi-nəzərdən təhlükəsiz olması deməkdir. Ancaq bu tətbiq köhnəlmişdir və yavaşdır, buna görə də indi az-çox yeni layihələrdə Hashtable-ı görməyəcəksiniz .

8. ArrayList və LinkedList. Hansının istifadəsinə üstünlük verilir?

Bu sual, bəlkə də məlumat strukturlarında ən populyardır və özü ilə bəzi tələlər daşıyır. Cavab verməzdən əvvəl gəlin bu məlumat strukturları haqqında daha çox öyrənək. ArrayList List interfeysini həyata keçirir və lazım olduqda genişləndirilən daxili massivdə işləyir. Daxili massiv tamamilə doldurulduqda və yeni element daxil edilməli olduqda, ölçüsü (oldSize * 1.5) +1 olan yeni massiv yaradılır. Bundan sonra köhnə massivdəki bütün məlumatlar yeni + yeni elementə kopyalanır və köhnəsi zibil toplayıcı tərəfindən silinəcəkdir . Əlavə etmə metodu massivin sonuncu boş xanasına element əlavə edir. Yəni orada artıq 3 elementimiz varsa, o, növbəti elementi 4-cü xanaya əlavə edəcək. Əsas metodların icrasına keçək:

• get(int index) - massivdəki elementi indekslə götürmək O(1) -də ən sürətlidir ;
• add(Object obj) - daxili massivdə yeni element üçün kifayət qədər yer varsa, o zaman normal daxiletmə ilə O(1) vaxt sərf olunacaq , çünki əlavə son xanaya yönəldilmişdir.

  Əgər yeni massiv yaratmalı və içindəkiləri ona köçürməli olsaq, onda bizim vaxtımız O(n) massivindəki elementlərin sayı ilə düz mütənasib olacaqdır ;

• remove(int index) - elementi, məsələn, ortadan çıxararkən biz O(n/2) vaxtını alacağıq, çünki elementləri onun sağ tərəfinə bir xana geri köçürməli olacağıq. Müvafiq olaraq, siyahının əvvəlindən silinirsə, onda O(n), sonundan - O(1);
• add(int index, Object obj) - silməyə bənzər bir vəziyyət: ortasına əlavə edərkən, sağdakı bir xanadakı elementləri irəli aparmalı olacağıq, buna görə də vaxt O(n/2). Təbii ki, əvvəldən - O(n), sondan - O(1);
• set(int index, Object obj) - burada vəziyyət fərqlidir, çünki sadəcə istədiyiniz elementi tapmaq və qalanını köçürmədən onun üzərinə yazmaq lazımdır, ona görə də O(1).

Bu məqalədə ArrayList haqqında daha çox oxuyun . LinkedList eyni anda iki interfeysi - List və Queue tətbiq edir və buna görə də hər iki məlumat strukturuna xas olan xüsusiyyətlərə və metodlara malikdir. Siyahıdan bir elementə indekslə, növbədən - "baş" və "quyruq" varlığına giriş əldə etdi. Daxili olaraq, ikiqat əlaqəli siyahını təmsil edən məlumat strukturu kimi həyata keçirilir. Yəni, "quyruq" və "baş" istisna olmaqla, hər bir elementin növbəti və əvvəlki ilə əlaqəsi var.

• get(int index) - siyahının ortasında olan elementi axtararkən, istədiyiniz element tapılana qədər bütün elementləri sıra ilə axtarmağa başlayır. Məntiqi olaraq, axtarış O(n/2) götürməlidir , lakin LinkedList-in də quyruğu var, ona görə də axtarış hər iki tərəfdən eyni vaxtda aparılır. Müvafiq olaraq, vaxt O(n/4) -ə endirilir .

  Əgər element siyahının əvvəlinə və ya sonuna yaxındırsa, onda vaxt O(1) olacaq ;

• əlavə et(Object obj) - yeni element əlavə edərkən, “quyruq” elementində əlavə edilmiş növbəti elementə keçid olacaq və yenisi bu əvvəlki elementə keçid alacaq və yeni “quyruq” olacaq. Müvafiq olaraq, vaxt O(1) olacaq ;
• remove(int index) - get(int index) metoduna bənzər məntiq . Siyahının ortasından elementi silmək üçün əvvəlcə onu tapmaq lazımdır. Bu, yenə O(n/4) dir , halbuki silinmənin özü əslində heç nə götürmür, çünki o, yalnız qonşu obyektlərin göstəricisini dəyişir (onlar bir-birinə istinad etməyə başlayırlar). Əgər element əvvəlində və ya sonundadırsa, onda yenidən - O(1) ;
• add(int index, Object obj) və set(int index, Object obj) - metodlar əldə etmək üçün eyni vaxt mürəkkəbliyinə malik olacaq(int index) , çünki çox vaxt elementin axtarışına sərf olunur. Buna görə də, siyahının ortası üçün - O(n/4) , başlanğıc üçün - O(1).

LinkedList ilə işləmək haqqında daha çox məlumat bu məqalədə təsvir edilmişdir . Bütün bunlara cədvəldə baxaq: Yəqin ki, artıq başa düşdüyünüz kimi, bu suala birmənalı cavab vermək mümkün deyil. Axı, müxtəlif vəziyyətlərdə fərqli sürətlərdə işləyirlər. Buna görə də, sizə belə bir sual verildikdə dərhal bu siyahının nəyə diqqət yetirəcəyini və ən çox hansı əməliyyatların aparılacağını soruşmalısınız. Bundan başlayaraq, cavab verin, amma bunun niyə belə olduğunu izah edin. Müqayisəmizi ümumiləşdirək: ArrayList:

• ən çox görülən əməliyyat elementin axtarışı, elementin üzərinə yazılmasıdırsa, ən yaxşı seçimdir;
• əməliyyat başlanğıc-ortada daxil etmə və silmədirsə, ən pis seçimdir, çünki elementlərin sağdakı yerdəyişmə əməliyyatları baş verəcəkdir.

LinkedList:

• ən yaxşı seçim, əgər tez-tez əməliyyatımız başlanğıc-ortada daxil etmə və silmədirsə;
• ən ümumi əməliyyat axtarışdırsa, ən pis seçimdir.

9. HashMap-da elementlər necə saxlanılır?

HashMap kolleksiyası daxili massiv Node[] cədvəlini ehtiva edir , onun xanaları da buckets adlanır . Node ehtiva edir:

• açar - açara keçid,
• dəyər - dəyərə istinad,
• hash - hash dəyəri,
• növbəti - növbəti Node üçün keçid .

Cədvəl[] massivinin bir xanası növbəti Node elementinə keçidi olan Node obyektinə istinaddan ibarət ola bilər və onun digərinə keçidi ola bilər və s... Nəticədə, bu Node elementləri növbəti ilə keçidi olan elementləri olan tək bağlı siyahı . Bu halda, bir zəncirin elementlərinin hash dəyəri eyni olur. Qısa bir araşdırmadan sonra elementlərin HashMap- da necə saxlandığına baxaq :

1. Açar null üçün yoxlanılır . Əgər null olarsa , onda açar cədvəl[0] xanasında saxlanılacaq , çünki null üçün hash kodu həmişə 0-dır.
2. Açar null deyilsə , o zaman açar obyektin hashcode() metodu çağırılır və onun hash kodunu qaytaracaq. Bu hash kodu Node obyektinin saxlanacağı massiv xanasını müəyyən etmək üçün istifadə olunur.
3. Sonra, bu heşkod heşkodu hesablayan daxili hash() metodunda yerləşdirilir , lakin cədvəl[] massivinin ölçüsü daxilində .
4. Sonra, hash dəyərindən asılı olaraq, Node cədvəlin [] massivində xüsusi bir xanaya yerləşdirilir .
5. Əgər cari Node elementini saxlamaq üçün istifadə edilən cədvəl[] xanası boş deyilsə, lakin artıq müəyyən elementə malikdirsə, onda Node elementləri sonuncu elementə çatana qədər növbəti dəyər üzərində təkrarlanır. Yəni, növbəti sahəsi null olan sahə .

   Bu axtarış zamanı qorunan Node obyektinin açarı axtarılanların açarları ilə müqayisə edilir:

   • uyğunluq tapılarsa, axtarış başa çatacaq və yeni Node uyğunluğun tapıldığı Düyün üzərinə yazacaq (yalnız onun dəyər sahəsi üzərinə yazılacaq );
   • heç bir əsas uyğunluq tapılmadıqda, yeni Node bu siyahıda sonuncu olacaq və əvvəlkinin ona növbəti keçidi olacaq.

Müsahibə zamanı tez-tez sual yaranır: münaqişə nədir ? Cədvəl[] massivinin xanasının bir elementi deyil, iki və ya daha çox zənciri saxladığı vəziyyət toqquşma adlanır . Bir cədvəl[] xanasında yalnız bir elementin saxlandığı normal hallarda , HashMap elementlərinə daxil olmaq sabit O(1) vaxt mürəkkəbliyinə malikdir . Ancaq istədiyiniz elementi olan bir hüceyrə elementlər zəncirindən ibarət olduqda ( toqquşma ), onda O(n) , çünki bu halda vaxt çeşidlənən elementlərin sayı ilə düz mütənasibdir.

10. İteratoru izah edin

Yuxarıdakı Kolleksiya iyerarxiyasının xəritələşdirilməsi diaqramında Kolleksiya interfeysi bütün iyerarxiyanın başladığı yer idi, lakin praktikada bu, tam olaraq belə deyil. Kolleksiya , Iterator<E> interfeysini həyata keçirən obyekti qaytaran iterator() metodu ilə interfeysdən miras qalır . Iterator interfeysi belə görünür:

public interface Iterator <E>{
   
    E next();
    boolean hasNext();
    void remove();
}

next() - bu metodu çağırmaqla növbəti elementi əldə edə bilərsiniz. hasNext() - növbəti elementin olub-olmadığını və kolleksiyanın sonuna çatılıb-çatılmadığını öyrənməyə imkan verir. Və hələ də elementlər olduqda hasNext() true qaytaracaq . Tipik olaraq, hasNext() növbəti() metodundan əvvəl çağırılır , çünki next() kolleksiyanın sonuna çatdıqda NoSuchElementException atacaq . remove() - Next() -ə sonuncu zənglə əldə edilmiş elementi silir . İteratorun məqsədi elementləri təkrarlamaqdır. Misal üçün:

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

Əslində, hər bir döngə bir iteratordan istifadə edərək başlıq altında həyata keçirilir. Bu barədə daha ətraflı burada oxuya bilərsiniz . List öz iterator versiyasını təqdim edir, lakin daha soyuq və daha mürəkkəbdir - ListIterator . Bu interfeys İteratoru genişləndirir və əlavə üsullara malikdir:

• kolleksiyada əvvəlki element varsa, hasPrevious doğru, əks halda false qaytaracaq;
• əvvəlki cari elementi qaytarır və əvvəlkinə keçir; heç biri yoxdursa, onda NoSuchElementException atılır;
• add ötürülən obyekti next()- ə növbəti çağırışla qaytarılacaq elementdən əvvəl daxil edəcək ;
• set cari elementə ötürülən obyektə istinad təyin edir;
• nextIndex növbəti elementin indeksini qaytarır. Əgər belə bir şey yoxdursa, o zaman siyahının ölçüsü qaytarılır;
• əvvəlki İndeks əvvəlki elementin indeksini qaytarır. Əgər yoxdursa, onda -1 rəqəmi qaytarılır.

Bu gün mənim üçün hamısı budur. Ümid edirəm ki, bu yazını oxuduqdan sonra əziz arzunuza - inkişaf etdirici olmağa daha da yaxınlaşırsınız.