Intervyuda nima so'rashi mumkin: Java-da ma'lumotlar tuzilmalari. 2-qism

1-QISM Endi biz har bir Java dasturchisi bilishi kerak bo'lgan baza haqida gapiramiz. Hammasi boshlanadigan klassik bilim haqida. Bugun men har qanday intervyuning asosiy mavzularidan biri - Java-dagi ma'lumotlar tuzilmalariga to'xtalib o'tmoqchiman . Shunday qilib, buta atrofida urish o'rniga, keling, boshlaylik. Suhbat davomida sizga ushbu mavzu bo'yicha berilishi mumkin bo'lgan savollar ro'yxatining davomini ko'ring.

6. Ro'yxat haqida bizga xabar bering

Ro'yxat - ob'ektlarning tartiblangan tuzilishini ifodalovchi interfeys bo'lib, u ro'yxat deb ataladi. Ushbu tuzilmaning "hiylasi" shundaki, Ro'yxatdagi elementlar indeks , ya'ni Ro'yxatning ichki identifikatori bo'yicha kiritilishi, o'zgartirilishi yoki o'chirilishi mumkin . Boshqacha qilib aytganda, indeks: "ro'yxat boshidan qancha element bor" degan ma'noni anglatadi. Birinchi Ro'yxat elementida indeks 0, ikkinchisida indeks 1 va hokazo. Shunday qilib, beshinchi element ro'yxat boshidan to'rtta element uzoqlikda joylashgan. Yuqorida aytib o'tilganidek, elementlarning ro'yxatga qo'shilish tartibi muhim ahamiyatga ega. Shuning uchun ma'lumotlar strukturasi ro'yxat deb ataladi . Indeks bo'yicha elementlar bilan ishlashga qaratilgan ushbu tuzilishga xos usullarni sanab o'tamiz:

• get - elementni belgilangan pozitsiyaga qaytaradi (indeks qiymati bo'yicha),
• olib tashlash - elementni belgilangan holatda olib tashlaydi,
• set - ko'rsatilgan pozitsiyadagi elementni usulda ko'rsatilgan element bilan almashtiradi.

Asosiy ilovalar ArrayList va LinkedList hisoblanadi . Biz ular haqida biroz keyinroq gaplashamiz. Vektor - bu iplar uchun xavfsiz bo'lgan ro'yxat, shuning uchun bu sinfdagi har bir usul sinxronlashtiriladi. Ammo shuni yodda tutingki, agar siz ba'zi ro'yxat harakatlarini himoya qilishni istasangiz, siz butun operatsiyalar ketma-ketligini sinxronlashtirasiz. Va individual operatsiyalarni sinxronlashtirish ham kamroq xavfsiz, ham ancha sekinroq. Albatta, Vektorda qulflash kerak bo'lmasa ham, tepada qulflash mavjud. Shuning uchun bu sinf endi eskirgan deb hisoblanadi va ishlatilmaydi. Aytgancha: ArrayList Vektor ga o'xshaydi , lekin qulflashni ishlatmaydi, shuning uchun u hamma joyda qo'llaniladi. Stack - bu bitta standart konstruktorga va Vektor sinfining barcha usullariga, shuningdek, bir nechta o'ziga xos usullarga ega Vektor sinfining pastki sinfidir (bular haqida keyinroq gaplashamiz). Misol tariqasida, jarayonni hujjatlar bilan papkalar to'plami sifatida tasavvur qilishingiz mumkin. Siz bitta papkani stekning yuqori qismiga joylashtirasiz va bu papkalarni faqat yuqoridan boshlab teskari tartibda olishingiz mumkin. Aslida, bu LIFO tipidagi mexanizm , ya'ni oxirgi kiruvchi birinchi chiqadi , oxirgi kelgan birinchi bo'lib ketadi. Stack o'z usullarini amalga oshiradi:

• surish - o'tkazilgan elementni stekning yuqori qismiga qo'shadi;
• peek - stekning yuqori qismida joylashgan elementni qaytaradi;
• pop - shuningdek, stekning yuqori qismidagi elementni qaytaradi, lekin uni olib tashlaydi;
• empty - stekning bo'sh yoki yo'qligini tekshiradi - rost yoki noto'g'ri ;
• qidiruv - berilgan element uchun stekni qidiradi. Agar element topilsa, uning stekning yuqori qismiga nisbatan tartib raqami qaytariladi. Agar element topilmasa, -1 qiymati qaytariladi.

Hozirgi vaqtda Stack kichik klassi soddaligi va moslashuvchanligi tufayli aslida ishlatilmaydi, ammo shunga qaramay, siz unga duch kelishingiz mumkin. Misol uchun, siz biron bir xatoga duch kelganingizda va konsolda bu haqda xabarlar to'plamini ko'rasiz. Stack va navbat haqida ko'proq ma'lumotni ushbu maqolada o'qishingiz mumkin .

7. Xarita haqida gapirib bering

Yuqorida aytib o'tilganidek, Xarita - bu interfeyslarning alohida tuzilishi va ularni amalga oshirishga ega bo'lgan to'plam. Bu alohida, chunki bu erda qiymatlar bir vaqtning o'zida emas, balki "kalit-qiymat" juftligida saqlanadi. Asosiy xarita usullari :

• put(K tugmasi, V qiymati) - Xaritaga element qo'shish;
• get(Ob'ekt kaliti) - qiymatni kalit bo'yicha qidirish;
• containKey(Ob'ekt kaliti) — Xaritada ushbu kalit mavjudligini tekshiradi;
• containValue(Ob'ekt qiymati) - Xaritada ushbu qiymat mavjudligini tekshiradi;
• olib tashlash(Ob'ekt kaliti) - qiymatni kaliti bilan olib tashlash.

Ko'rib turganingizdek, aksariyat operatsiyalar kalit yordamida ishlaydi. Qoida tariqasida, o'zgarmas ob'ektlar kalit sifatida tanlanadi . Ushbu ob'ektning odatiy misoli String . Xaritaning asosiy ilovalari :

1. HashMap - qiymatlarni tasodifiy tartibda saqlash uchun mo'ljallangan, ammo xarita elementlarini tezda qidirishga imkon beradi. Null kalit so'zidan foydalanib kalitni belgilash imkonini beradi , lekin bir martadan ortiq emas, chunki bir xil kalitlarga ega bo'lgan juftliklar bir-birining ustiga yoziladi. Asosiy shart - bu kalitlarning o'ziga xosligi: qiymatlarni takrorlash mumkin (bir nechta null qiymatlar bo'lishi mumkin).
2. LinkedHashMap - bu qiymatlarni qo'shilgan tartibda saqlaydigan HashMap analogidir . Shunga ko'ra, LinkedList kabi , uning sarlavhasi bor - ikki marta bog'langan ro'yxatning boshi. Ishga tushirilganda, u o'zini ko'rsatadi.

   LinkedHashMap shuningdek, iterator ishlatilganda elementlarga qanday kirishni ko'rsatadigan accessOrder-ga ega . AccessOrder noto'g'ri bo'lsa , kirish elementlar kiritilgan tartibda amalga oshiriladi. Agar rost bo'lsa, elementlar oxirgi kirish tartibida bo'ladi (oxirgi kirish elementi oxirida joylashtiriladi).

3. TreeMap - bu elementlarni asosiy qiymatlar bo'yicha saralaydigan Xarita . TreeSet ga o'xshash , lekin kalit qiymatlarga asoslangan juftliklar uchun. TreeMap tartiblash qoidalarini o'rnatish uchun kalitlar Comparable interfeysini amalga oshirishi kerak. Aks holda, kalitga yo'naltirilgan taqqoslash ( TreeMap konstruktorida ko'rsatilgan ), TreeSet bo'lishi kerak - ichida TreeMap ob'ekti bilan amalga oshiriladi, unda barcha sehrlar sodir bo'ladi.

   TreeMap-da qizil-qora daraxtlardan foydalangan holda tartiblash haqida ko'proq TreeMap-ning xususiyatlari haqidagi maqolada o'qishingiz mumkin .

4. Hashtable HashMap ga o'xshaydi , lekin nulllarni kalit yoki qiymat sifatida saqlashga ruxsat bermaydi . U ko'p tarmoqli nuqtai nazardan ehtiyotkorlik bilan sinxronlashtiriladi, bu esa o'z navbatida ko'p tarmoqli nuqtai nazardan xavfsiz ekanligini anglatadi. Ammo bu amalga oshirish eskirgan va sekin, shuning uchun endi siz Hashtable-ni ko'proq yoki kamroq yangi loyihalarda ko'rmaysiz .

8. ArrayList va LinkedList. Qaysi birini ishlatish afzalroq?

Bu savol, ehtimol, ma'lumotlar tuzilmalarida eng mashhur bo'lib, u bilan birga ba'zi tuzoqlarni ham o'z ichiga oladi. Javob berishdan oldin, keling, ushbu ma'lumotlar tuzilmalari haqida ko'proq bilib olaylik. ArrayList List interfeysini amalga oshiradi va kerak bo'lganda kengaytiriladigan ichki massivda ishlaydi. Ichki massiv to'liq to'ldirilganda va yangi elementni kiritish kerak bo'lganda, (oldSize * 1,5) +1 o'lchamli yangi massiv yaratiladi. Shundan so'ng, eski massivdagi barcha ma'lumotlar yangi + yangi elementga ko'chiriladi va eskisi axlat yig'uvchi tomonidan o'chiriladi . Qo'shish usuli elementni massivning oxirgi bo'sh katagiga qo'shadi. Ya'ni, agar bizda allaqachon 3 ta element mavjud bo'lsa, u keyingi elementni 4-hujayraga qo'shadi. Keling, asosiy usullarning ishlashini ko'rib chiqaylik:

• get(int index) - massivdagi elementni indeks bo'yicha olish O(1) da eng tezdir ;
• add(Object obj) - agar yangi element uchun ichki massivda etarli joy bo'lsa, unda oddiy kiritish bilan O(1) vaqt sarflanadi , chunki qo'shilish oxirgi katakka mo'ljallangan.

  Agar yangi massiv yaratish va unga tarkibni nusxalash kerak bo'lsa, unda bizning vaqtimiz O(n) massivdagi elementlar soniga to'g'ridan-to'g'ri proportsional bo'ladi ;

• remove(int index) - elementni, masalan, o'rtadan olib tashlashda, biz O(n/2) vaqtini olamiz, chunki elementlarni uning o'ng tomoniga bir katak orqaga o'tkazishimiz kerak bo'ladi. Shunga ko'ra, agar ro'yxat boshidan o'chirilgan bo'lsa, u holda O(n), oxiridan - O(1);
• add(int index, Object obj) - o'chirishga o'xshash holat: o'rtaga qo'shishda biz o'ngdagi bitta katakchadagi elementlarni oldinga siljitishimiz kerak, shuning uchun vaqt O(n/2). Albatta, boshidan - O(n), oxiridan - O(1);
• set(int index, Object obj) - bu erda vaziyat boshqacha, chunki siz faqat kerakli elementni topib, qolganlarini ko'chirmasdan uning ustiga yozishingiz kerak, shuning uchun O(1).

Ushbu maqolada ArrayList haqida ko'proq o'qing . LinkedList bir vaqtning o'zida ikkita interfeysni amalga oshiradi - List va Queue va shuning uchun ikkala ma'lumot tuzilmalariga xos xususiyatlar va usullarga ega. Ro'yxatdan u indeks bo'yicha elementga kirishni oldi, Navbatdan - "bosh" va "dum" mavjudligi. Ichkarida, u ikki marta bog'langan ro'yxatni ifodalovchi ma'lumotlar strukturasi sifatida amalga oshiriladi. Ya'ni, har bir element "quyruq" va "bosh" dan tashqari, keyingi va oldingisiga havolaga ega.

• get(int index) - ro'yxatning o'rtasida joylashgan elementni qidirganda, kerakli element topilgunga qadar barcha elementlarni tartibda qidirishni boshlaydi. Mantiqan, qidiruv O(n/2) ni olishi kerak , lekin LinkedList-ning ham dumi bor, shuning uchun qidiruv har ikki tomondan bir vaqtning o'zida amalga oshiriladi. Shunga ko'ra, vaqt O(n/4) ga qisqartiriladi .

  Agar element ro'yxat boshiga yoki oxiriga yaqin bo'lsa, u holda vaqt O (1) bo'ladi ;

• qo'shish(Object obj) - yangi element qo'shganda, "dum" elementi qo'shilgan keyingi elementga havolaga ega bo'ladi va yangisi ushbu oldingi elementga havola oladi va yangi "dum" bo'ladi. Shunga ko'ra, vaqt O (1) bo'ladi ;
• remove(int index) - get(int index) usuliga o'xshash mantiq . Ro'yxatning o'rtasidan elementni olib tashlash uchun avval uni topishingiz kerak. Bu yana O(n/4) , o'chirishning o'zi esa aslida hech narsa olmaydi, chunki u faqat qo'shni ob'ektlarning ko'rsatkichini o'zgartiradi (ular bir-biriga murojaat qila boshlaydi). Agar element boshida yoki oxirida bo'lsa, u holda yana - O(1) ;
• add(int index, Object obj) va set(int index, Object obj) - metodlar olish uchun bir xil vaqt murakkabligiga ega bo'ladi(int index) , chunki ko'p vaqt elementni qidirishga sarflanadi. Shuning uchun, ro'yxatning o'rtasi uchun - O(n/4) , boshi uchun - O(1).

LinkedList bilan ishlash haqida batafsil ma'lumot ushbu maqolada tasvirlangan . Bularning barchasini jadvalda ko'rib chiqamiz: Siz allaqachon tushunganingizdek, bu savolga aniq javob berishning iloji yo'q. Axir, turli vaziyatlarda ular turli tezlikda ishlaydi. Shuning uchun, sizga bunday savol berilganda, darhol ushbu ro'yxat nimaga e'tibor qaratishini va qaysi operatsiyalarni tez-tez bajarishini so'rashingiz kerak. Bundan boshlab, javob bering, lekin nima uchun bunday bo'lganini tushuntiring. Taqqoslashimizni umumlashtiramiz: ArrayList:

• eng tez-tez bajariladigan operatsiya elementni qidirish, elementni ustiga yozish bo'lsa, eng yaxshi tanlov;
• Agar operatsiya boshida-o'rtada kiritish va o'chirish bo'lsa, eng yomon tanlov, chunki o'ngdagi elementlarning siljish operatsiyalari amalga oshiriladi.

Bog'langan ro'yxat:

• eng yaxshi tanlov, agar bizning tez-tez bajariladigan operatsiyamiz boshida-o'rtada kiritish va o'chirish bo'lsa;
• Agar eng keng tarqalgan operatsiya qidiruv bo'lsa, eng yomon tanlov.

9. HashMapda elementlar qanday saqlanadi?

HashMap to'plamida ichki qator Node[] jadvali mavjud bo'lib , uning kataklari chelaklar deb ham ataladi . Tugun o'z ichiga oladi:

• kalit - kalitga havola,
• qiymat - qiymatga havola,
• hash - hash qiymati,
• keyingi - keyingi tugunga havola .

Jadval[] massivining bir yacheykasi keyingi Tugun elementiga havola bilan tugun obyektiga havolani o'z ichiga olishi mumkin va u boshqasiga havolaga ega bo'lishi mumkin va hokazo... Natijada, bu Tugun elementlari yakka bog'langan ro'yxat , keyingisiga havolasi bo'lgan elementlar. Bunday holda, bitta zanjir elementlarining xesh qiymati bir xil bo'ladi. Qisqa tahlildan so'ng, elementlar HashMap da qanday saqlanishini ko'rib chiqamiz :

1. Kalit null uchun tekshiriladi . Agar u null bo'lsa, kalit jadval[0] katakchasida saqlanadi, chunki null uchun xesh kodi har doim 0 bo'ladi.
2. Agar kalit null bo'lmasa , kalit ob'ektning hashcode() usuli chaqiriladi , bu uning xesh kodini qaytaradi. Ushbu xesh-kod Node obyekti saqlanadigan massiv katakchasini aniqlash uchun ishlatiladi.
3. Keyinchalik, bu xeshkod xeshkodni hisoblaydigan ichki hash() usuliga joylashtiriladi , lekin jadval[] massivi hajmida .
4. Keyinchalik, xesh qiymatiga qarab, Tugun jadval[] massividagi ma'lum bir katakka joylashtiriladi .
5. Joriy Tugun elementini saqlash uchun foydalanilgan jadval [] katakchasi boʻsh boʻlmasa-da, lekin allaqachon baʼzi elementga ega boʻlsa, tugun elementlari oxirgi elementga yetguncha keyingi qiymatda takrorlanadi. Ya'ni, keyingi maydoni null bo'lgan maydon .

   Ushbu qidiruv davomida himoyalangan Node ob'ektining kaliti qidirilayotganlarning kalitlari bilan taqqoslanadi:

   • agar moslik topilsa, qidiruv tugaydi va yangi tugun moslik topilgan tugunning ustiga yoziladi ( faqat uning qiymat maydoni qayta yoziladi );
   • agar hech qanday kalit moslik topilmasa, yangi tugun ushbu ro'yxatdagi oxirgi bo'ladi va oldingisi unga keyingi havolaga ega bo'ladi.

Suhbat davomida ko'pincha savol tug'iladi: ziddiyat nima ? Jadval[] massivining yacheykasi bitta elementni emas, balki ikki yoki undan ortiq zanjirni saqlaydigan holat to'qnashuv deyiladi . Oddiy hollarda, bitta jadval[] katakchasida faqat bitta element saqlangan holda , HashMap elementlariga kirish doimiy O(1) vaqt murakkabligiga ega . Ammo kerakli elementga ega bo'lgan hujayra elementlar zanjirini o'z ichiga olgan bo'lsa ( to'qnashuv ), keyin O(n) , chunki bu holda vaqt tartiblangan elementlar soniga to'g'ridan-to'g'ri proportsionaldir.

10. Takrorlovchini tushuntiring

Yuqoridagi To'plam ierarxiyasini xaritalash diagrammasida To'plam interfeysi butun ierarxiya boshlangan joy edi, lekin amalda bu unchalik emas. To'plam iterator() usuli bilan interfeysdan meros bo'lib , Iterator<E> interfeysini amalga oshiradigan ob'ektni qaytaradi . Iterator interfeysi quyidagicha ko'rinadi:

public interface Iterator <E>{

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

next() - bu usulni chaqirib, keyingi elementni olishingiz mumkin. hasNext() - keyingi element bor yoki yo'qligini va to'plamning oxirigacha yetib bormaganligini aniqlash imkonini beradi. Hali ham elementlar mavjud bo'lganda, hasNext() true ni qaytaradi . Odatda hasNext() keyingi() usulidan oldin chaqiriladi , chunki next() toʻplam oxiriga yetganda NoSuchElementExceptionni chiqaradi . remove() - Keyingi() ga oxirgi qo'ng'iroq orqali olingan elementni o'chiradi . Iteratorning maqsadi elementlarni takrorlashdir. Masalan:

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

Aslida, har bir pastadir iterator yordamida kaput ostida amalga oshiriladi. Bu haqda batafsil ma'lumotni shu yerda o'qishingiz mumkin . Ro'yxat iteratorning o'z versiyasini taqdim etadi, ammo sovuqroq va murakkabroq - ListIterator . Ushbu interfeys Iteratorni kengaytiradi va qo'shimcha usullarga ega:

• to'plamda oldingi element mavjud bo'lsa hasPrevious rost, aks holda false qaytaradi;
• oldingi joriy elementni qaytaradi va oldingisiga o'tadi; agar yo'q bo'lsa, u holda NoSuchElementException tashlanadi;
• add o'tgan ob'ektni keyingi () ga keyingi chaqiruv orqali qaytariladigan elementdan oldin kiritadi ;
• set joriy elementga o'tgan ob'ektga havolani belgilaydi;
• nextIndex keyingi elementning indeksini qaytaradi. Agar bunday narsa bo'lmasa, unda ro'yxatning o'lchami qaytariladi;
• previousIndex oldingi elementning indeksini qaytaradi. Agar yo'q bo'lsa, -1 raqami qaytariladi.

Xo'sh, bugun men uchun hammasi shu. Umid qilamanki, ushbu maqolani o'qib chiqqandan so'ng, siz o'zingizning orzuingiz - dasturchi bo'lishga yanada yaqinroq bo'lasiz.