Java dasturchisi uchun intervyudan olingan savollar va javoblarni tahlil qilish. 9-qism

Feyerverk! Dasturchi bo'lish oson emas. Siz doimo o'rganishingiz kerak, har doim yangi narsalarni o'rganishingiz kerak. Ammo, har qanday biznesda bo'lgani kabi, eng qiyin narsa - boshlash, maqsad sari birinchi qadamni qo'yishdir. Va siz ushbu saytda o'tirganingiz va ushbu maqolani o'qiyotganingiz uchun siz birinchi qadamni bajardingiz. Bu shuni anglatadiki, endi siz yo'lda sekinlashmasdan yoki o'chirmasdan maqsadingizga maqsadli harakat qilishingiz kerak. Agar men to'g'ri tushunsam, sizning maqsadingiz Java dasturchisi bo'lish yoki agar siz bo'lsangiz, bilimingizni oshirishdir. Agar shunday bo'lsa, siz to'g'ri joydasiz, chunki biz 250+ Java dasturchisi intervyu savollarining keng ro'yxatini tahlil qilishni davom ettiramiz. Davom etaylik!

To'plamlar

84. Iteratorlar va ulardan foydalanish haqida gapirib bering

To'plamlar har qanday Java dasturchi intervyusida eng sevimli mavzulardan biri bo'lib, to'plam ierarxiyasi haqida gapirganda, nomzodlar ko'pincha bu Collection interfeysidan boshlanadi deb aytishadi . Lekin bu to'g'ri emas, chunki bu interfeysning tepasida yana biri bor - Iterable . Ushbu interfeys iterator() usulini ifodalaydi , bu sizga joriy to'plam uchun Iterator ob'ektini chaqirish imkonini beradi . Va bu Iterator ob'ekti nima ? Iterator - foydalanuvchi ma'lum bir to'plamni amalga oshirishni bilishi kerak bo'lmasdan, to'plam bo'ylab harakatlanish va elementlarni takrorlash qobiliyatini ta'minlaydigan ob'ekt. Ya'ni, bu to'plam elementlariga qandaydir ko'rsatgich bo'lib, u go'yo undagi ma'lum bir joyga qaraydi. Iterator quyidagi usullarga ega:

• hasNext() - ko'rsatgichdan keyin joylashgan element mavjud bo'lsa, true qiymatini qaytaradi (bu usul to'plamning oxiriga yetib kelganligini aniqlash imkonini beradi);
• next() - ko'rsatkichdan keyingi keyingi elementni qaytaradi. Agar yo'q bo'lsa, NoSuchElementException tashlanadi . Ya'ni, ushbu usulni qo'llashdan oldin, element mavjudligiga ishonch hosil qilish yaxshiroqdir - hasNext() yordamida ;
• remove() - keyingi() usuli yordamida to'plamdan olingan oxirgi elementni olib tashlaydi . Agar next() hech qachon remove() chaqirilgunga qadar chaqirilmagan bo'lsa, istisno chiqariladi - IllegalStateException ;
• forEachRemaining(<Consumer>) - to'plamning har bir elementi bilan o'tkazilgan amalni bajaradi (usul Java 8 da paydo bo'lgan).

Quyida muhokama qilingan iterator usullari yordamida roʻyxatni takrorlash va uning barcha elementlarini olib tashlashning kichik misoli keltirilgan:

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

Konsolda ko'rsatiladi: Bu elementlarni olib tashlash muvaffaqiyatli bo'lganligini anglatadi. Bizda iterator bo'lgandan so'ng, biz barcha elementlarni ekranga chop etish usulidan foydalanishimiz mumkin:

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

Ammo bundan keyin iterator keyingi foydalanish uchun yaroqsiz bo'lib qoladi, chunki u butun ro'yxatni bosib o'tadi va oddiy iteratorda orqaga qaytish usullari yo'q. Bu erda biz asta-sekin LinkedList ga yaqinlashamiz , ya'ni uning listIterator() usuli , bu iteratorning modernizatsiya qilingan turini - ListIteratorni qaytaradi . Oddiy (standart) iterator usullaridan tashqari, buning qo'shimcha usullari mavjud:

• add(<Element>) - ro'yxatga yangi element kiritadi;
• hasPrevious() - agar ko'rsatgichdan oldin joylashgan element bo'lsa (oldingi element bor yoki yo'qmi) rost qaytaradi;
• nextIndex() - ko'rsatkichdan keyingi keyingi element ro'yxatidagi indeksni qaytaradi;
• oldingi() - oldingi elementni qaytaradi (ko'rsatgichgacha);
• oldingiIndex() - oldingi element indeksini qaytaradi;
• set(<Element>) - Keyingi() yoki oldingi() usullari bilan qaytarilgan oxirgi elementni almashtiradi .

Ko'rib turganingizdek, ushbu iteratorning funksionalligi ancha qiziqarli: u har ikki yo'nalishda harakat qilish imkonini beradi va elementlar bilan ishlashda qo'llarni bo'shatadi. Bundan tashqari, odamlar iteratorlar haqida gapirganda, ular ba'zan naqshning o'zini anglatadi. Muammoga duch kelmaslik va bu haqda ishonchli gapirish uchun Iterator naqshlari haqidagi ushbu maqolani o'qing .

85. Java Collection Framework-da kolleksiya ierarxiyasi nimadan iborat?

Java-da ikkita to'plam ierarxiyasi mavjud. Birinchi ierarxiya to'plam ierarxiyasining o'zi bo'lib , quyidagi tuzilishga ega: U, o'z navbatida, quyidagi kichik to'plamlarga bo'linadi:

• To'plam - tartibsiz noyob (takrorlanmaydigan) elementlarni o'z ichiga olgan to'plam sifatida ma'lumotlar strukturasini tavsiflovchi interfeys . Interfeysda standart ilovalar mavjud - TreeSet , HashSet va LinkedHashSet .
• Ro'yxat - ob'ektlarning tartiblangan ketma-ketligini saqlaydigan ma'lumotlar strukturasini tavsiflovchi interfeys. Roʻyxatdagi misollar ushbu toʻplamdagi indeksi boʻyicha kiritilishi va oʻchirilishi mumkin (massivga oʻxshash, lekin oʻlchamini dinamik oʻzgartirish bilan). Interfeysda standart ilovalar mavjud - ArrayList , Vector ( eskirgan va aslida ishlatilmaydi ) va LinkedList .
• Navbat - bu FIFO-Birinchi kiruvchi birinchi chiqish qoidasiga amal qiladigan navbat ko'rinishidagi elementlarni saqlaydigan ma'lumotlar strukturasini tavsiflovchi interfeys . Interfeys quyidagi standart ilovalarga ega: LinkedList (ha, u Queue-ni ham qo'llaydi ) va PriotityQueue .

To'plamlarning ikkinchi ierarxiyasi Xarita bo'lib , u quyidagi tuzilishga ega: Ushbu to'plamda pastki to'plamlarga bo'linishlar mavjud emas (chunki Xarita ierarxiyasining o'zi kichik to'plamga o'xshaydi, lekin alohida yotadi). Standart xarita ilovalari Hashtable ( eskirgan deb hisoblanadi), LinkedHashMap va TreeMap . Aslida, To'plam haqida so'ralganda , odatda ikkala ierarxiya ham nazarda tutiladi.

86. ArrayList ning ichki tuzilishi nimadan iborat?

ArrayList massivga o'xshaydi, lekin dinamik ravishda kengayish qobiliyatiga ega. Bu nima degani? Gap shundaki, ArrayList oddiy massiv asosida ishlaydi, ya'ni elementlarni ichki massivda saqlaydi (uning standart hajmi 10 katak). Ichki massiv to'la bo'lganda, yangi massiv yaratiladi, uning o'lchami formula bilan aniqlanadi:

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

Ya'ni, agar bizning massivimizning o'lchami 10 bo'lsa, yangisining o'lchami: 10 * 3 / 2 + 1 = 16. Keyin, birinchi (eski) massivdagi barcha qiymatlar unga ko'chiriladi. mahalliy System.arraycopy () usuli va birinchi massiv o'chiriladi. Aslida, ArrayList ning dinamik kengayishi shunday amalga oshiriladi . Eng ko'p qo'llaniladigan ArrayList usullarini ko'rib chiqamiz : 1. add(<Elelement>) - elementni massiv oxiriga (oxirgi bo'sh katakka) qo'shadi va avval bu massivda bo'sh joy mavjudligini tekshiradi. Agar u mavjud bo'lmasa, elementlar nusxalanadigan yangi massiv yaratiladi. Bu amalning logarifmik murakkabligi O(1) ga teng. Shunga o'xshash usul mavjud - add(<Index>,<Elelement>) . U elementni roʻyxat (massiv) oxiriga emas, balki argument sifatida kelgan indeksli maʼlum bir katakka qoʻshadi. Bunday holda, logarifmik murakkablik qayerga qo'shilganiga qarab farq qiladi:

• agar bu taxminan ro'yxatning boshi bo'lsa, logarifmik murakkablik O (N) ga yaqin bo'ladi, chunki yangisining o'ng tomonida joylashgan barcha elementlarni bitta katakchani o'ngga siljitish kerak bo'ladi;
• element o'rtaga kiritilgan bo'lsa - O(N/2), chunki biz ro'yxat elementlarining faqat yarmini bitta katakchani o'ngga siljitishimiz kerak.

Ya'ni, bu usulning logarifmik murakkabligi elementning qaerga kiritilganiga qarab O(N) dan O(1) gacha bo'ladi. 2. set(<Index>,<Elelement>) - elementni ro'yxatdagi ko'rsatilgan pozitsiyaga yozadi. Agar ushbu pozitsiyada allaqachon element mavjud bo'lsa, uning ustiga yoziladi. Bu amalning logarifmik murakkabligi O(1) ga teng, chunki siljishlar yo‘q: faqat massivdagi indeks bo‘yicha qidirish, biz eslaganimizdek, O(1) murakkabligiga ega bo‘lgan elementni yozish. 3. remove(<index>) - elementni ichki massivdagi indeksi bo'yicha olib tashlash. Ro'yxat oxirida bo'lmagan elementni o'chirishda, elementni o'chirib tashlaganingizdan so'ng qolgan bo'shliqni yopish uchun barcha elementlarni uning o'ng tomonidagi bitta katakchani chapga siljitish kerak. Shuning uchun logarifmik murakkablik qo'shish(<Index>,<Elelement>) bilan bir xil bo'ladi, agar element o'rtada bo'lsa - O(N/2) - chunki elementlarning yarmini bir chapga siljitish kerak. Shunga ko'ra, agar u boshida bo'lsa - O (N). Xo'sh, agar oxirida u O (1) bo'lsa, hech narsani ko'chirishga hojat yo'q. Ushbu mavzuni chuqurroq o'rganishni istaganlar uchun men ushbu havolani ArrayList klassi tahlili bilan maqolaga qoldiraman .

87. LinkedList ning ichki tuzilishi nimadan iborat?

Agar ArrayList ichki massivdagi elementlarni o'z ichiga olsa, u holda LinkedList ikki marta bog'langan ro'yxat shaklida bo'ladi. Bu shuni anglatadiki, har bir element oldingi elementga ( oldingi ) va keyingisiga ( keyingi ) havolani o'z ichiga oladi. Birinchi elementda avvalgisiga havola yo'q (bu birinchi), lekin u ro'yxatning boshi hisoblanadi va LinkedList to'g'ridan -to'g'ri unga havolaga ega. Oxirgi element, aslida, keyingi elementga ega emas, u ro'yxatning dumidir va shuning uchun LinkedList-ning o'zida unga to'g'ridan-to'g'ri havola mavjud . Shuning uchun, ro'yxatning boshi yoki dumiga kirishning logarifmik murakkabligi O (1) ga teng. ArrayList -da , ro'yxat kattalashganda, ichki massiv ko'paydi, ammo bu erda hamma narsa soddaroq bo'ladi - element qo'shganda, bir nechta havolalar o'zgaradi. Keling, eng ko'p ishlatiladigan LinkedlList usullarini ko'rib chiqaylik : 1. add(<Elelement>) - ro'yxatning oxiriga qo'shish, ya'ni. oxirgi elementdan keyin (5) yangi elementga havola keyingi sifatida qo'shiladi . Yangi element oldingi element sifatida oxirgi (5) ga havolaga ega bo'ladi . Bunday operatsiyaning logarifmik murakkabligi O (1) bo'ladi, chunki faqat oxirgi elementga havola kerak va siz eslayotganingizdek, quyruq LinkedList- dan to'g'ridan-to'g'ri havolaga ega va unga kirishning logarifmik murakkabligi minimaldir. 2. add(<Index>,<Elelement>) - elementni indeks bo'yicha qo'shish. Elementni, masalan, roʻyxatning oʻrtasiga qoʻshganda, avval bosh va dum qismidagi elementlar (har ikki tomonda) kerakli joy topilguncha takrorlanadi. Agar biz uchinchi va to'rtinchi (yuqoridagi rasmda) orasiga element qo'shmoqchi bo'lsak, to'g'ri joyni qidirganda, uchinchi elementning keyingi havolasi allaqachon yangisiga ishora qiladi. Yangisi uchun oldingi havola uchinchisiga ishora qiladi. Shunga ko'ra, to'rtinchi elementning havolasi - oldingi - allaqachon yangi elementga ishora qiladi va yangi elementning keyingi havolasi to'rtinchi elementga ishora qiladi: Bu usulning logarifmik murakkabligi yangi elementga berilgan indeksga bog'liq bo'ladi:

• agar u bosh yoki dumga yaqin bo'lsa, u O (1) ga yaqinlashadi, chunki aslida elementlarni takrorlash kerak bo'lmaydi;
• agar u o'rtaga yaqin bo'lsa, u holda O(N/2) - bosh va quyruqdan elementlar kerakli element topilgunga qadar bir vaqtning o'zida saralanadi.

3. set(<Index>,<Elelement>) - elementni ro'yxatdagi ko'rsatilgan pozitsiyaga yozadi. Ushbu operatsiyaning logarifmik murakkabligi elementning boshga, quyruqga yoki o'rtaga qanchalik yaqin bo'lishiga qarab, O (1) dan O (N / 2) gacha bo'ladi. 4. olib tashlash(<indeks>) - elementni ro'yxatdan o'chiradi, asosan o'chirilayotgan elementdan oldingi ( oldingi ) o'chirilgandan keyin keladigan elementga ( keyingi ) havola qiladi. Va aksincha: oʻchirilayotgan elementdan keyin keladigan element oʻchirilayotgan elementdan oldin kelgan elementga ishora qilishi uchun: Natijada indeks boʻyicha qoʻshishga teskari jarayon ( add(<Index>,<Elelement>) ). LinkedList ichki tuzilishi haqida ko'proq ma'lumot olishni istaganlar uchun ushbu maqolani o'qishni tavsiya etaman .

88. HashMapning ichki tuzilishi nimadan iborat?

Ehtimol, Java dasturchisi bilan suhbatda eng mashhur savollardan biri. HashMap v kalit-qiymat juftlari bilan ishlaydi . Ular HashMapv ichida qanday saqlanadi ? HashMap ichida bir qator tugunlar mavjud:

Node<K,V>[] table

Odatiy bo'lib, massivning o'lchami 16 ni tashkil qiladi va u har safar elementlar bilan to'ldirilganda ikki baravar ko'payadi ( LOAD_FACTOR ga erishilganda - to'liqlikning ma'lum foizi, sukut bo'yicha u 0,75 ni tashkil qiladi ). Har bir tugun kalit xeshini, kalitni, qiymatni va keyingi elementga havolani saqlaydi: Aslida, "keyingi elementga havola" biz har bir elementga havolani o'z ichiga olgan alohida bog'langan ro'yxat bilan ishlayotganimizni anglatadi. keyingisi. Ya'ni, HashMap ma'lumotlarni bir-biriga bog'langan ro'yxatlar qatorida saqlaydi. Ammo men darhol ta'kidlayman: agar jadval massivining bitta katagida bir nechta elementlardan iborat o'xshash yakka bog'langan ro'yxatga havola bo'lsa, bu yaxshi emas. Ushbu hodisa to'qnashuv deb ataladi . Lekin birinchi narsa birinchi. Keling, put usuli yordamida yangi juftlik qanday saqlanishini ko'rib chiqaylik . Birinchidan, kalitning hachCode() kodi olinadi. Shuning uchun, xashmap to'g'ri ishlashi uchun siz ushbu usul kalit sifatida bekor qilingan darslarni olishingiz kerak. Keyinchalik bu xesh-kod ichki usulda - hash() - jadval massivi o'lchamidagi raqamni aniqlash uchun ishlatiladi . Keyinchalik, olingan raqamdan foydalanib, jadval massivining ma'lum bir katagiga kirish mumkin . Bu erda ikkita holat mavjud:

1. Hujayra bo'sh - yangi tugun qiymati unda saqlanadi .
2. Hujayra bo'sh emas - kalitlarning qiymati taqqoslanadi. Agar ular teng bo'lsa, yangi tugun qiymati eskisining ustiga yoziladi, agar ular teng bo'lmasa, keyingi elementga kirish va uning kaliti bilan solishtirish ... Va shunga o'xshash yangi qiymat eskisini ustiga yozmaguncha yoki oxiriga yetguncha davom etadi. yakka bog'langan ro'yxat va u erda oxirgi element sifatida saqlanadi.

Elementni kalit ( get(<key>) usuli ) bo‘yicha qidirishda kalitning hashkodi hisoblab chiqiladi, so‘ngra hash() yordamida uning massiv ichidagi qiymati va natijada olingan raqamdan foydalanib, jadval massivining katagi topiladi. , unda qidiruv allaqachon tugunlarni sanab o'tish va kerakli tugunning kalitini joriy kalit bilan taqqoslash orqali amalga oshiriladi. Xaritada ideal vaziyatdagi amallar algoritmik murakkabligi O(1) ga ega, chunki ular massivga kirishadi va esingizda boʻlsa, elementlar sonidan qatʼiy nazar massivdagi amallar O(1) murakkablikka ega. Lekin bu ideal. Agar foydalanilayotgan massiv katakchasi bo'sh bo'lmasa (2) va u erda allaqachon ba'zi tugunlar mavjud bo'lsa, algoritmik murakkablik chiziqli O(N) ga aylanadi, chunki endi kerakli joyni topishdan oldin elementlarni takrorlash kerak. Buni eslatib o'tmasdan ilojim yo'q: Java 8 dan boshlab, agar bitta bog'langan ro'yxat tugunida 8 dan ortiq element (to'qnashuv) bo'lsa, u ikkilik daraxtga aylanadi. Bunday holda, algoritmik murakkablik endi O (N) bo'lmaydi, lekin O (log (N)) - bu boshqa masala, shunday emasmi? HashMap - bu katta mavzu va odamlar intervyularda u haqida savollar berishni yaxshi ko'radilar. Shuning uchun, men sizga uni batafsil tushunishni maslahat beraman (u tishlaringizdan sakrab tushishi uchun). Shaxsan men HashMap savollarisiz intervyu olmaganman . Ushbu maqolada HashMap- ga chuqur sho'ng'in topishingiz mumkin . Bugun hammasi shu, davomi...