Java tərtibatçısı üçün müsahibələrdən alınan sualların və cavabların təhlili. 9-cu hissə

Atəşfəşanlıq! Proqramçı olmaq asan deyil. Daim öyrənmək, həmişə yeni bir şey öyrənmək lazımdır. Ancaq hər bir işdə olduğu kimi, ən çətin şey başlamaq, hədəfinizə doğru ilk addımı atmaqdır. Və bu saytda oturub bu yazını oxuduğunuz üçün ilk addımı tamamladınız. Bu o deməkdir ki, indi siz məqsədyönlü şəkildə, yol boyu sürəti azaltmadan və ya söndürmədən məqsədinizə doğru hərəkət etməlisiniz. Düzgün başa düşdümsə, məqsədiniz Java proqramçısı olmaq və ya əgər varsa, biliklərinizi artırmaqdır. Əgər belədirsə, onda siz doğru yerdəsiniz, çünki biz 250+ Java tərtibatçısının müsahibə suallarının geniş siyahısını təhlil etməyə davam edəcəyik. Davam edək!

Kolleksiyalar

84. İteratorlar və onların istifadəsi haqqında bizə məlumat verin

Kolleksiyalar hər hansı Java tərtibatçısının müsahibəsində sevimli mövzulardan biridir və kolleksiya iyerarxiyası haqqında danışarkən namizədlər çox vaxt bunun Kolleksiya interfeysi ilə başladığını deyirlər . Ancaq bu doğru deyil, çünki bu interfeysin üstündə başqa biri var - İterable . Bu interfeys cari kolleksiya üçün İterator obyektini çağırmağa imkan verən iterator() metodunu təmsil edir. Və bu İterator obyekti tam olaraq nədir ? İterator , istifadəçinin müəyyən kolleksiyanın həyata keçirilməsini bilməsi tələb olunmadan kolleksiyada hərəkət etmək və elementlər üzərində təkrarlamaq imkanı verən obyektdir. Yəni, bu, kolleksiyanın elementlərinə bir növ göstəricidir, sanki onun içindəki müəyyən bir yerə baxır. İterator aşağıdakı üsullara malikdir:

• hasNext() - göstəricidən sonra yerləşən element varsa, doğru qaytarır (bu üsul kolleksiyanın sonuna çatılıb-çatılmadığını öyrənməyə imkan verir);
• next() - göstəricidən sonrakı elementi qaytarır. Heç biri yoxdursa, NoSuchElementException atılır . Yəni, bu üsuldan istifadə etməzdən əvvəl elementin mövcud olduğundan əmin olmaq daha yaxşıdır - hasNext() istifadə edərək ;
• remove() - növbəti() metodundan istifadə edərək kolleksiyadan alınan sonuncu elementi silir . Əgər next() heç vaxt remove() çağırılmamış çağırılmamışsa , istisna atılacaq - IllegalStateException ;
• forEachRemaining(<İstehlakçı>) - kolleksiyanın hər bir elementi ilə ötürülən hərəkəti yerinə yetirir (metod Java 8-də ortaya çıxdı).

Müzakirə olunan iterator üsullarından istifadə edərək siyahıda təkrarlamanın və onun bütün elementlərinin silinməsinin kiçik bir nümunəsi:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

Konsol göstərəcək: Bu o deməkdir ki, elementlərin çıxarılması uğurlu olub. İteratorumuz olduqdan sonra bütün elementləri ekrana çap etmək üçün bir üsuldan istifadə edə bilərik:

iterator.forEachRemaining(x -> System.out.print(x));

Lakin bundan sonra iterator sonrakı istifadə üçün yararsız hala düşəcək, çünki o, bütün siyahını keçəcək və adi iteratorun geriyə qayıtma üsulları yoxdur. Burada biz tədricən LinkedList-ə , yəni onun modernləşdirilmiş təkrarlayıcı növünü - ListIterator qaytaran listIterator() metoduna yaxınlaşırıq . Adi (standart) iterator üsullarına əlavə olaraq, bunun əlavə üsulları var:

• add(<Element>) - siyahıya yeni element daxil edir;
• hasPrevious() - göstəricidən əvvəl yerləşən element varsa (əvvəlki elementin olub-olmamasından asılı olmayaraq) doğru qaytarır;
• nextIndex() - göstəricidən sonrakı elementin siyahısında indeksi qaytarır;
• əvvəlki() - əvvəlki elementi qaytarır (göstəriciyə qədər);
• previousIndex() - əvvəlki elementin indeksini qaytarır;
• set(<Element>) - sonrakı() və ya əvvəlki() metodları ilə qaytarılan sonuncu elementi əvəz edir .

Gördüyünüz kimi, bu iteratorun funksionallığı daha maraqlıdır: o, hər iki istiqamətdə hərəkət etməyə imkan verir və elementlərlə işləyərkən əllərinizi azad edir. Həmçinin, insanlar iteratorlar haqqında danışarkən bəzən nümunənin özünü nəzərdə tuturlar. Problemə düşməmək və bu barədə inandırıcı danışmaq üçün İterator nümunəsi haqqında bu məqaləni oxuyun .

85. Java Collection Framework-də kolleksiya iyerarxiyası nədir?

Java-da iki kolleksiya iyerarxiyası var. Birinci iyerarxiya aşağıdakı struktura malik Kolleksiya iyerarxiyasının özüdür : O, öz növbəsində aşağıdakı altkolleksiyalara bölünür:

• Dəst , belə bir məlumat strukturunu sıralanmamış unikal (təkrar etməyən) elementləri ehtiva edən dəst kimi təsvir edən interfeysdir . İnterfeys standart tətbiqlərə malikdir - TreeSet , HashSet və LinkedHashSet .
• Siyahı obyektlərin ardıcıl ardıcıllığını saxlayan məlumat strukturunu təsvir edən interfeysdir. Siyahıya daxil olan nümunələr bu kolleksiyadakı indeksinə görə daxil edilə və silinə bilər (massivin analoqu, lakin dinamik ölçüsünün dəyişdirilməsi ilə). İnterfeys standart tətbiqlərə malikdir - ArrayList , Vector ( köhnəlmiş hesab olunur və əslində istifadə edilmir ) və LinkedList .
• Queue FIFO - First In First Out qaydasına əməl edən növbə şəklində elementləri saxlayan məlumat strukturunu təsvir edən interfeysdir . İnterfeys aşağıdakı standart tətbiqlərə malikdir: LinkedList (bəli, o da Queue tətbiq edir ) və PriotityQueue .

Kolleksiyaların ikinci iyerarxiyası Map , aşağıdakı quruluşa malikdir: Bu kolleksiyada altkolleksiyalara bölmələr yoxdur (çünki Xəritə iyerarxiyasının özü altkolleksiya kimi bir şeydir, lakin ayrıca yerləşir). Standart Xəritə tətbiqləri Hashtable (köhnəlməmiş hesab olunur), LinkedHashMap və TreeMap- dır . Əslində, Kolleksiya haqqında soruşduqda , adətən hər iki iyerarxiya nəzərdə tutulur.

86. ArrayList-in daxili strukturu nədir?

ArrayList seriala bənzəyir, lakin dinamik şəkildə genişlənmə qabiliyyətinə malikdir. Bunun mənası nədi? Fakt budur ki, ArrayList adi massiv əsasında işləyir, yəni elementləri daxili massivdə saxlayır (onun standart ölçüsü 10 xanadır). Daxili massiv dolduqda yeni massiv yaradılır, onun ölçüsü düsturla müəyyən edilir:

<размерТекущегоМассива> * 3 / 2  + 1

Yəni, massivimizin ölçüsü 10 olarsa, yenisinin ölçüsü belə olacaq: 10 * 3 / 2 + 1 = 16. Bundan sonra, birinci (köhnə) massivdən istifadə edərək bütün dəyərlər ona kopyalanır. yerli System.arraycopy () metodu və birinci massiv silinir. Əslində, ArrayList-in dinamik genişlənməsi belə həyata keçirilir . Ən çox istifadə olunan ArrayList üsullarına nəzər salaq : 1. add(<Elelement>) - massivin sonuna (sonuncu boş xanaya) element əlavə edir və əvvəlcə bu massivdə boşluq olub-olmadığını yoxlayır. Əgər orada deyilsə, elementlərin kopyalandığı yeni massiv yaradılır. Bu əməliyyatın loqarifmik mürəkkəbliyi O(1)-dir. Bənzər bir üsul var - əlavə et(<İndeks>,<Elelement>) . O, elementi siyahının (massivin) sonuna deyil, arqument kimi gələn indeksi olan xüsusi xanaya əlavə edir. Bu halda loqarifmik mürəkkəblik əlavə olunduğu yerə görə fərqlənəcək:

• əgər bu təxminən siyahının başlanğıcı idisə, loqarifmik mürəkkəblik O(N)-ə yaxın olacaq, çünki yenisinin sağında yerləşən bütün elementlər bir xana sağa köçürülməli olacaq;
• element ortada daxil edilirsə - O(N/2) çünki siyahı elementlərinin yalnız yarısını bir xana sağa köçürməliyik.

Yəni, bu metodun loqarifmik mürəkkəbliyi elementin daxil edildiyi yerdən asılı olaraq O(N) ilə O(1) arasında dəyişir. 2. set(<İndeks>,<Elelement>) - elementi siyahıda göstərilən mövqeyə yazır. Əgər həmin mövqedə artıq element varsa, onun üzərinə yazır. Bu əməliyyatın loqarifmik mürəkkəbliyi O(1)-dir, çünki yerdəyişmə yoxdur: yalnız xatırladığımız kimi O(1) mürəkkəbliyi olan massivdə indeks üzrə axtarış və elementin yazılması. 3. remove(<index>) - elementin daxili massivdəki indeksinə görə silinməsi. Siyahının sonunda olmayan bir elementi silərkən, elementi sildikdən sonra qalan boşluğu bağlamaq üçün bütün elementləri onun sağındakı bir xana sola köçürməlisiniz. Buna görə də, element ortada - O(N/2) idisə, loqarifmik mürəkkəblik add(<İndeks>,<Elelement>) ilə eyni olacaq, çünki elementlərin yarısını bir sola sürüşdürmək lazımdır. Müvafiq olaraq, başlanğıcda olsaydı - O(N). Yaxşı, əgər sonda O(1) olarsa, heç nəyi köçürməyə ehtiyac yoxdur. Bu mövzunu daha dərindən araşdırmaq istəyənlər üçün bu linki ArrayList sinfinin təhlili ilə məqaləyə buraxacağam .

87. LinkedList-in daxili strukturu hansıdır?

ArrayList daxili massivdə elementləri ehtiva edirsə, LinkedList ikiqat əlaqəli siyahı şəklindədir. Bu o deməkdir ki, hər bir element əvvəlki elementə ( əvvəlki ) və sonrakı elementə ( sonrakı ) keçid ehtiva edir. Birinci elementin əvvəlki ilə əlaqəsi yoxdur (bu, birincidir), lakin o, siyahının baş hissəsi hesab olunur və LinkedList-in birbaşa ona keçidi var. Sonuncu elementin, əslində, növbəti elementi yoxdur, o, siyahının quyruğudur və buna görə də LinkedList-in özündə ona birbaşa keçid var . Buna görə də, siyahının baş və ya quyruğuna daxil olmağın loqarifmik mürəkkəbliyi O(1)-dir. ArrayList -də siyahı böyüdükdə daxili massiv artdı, amma burada hər şey daha sadə olur - element əlavə edərkən bir neçə keçid sadəcə dəyişir. Ən çox istifadə olunan LinkedlList üsullarına nəzər salaq : 1. add(<Elelement>) - siyahının sonuna əlavə etmək, yəni. sonuncu elementdən (5) sonra yeni elementə keçid növbəti kimi əlavə olunacaq . Yeni elementin əvvəlki element kimi sonuncuya (5) keçidi olacaq . Belə bir əməliyyatın loqarifmik mürəkkəbliyi O(1) olacaq, çünki yalnız sonuncu elementə keçid lazımdır və xatırladığınız kimi, quyruğun LinkedList- dən birbaşa əlaqəsi var və ona daxil olmağın loqarifmik mürəkkəbliyi minimaldır. 2. add(<Index>,<Elelement>) - elementin indeks üzrə əlavə edilməsi. Məsələn, siyahının ortasına element əlavə edərkən, baş və quyruqdan (hər iki tərəfdən) olan elementlər əvvəlcə istədiyiniz yer tapılana qədər təkrarlanır. Əgər üçüncü və dördüncü arasında element daxil etmək istəyiriksə (yuxarıdakı şəkildə), onda düzgün yeri axtararkən üçüncü elementin növbəti keçidi artıq yenisini göstərəcək. Yenisi üçün əvvəlki keçid üçüncü birinə işarə edəcək. Müvafiq olaraq, dördüncü elementin - əvvəlki - keçidi artıq yeni elementə, yeni elementin növbəti keçidi isə dördüncü elementə işarə edəcək: Bu metodun loqarifmik mürəkkəbliyi yeni elementə verilən indeksdən asılı olacaq:

• baş və ya quyruğa yaxındırsa, O(1)-ə yaxınlaşacaq, çünki əslində elementlər üzərində təkrarlamaq lazım olmayacaq;
• ortasına yaxındırsa, onda O(N/2) - başdan və quyruqdan olan elementlər tələb olunan element tapılana qədər eyni vaxtda çeşidlənəcək.

3. set(<İndeks>,<Elelement>) - elementi siyahıda göstərilən mövqeyə yazır. Bu əməliyyatın loqarifmik mürəkkəbliyi yenə də elementin baş, quyruğu və ya ortasına nə qədər yaxın olmasından asılı olaraq O(1) ilə O(N/2) arasında dəyişəcək. 4. remove(<index>) - elementi siyahıdan çıxarır, mahiyyətcə silinəndən əvvəl gələn elementi ( əvvəlki ) silinəndən sonra gələn elementə istinad edir ( sonrakı ). Və əksinə: belə ki, silinən elementdən sonra gələn element silinəndən əvvəl gələn elementə aiddir: Nəticə indeks üzrə əlavə etməyə tərs bir prosesdir ( add(<Index>,<Elelement>) ). LinkedList-in daxili strukturu haqqında daha çox öyrənmək istəyənlər üçün bu məqaləni oxumağı məsləhət görürəm .

88. HashMap-ın daxili strukturu nədir?

Java tərtibatçısı ilə müsahibə zamanı bəlkə də ən populyar suallardan biridir. HashMap v açar-dəyər cütləri ilə işləyir . Onlar HashMapv-in özündə necə saxlanılır ? HashMap daxilində bir sıra qovşaqlar var:

Node<K,V>[] table

Varsayılan olaraq, massivin ölçüsü 16-dır və elementlərlə doldurulduqca o, hər dəfə ikiqat artır ( LOAD_FACTOR- a çatdıqda - dolğunluğun müəyyən faizi, standart olaraq 0,75- dir ). Hər bir qovşaq açarın hashini, açarı, dəyərini və növbəti elementə keçidi saxlayır: Əslində, “növbəti elementə keçid” o deməkdir ki, biz tək-tək əlaqəli siyahı ilə məşğul oluruq, burada hər bir elementə keçid var. növbəti. Yəni, HashMap məlumatları tək-tək əlaqəli siyahılar massivində saxlayır. Ancaq dərhal qeyd edəcəm: cədvəl massivinin bir xanasında birdən çox elementdən ibarət oxşar tək əlaqəli siyahıya keçid olduqda, bu yaxşı deyil. Bu fenomen toqquşma adlanır . Ancaq ilk şeylər. Yeni cütün put metodundan istifadə edərək necə saxlandığını görək . Əvvəlcə açarın hachCode() kodu alınır. Buna görə də, hashmapın düzgün işləməsi üçün bu metodun açar kimi ləğv edildiyi dərsləri almalısınız. Bu hash kodu daha sonra daxili metodda istifadə olunur - hash() - cədvəl massivinin ölçüsü daxilində rəqəmi müəyyən etmək üçün . Sonra, alınan nömrədən istifadə edərək, cədvəl massivinin müəyyən bir xanasına daxil olursunuz . Burada iki halımız var:

1. Hüceyrə boşdur - yeni Node dəyəri orada saxlanılır .
2. Hüceyrə boş deyil - düymələrin dəyəri müqayisə edilir. Əgər onlar bərabərdirsə, yeni Node dəyəri köhnənin üzərinə yazır, bərabər deyilsə, növbəti elementə daxil olur və onun açarı ilə müqayisə edilir... Və s. tək əlaqəli siyahı və orada sonuncu element kimi saxlanılacaq.

Elementi açarla ( get(<key>) metodu ) axtararkən açarın hashCode kodu hesablanır, sonra hash() funksiyasından istifadə edərək onun massiv daxilindəki dəyəri və əldə edilən nömrədən istifadə edərək cədvəl massivinin xanası tapılır. , burada axtarış artıq qovşaqları sadalamaq və istədiyiniz qovşağın açarını cari olanın açarı ilə müqayisə etməklə aparılır. Xəritədə ideal vəziyyətdə olan əməliyyatlar O(1) alqoritmik mürəkkəbliyinə malikdir, çünki onlar massivə daxil olurlar və xatırladığınız kimi elementlərin sayından asılı olmayaraq massiv üzərində əməliyyatlar O(1) mürəkkəbliyinə malikdir. Amma bu idealdır. İstifadə olunan massiv xanası boş olmadıqda (2) və orada artıq bəzi qovşaqlar olduqda, alqoritmik mürəkkəblik xətti O(N)-yə çevrilir, çünki indi düzgün yeri tapmaqdan əvvəl elementlər üzərində təkrarlamaq lazımdır. Bunu qeyd etməyə kömək edə bilmirəm: Java 8-dən başlayaraq, əgər tək bağlı siyahı qovşağında 8-dən çox element (toqquşma) varsa, o, ikili ağaca çevrilir. Bu halda, alqoritmik mürəkkəblik artıq O(N) deyil, O(log(N)) olacaq - bu başqa məsələdir, elə deyilmi? HashMap böyük bir mövzudur və insanlar müsahibələrdə bu haqda suallar verməyi xoşlayırlar. Buna görə də sizə bunu ətraflı başa düşməyi məsləhət görürəm (dişlərinizdən sıçraması üçün). Şəxsən mənim HashMap sualları olmadan müsahibəm olmayıb . Bu məqalədə HashMap- a dərindən baxa bilərsiniz . Bu günə qədər, davamı budur...