JavaKolleksiyalar8 boʻlim · 23 savol

Java Collections: qanday tuzilgan va qanday ishlaydi

Bu sahifa Java Collections mavzusini chuqur tushuntiradi: kolleksiyalar qanday tuzilgan, nega aynan shunday ishlaydi va qachon qaysi birini tanlash kerak. Murakkab joylar qadamma-qadam animatsiya bilan koʻrsatilgan.

Boʻlimlar asoslardan chuqurroq mavzularga qarab ketadi. Bilgan joyingizni oʻtkazib yuborishingiz yoki istalgan boʻlimdan boshlashingiz mumkin.

Har boʻlim oxirida tushunganingizni tekshiradigan savollar bor. Avval javobni oʻzingiz oʻylab koʻring, keyin oching.

1Kolleksiyalar xaritasi

Java Collections bir nechta interfeys va ularning implementationʼlaridan iborat. Avval shu xaritani koʻrib chiqamiz: qaysi kolleksiya nimani saqlaydi va qachon qaysi birini tanlash kerak.

InterfeysNima saqlaydiKoʻp ishlatiladiganTartib
Listelementlar ketma-ketligi, takror boʻlishi mumkinArrayList, LinkedListqoʻshilgan tartib, index bor
Setfaqat unikal elementlarHashSet, LinkedHashSet, TreeSetyoʻq / insertion order / sort qilingan
Mapkalit → qiymat, kalitlar unikalHashMap, LinkedHashMap, TreeMapyoʻq / insertion order / sort qilingan
Queue, Dequenavbat: Queue — bir uchidan, Deque — ikkala uchidanArrayDeque, PriorityQueueFIFO / LIFO / priority boʻyicha

Tanlashda uchta savol beriladi: tartib kerakmi, takror elementlar boʻlishi mumkinmi va elementni nima boʻyicha qidiraman — index, qiymatning oʻzi yoki kalit. Koʻp holatda javob ArrayList, HashSet yoki HashMap boʻladi, qolganlari aniq ehtiyoj boʻlganda olinadi.

Map Collectiondan meros olmaydi, lekin keySet(), values() va entrySet() orqali kolleksiya koʻrinishidagi view beradi. Setning asosiy implementationʼlari esa Map ustiga qurilgan: HashSet — HashMap, LinkedHashSet — LinkedHashMap, TreeSet — TreeMap asosida ishlaydi.

Tushunganingizni tekshiring

List, Set va Map farqi nimada? Qachon qaysi birini tanlaysiz?Javob
Qisqa javob

List — tartibli kolleksiya: takror elementlar boʻlishi mumkin, elementni index orqali olasiz. Set — faqat unikal elementlar. Map — kalit va qiymat juftliklari, kalitlar takrorlanmaydi.

Tanlov vazifaga bogʻliq. Tartib va index kerak boʻlsa — List (koʻpincha ArrayList). Element bor-yoʻqligini tez tekshirish yoki takrorlarni olib tashlash kerak boʻlsa — Set (HashSet). Qiymatni kalit boʻyicha topish kerak boʻlsa — Map (HashMap).

Har birining tartibni saqlaydigan varianti ham bor: LinkedHashSet va LinkedHashMap insertion orderʼni saqlaydi, TreeSet va TreeMap esa elementlarni sort qilingan holda saqlaydi.

Queue, Deque va PriorityQueue qachon ishlatiladi?Javob
Qisqa javob

Queue — FIFO navbat. Deque — ikkala tomonidan ham qoʻshib-olsa boʻladigan navbat, stack sifatida ham ishlatiladi. PriorityQueue har safar eng kichik elementni (yoki comparator boʻyicha birinchisini) beradi.

Queue metodlari juft-juft: add, remove, element xato boʻlsa exception tashlaydi, offer, poll, peek esa false yoki null qaytaradi.

Stack uchun eski Stack klassi emas, ArrayDeque ishlatiladi (push, pop, peek): Stack Vectordan meros oladi va har bir metodi synchronized.

PriorityQueue binary heap asosida ishlaydi: qoʻshish va olish O(log n), eng kichigini koʻrish O(1). Lekin uni iterator bilan aylanib chiqsangiz, elementlar sort qilingan tartibda chiqmaydi.

2ArrayList va LinkedList: maʼlumot qanday saqlanadi

ArrayList elementlarni oddiy massivda saqlaydi. Massivning capacityʼsi sizeʼdan, yaʼni elementlar sonidan katta boʻlishi mumkin: boʻsh kataklar keyingi add uchun zaxira. Index boʻyicha olish shuning uchun O(1) — element manzili darhol hisoblanadi.

1/7ArrayList maʼlumotni massivda saqlaydi. Hozir capacity 4, size 3: oxirgi katak keyingi add uchun boʻsh turibdi.

Massiv toʻlsa, taxminan 1,5 baravar katta yangi massiv yaratiladi va hamma elementlar koʻchiriladi. Bu kamdan-kam boʻladi, shuning uchun oxiriga qoʻshish oʻrtacha O(1). Oʻrtadan oʻchirish yoki oʻrtaga qoʻshish esa har safar qolgan elementlarni surishni talab qiladi — O(n).

LinkedList — doubly linked list: har bir element alohida node, u oldingi va keyingi nodeʼga reference saqlaydi. Boshiga va oxiriga qoʻshish O(1), lekin n-elementga yetish uchun listni boshidan yoki oxiridan yurib chiqish kerak — O(n).

Nazariy jihatdan LinkedList oʻrtaga qoʻshishda yutadi, amalda esa deyarli har doim ArrayList tezroq: massiv xotirada ketma-ket turadi va CPU cache bilan yaxshi ishlaydi, nodeʼlar esa xotirada sochilib yotadi va har biri qoʻshimcha joy oladi. Navbat yoki stack kerak boʻlsa — ArrayDeque.

Tushunganingizni tekshiring

ArrayList va LinkedList farqi nimada?Javob
Qisqa javob

ArrayList massiv asosida ishlaydi: index boʻyicha olish O(1), oʻrtaga qoʻshish yoki oʻchirish O(n). LinkedList — doubly linked list: index boʻyicha olish O(n), boshiga va oxiriga qoʻshish O(1).

ArrayListning oʻrtasidan element oʻchirilsa, undan keyingi hamma elementlar bir katak chapga suriladi. LinkedListda nodeʼni uzib olishning oʻzi O(1), lekin oʻsha nodeʼgacha yetib borish baribir O(n).

Amalda deyarli har doim ArrayList tezroq: elementlar xotirada ketma-ket turadi va CPU cache bilan yaxshi ishlaydi. LinkedListning har bir nodeʼida esa ikkita qoʻshimcha reference va obyekt header bor. Queue yoki stack kerak boʻlsa, LinkedList oʻrniga ArrayDeque ishlatiladi.

Massiv va ArrayList farqi nima? Arrays.asListning qanday tuzogʻi bor?Javob
Qisqa javob

Massivning oʻlchami oʻzgarmaydi va unda primitivlar saqlanishi mumkin. ArrayList kerak boʻlganda kattalashadi, lekin faqat obyektlarni saqlaydi (int emas, Integer). Arrays.asList esa oʻlchami qatʼiy, massivning oʻziga bogʻlangan view qaytaradi.

Arrays.asList qaytargan listda set ishlaydi va asl massivni ham oʻzgartiradi, lekin oʻlchamni oʻzgartiradigan amallar (add, remove) UnsupportedOperationException tashlaydi.

Yana bir tuzoq: Arrays.asList(new int[]{1, 2, 3}) uch elementli list emas, bitta elementli List<int[]> qaytaradi, chunki primitiv massiv generic turga bitta obyekt boʻlib tushadi.

String[] arr = {"a", "b"};
List<String> list = Arrays.asList(arr);
list.set(0, "z");   // arr[0] ham "z" boʻladi
list.add("c");      // UnsupportedOperationException

List<String> copy = new ArrayList<>(Arrays.asList(arr)); // oʻzgartirsa boʻladigan nusxa

3HashMap qanday tuzilgan

HashMap — bucketlar massivi. Kalit qaysi bucketga tushishi uning hashCodeidan hisoblanadi: hash aralashtiriladi (h ^ (h >>> 16)) va index olinadi — (n - 1) & hash, bunda n — massiv uzunligi. Uzunlik doim ikkining darajasi, shuning uchun bu amal hashʼning oxirgi bitlarini oladi: natija hash manfiy boʻlsa ham doim 0 dan n − 1 gacha boʻlgan toʻgʻri index chiqadi, amal esa %dan tezroq.

1/88 ta bucketli boʻsh HashMap (soddalik uchun; default capacity 16). Quyidagi hash qiymatlari misol uchun olingan.

Ikki kalit bitta bucketga tushishi mumkin — bu collision. Unda nodeʼlar list boʻlib ulanadi va qidiruvda avval hash, keyin equals bilan birma-bir tekshiriladi. Bucket juda uzaysa (8 tadan koʻp node va massiv kamida 64), Java 8 dan boshlab list red-black treeʼga aylanadi va qidiruv O(log n) boʻladi.

Elementlar soni capacity × load factorʼdan oshsa (default 16 × 0,75 = 12), massiv ikki baravar kattalashadi. Bunda hash qayta hisoblanmaydi: har bir entry uchun bitta bit qaraladi va entry yo oʻz indexida qoladi, yo eski uzunlik qadar suriladi.

1/6Capacity 4, load factor 0,75 → threshold 3. Index — hashʼning oxirgi 2 biti: A va B bucket 1 da, C bucket 2 da.

HashSet ham shu mexanizm bilan ishlaydi: u HashMap ustiga qurilgan, elementlar kalit sifatida saqlanadi. Kundalik ishda Mapning ikki metodi koʻp yordam beradi: guruhlash uchun computeIfAbsent, sanash uchun merge.

Tushunganingizni tekshiring

HashMap qanday ishlaydi?Javob
Qisqa javob

HashMap bucketlar massividan iborat. Kalitning hashCodeidan bucket indexi hisoblanadi, bucket ichida esa kalit equals bilan qidiriladi. get va put oʻrtacha O(1).

put(k, v) avval hash hisoblaydi: h ^ (h >>> 16) — yuqori bitlar pastki bitlarga aralashtiriladi. Index — (n - 1) & hash, bunda n — massiv uzunligi. Bucket boʻsh boʻlsa, yangi node qoʻyiladi. Boʻsh boʻlmasa, nodeʼlar hash va equals bilan solishtiriladi: teng kalit topilsa uning qiymati almashtiriladi, topilmasa yangi node qoʻshiladi.

get(k) xuddi shu yoʻl bilan bucketni topadi va kalitni equals bilan qidiradi. hashCode yaxshi taqsimlansa, bucketlar qisqa boʻladi va qidiruv tez ishlaydi.

Ikki kalitning hash qiymati bir xil boʻlsa, HashMap ularni qanday saqlaydi?Javob
Qisqa javob

Ikkalasi bitta bucketga tushadi va u yerda list boʻlib saqlanadi. Hech biri oʻchib ketmaydi: kerakli kalitni equals topadi. Bucket juda uzayib ketsa, Java 8 dan boshlab u red-black treeʼga aylanadi.

Bu holat collision deyiladi. Hash qiymatlari har xil, lekin (n - 1) & hash bir xil chiqqan kalitlar ham bitta bucketga tushadi. Qidirishda bucketdagi nodeʼlar birma-bir hash va equals bilan tekshiriladi.

Bitta bucketga koʻp kalit tushsa, qidiruv O(n) gacha sekinlashadi. Shuning uchun bucketdagi nodeʼlar 8 tadan oshsa va massiv uzunligi kamida 64 boʻlsa, bucket treeʼga aylanadi — bu treeify deyiladi — va qidiruv O(log n) boʻladi. Massiv 64 dan kichik boʻlsa, buning oʻrniga massiv kattalashtiriladi. Resize paytida boʻlingan bucketda nodeʼlar 6 ta yoki undan kam qolsa, tree yana listga qaytadi; remove paytida esa tree juda kichrayib qolganda qaytadi.

Koʻp uchraydigan notoʻgʻri tasavvur: «eski qiymat oʻchib ketadi». Qiymat faqat kalitlar equals boʻyicha teng boʻlganda almashtiriladi.

HashMap qachon va qanday kattalashadi? Load factor nima?Javob
Qisqa javob

Elementlar soni capacity × load factorʼdan oshsa, massiv ikki baravar kattalashadi va elementlar yangi bucketlarga qayta taqsimlanadi. Default qiymatlar — capacity 16, load factor 0,75: birinchi resize 13-element qoʻshilganda boʻladi.

Load factor massiv qanchalik toʻlganda kattalashishini belgilaydi. Kichikroq qiymat collisionʼlarni kamaytiradi, lekin xotira koʻproq ketadi. 0,75 — tezlik va xotira oʻrtasidagi murosa.

Resize O(n): hamma nodeʼlar qayta joylashtiriladi. Elementlar soni oldindan maʼlum boʻlsa, mapʼni kerakli capacity bilan yaratgan maʼqul. Java 19 dan beri buning uchun HashMap.newHashMap(n) bor: u n ta elementni resizeʼsiz sigʻdiradigan capacityʼni oʻzi hisoblaydi.

// 1000 element resizeʼsiz sigʻadi
Map<String, User> byId = HashMap.newHashMap(1000);

// Java 19 dan oldin
Map<String, User> old = new HashMap<>((int) (1000 / 0.75f) + 1);
HashSet takror elementni qanday aniqlaydi?Javob
Qisqa javob

HashSet aslida HashMap ustiga qurilgan: elementlar unda kalit sifatida saqlanadi. Takrorni hashCode va equals aniqlaydi.

add(e) aslida HashMapga put(e, PRESENT) qiladi. Avval hashCode orqali bucket topiladi, keyin oʻsha bucketdagi elementlar equals bilan solishtiriladi. Teng element topilsa, yangisi qoʻshilmaydi va add false qaytaradi.

Demak, oʻzingiz yozgan klassni HashSetga qoʻshsangiz, equals va hashCodeni birga override qilish shart. Aks holda mazmunan bir xil ikki obyektning ikkalasi ham qoʻshilib ketadi.

computeIfAbsent, merge va getOrDefault qachon ishlatiladi va ularning qanday tuzoqlari bor?Javob
Qisqa javob

computeIfAbsent kalit yoʻq boʻlsa, qiymatni yaratib qoʻyadi. merge mavjud qiymatni yangisi bilan birlashtiradi — sanash uchun qulay. getOrDefault yoʻq kalit uchun default qaytaradi, lekin mapʼga hech narsa qoʻymaydi.

Odatiy misollar: guruhlash — map.computeIfAbsent(k, x -> new ArrayList<>()).add(v), sanash — map.merge(word, 1, Integer::sum).

Tuzoqlar. computeIfAbsentdagi funksiya null qaytarsa, hech narsa qoʻyilmaydi. Funksiya ichida shu mapʼning oʻzini oʻzgartirib boʻlmaydi: Java 9 dan beri HashMap buni sezsa, ConcurrentModificationException tashlaydi. mergedagi funksiya null qaytarsa, entry oʻchiriladi. getOrDefault esa kalit bor-u qiymati null boʻlsa, defaultʼni emas, nullni qaytaradi.

Map<String, List<Order>> byUser = new HashMap<>();
for (Order o : orders)
    byUser.computeIfAbsent(o.userId(), k -> new ArrayList<>()).add(o);

Map<String, Integer> counts = new HashMap<>();
for (String w : words)
    counts.merge(w, 1, Integer::sum);

4equals va hashCode kontrakti

HashMap kalitni ikki bosqichda topadi: hashCode bucketni koʻrsatadi, equals esa bucketdagi nodeʼlar orasidan kerakli kalitni ajratadi. Shuning uchun kontrakt bor: equals boʻyicha teng obyektlarning hashCodei ham teng boʻlishi shart. Teskarisi shart emas — har xil obyektlar bir xil hash berishi mumkin, bu collision.

Faqat equals override qilinsa, mazmunan teng kalitlar har xil hash beradi va map ularni topolmaydi. Faqat hashCode override qilinsa, ular bitta bucketga tushadi, lekin Object.equals ularni har xil deb hisoblaydi. Eng oson yechim — record: equals va hashCodeni kompilyator fieldʼlar boʻyicha oʻzi yozadi.

Ikkinchi tuzoq — kalitning oʻzi oʻzgarishi. Bucket put paytidagi hash boʻyicha tanlanadi va keyin qayta hisoblanmaydi. Kalit oʻzgarsa, nima boʻlishini koʻring:

1/4map.put(key, 1): key — ["a"] listi, uning hashCode() = 128. 128 & 7 = 0, entry bucket 0 ga tushadi (soddalik uchun 8 ta bucket). Hash ham nodeʼda saqlanadi.

Shuning uchun kalitlar immutable boʻlishi kerak: String, Integer yoki fieldʼlari final va oʻzi ham immutable boʻlgan klass.

Tushunganingizni tekshiring

Faqat equals override qilinsa, hashCode esa qilinmasa, HashMap qanday ishlaydi?Javob
Qisqa javob

Notoʻgʻri ishlaydi: mazmunan teng ikki kalitning hashCodei har xil chiqadi va get null qaytaradi, chunki HashMap equalsni chaqirishdan oldin saqlangan hashʼni solishtiradi. Kontrakt shuni talab qiladi: equals boʻyicha teng obyektlarning hashCodei ham teng boʻlishi kerak.

Object.hashCode() odatda har bir obyekt uchun alohida qiymat beradi. equalsni override qilib, hashCodeni qoldirib ketsangiz, new Point(1, 2) bilan qoʻyilgan qiymatni boshqa new Point(1, 2) bilan topib boʻlmaydi. HashSetda esa bir xil nuqta ikki marta saqlanib qoladi.

Teskarisi ham ishlamaydi: faqat hashCode override qilinsa, kalitlar bitta bucketga tushadi, lekin Object.equals obyektlarni faqat reference boʻyicha solishtiradi.

Eng oson yechim — record: kompilyator equals, hashCode va toStringni fieldʼlar boʻyicha oʻzi yozadi.

class Point {
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        return o instanceof Point p && p.x == x && p.y == y;
    }
    // hashCode() yoʻq
}

Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), "A");
map.get(new Point(1, 2)); // null (deyarli har doim)
HashMapda mutable obyektni kalit qilish nega xavfli?Javob
Qisqa javob

putdan keyin kalitning hashCodega taʼsir qiladigan fieldʼi oʻzgarsa, entry eski bucketda qolib ketadi. Endi get ham, containsKey ham uni topmaydi, lekin u mapʼda turaveradi.

Bucket put paytidagi hash boʻyicha tanlanadi va keyin qayta hisoblanmaydi. Kalit oʻzgargach, get yangi hash boʻyicha boshqa bucketdan qidiradi. Entry yoʻqolgandek boʻladi: uni faqat mapʼni aylanib chiqib topish mumkin, u esa xotirani band qilib turaveradi.

Shuning uchun kalitlar immutable boʻlishi kerak: String, Integer yoki fieldʼlari final va oʻzi ham immutable boʻlgan record yoki klass. record Key(List<String> parts) ham xavfli: listni tashqaridan oʻzgartirish mumkin, shuning uchun konstruktorda List.copyOf bilan nusxa olinadi.

List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, Integer> map = new HashMap<>();
map.put(key, 1);

key.add("b");         // hashCode oʻzgardi
map.get(key);         // null
map.containsKey(key); // false
map.size();           // 1 — entry hali ham mapʼda

5Tartib: Comparable, TreeMap va LinkedHashMap

Elementlar tartibini ikki yoʻl bilan berish mumkin. Comparable — klassning natural orderʼi, compareTo klassning oʻzida yoziladi (String, Integer, LocalDate). Comparator — tashqaridan beriladigan tartib: Comparator.comparing(User::age).thenComparing(User::name).

TreeMap va TreeSet — red-black tree: kalitlar doim sort qilingan, amallar O(log n). Ular elementlarni equals bilan emas, compareTo yoki berilgan Comparator bilan solishtiradi, shuning uchun tartib equals bilan mos boʻlgani maʼqul. Ularning kuchi — oraliqni va eng yaqin kalitni topish: floorKey, ceilingKey, subMap.

LinkedHashMap — HashMap va entryʼlarni bogʻlab turadigan doubly linked list. Odatda insertion orderʼni saqlaydi, accessOrder = true bilan esa access orderʼni: har bir get entryʼni oxirga suradi. Bu LRU cache uchun tayyor asos:

1/7new LinkedHashMap<>(16, 0.75f, true) — oxirgi argument accessOrder. Birinchi argument 16 — hash jadvalning capacityʼsi. removeEldestEntry esa size cache limiti 3 dan oshganda eng eski entryʼni oʻchiradi.

Java 21 da tartibli kolleksiyalarga umumiy API qoʻshildi — sequenced collections: getFirst(), getLast(), reversed() va boshqalar.

Tushunganingizni tekshiring

Comparable va Comparator farqi nima?Javob
Qisqa javob

Comparable klassning natural orderʼini belgilaydi: compareTo klassning oʻzida yoziladi. Comparator — tashqaridan beriladigan tartib, bitta klass uchun bir nechta boʻlishi mumkin.

String, Integer, LocalDate Comparableni implement qiladi. Boshqa tartib kerak boʻlsa, masalan foydalanuvchilarni avval yoshi, keyin ismi boʻyicha sort qilish uchun, Comparator yoziladi: Comparator.comparing(User::age).thenComparing(User::name).

TreeSet va TreeMap elementlarni equals bilan emas, compareTo yoki compare bilan solishtiradi. Ikki element uchun natija 0 chiqsa, ikkinchisi takror hisoblanadi va qoʻshilmaydi. Shuning uchun tartib equals bilan mos boʻlgani maʼqul.

record User(String name, int age) {}

Set<User> byAge = new TreeSet<>(Comparator.comparingInt(User::age));
byAge.add(new User("Ali", 25));
byAge.add(new User("Vali", 25)); // qoʻshilmaydi: compare() 0 qaytardi
TreeMap va LinkedHashMap farqi nimada?Javob
Qisqa javob

LinkedHashMap insertion orderʼni (yoki access orderʼni) saqlaydi, amallar O(1). TreeMap kalitlarni sort qilingan holda saqlaydi, amallar O(log n), lekin u oraliqni va eng yaqin kalitni topa oladi.

LinkedHashMap — HashMapning hamma entryʼlarni bogʻlab turadigan doubly linked list qoʻshilgan koʻrinishi. Aylanib chiqqanda entryʼlar qoʻshilgan tartibda keladi.

TreeMap — red-black tree. Unda firstKey, floorKey, ceilingKey, headMap, subMap kabi metodlar bor: masalan, «shu vaqtgacha boʻlgan oxirgi narx» yoki «10 dan 20 gacha boʻlgan kalitlar». HashMapda buning uchun butun mapʼni aylanib chiqish kerak boʻladi.

LRU cache yozish uchun qaysi kolleksiya eng qulay?Javob
Qisqa javob

LinkedHashMap. Konstruktorda accessOrder = true berilsa, har bir get entryʼni oxirga suradi, removeEldestEntry esa hajm capacityʼdan oshganda eng eski entryʼni oʻchiradi. Hamma amal O(1).

LRU (least recently used) — joy tugaganda eng uzoq vaqt ishlatilmagan entry chiqarib tashlanadi. accessOrder = true boʻlsa, boshida eng eski, oxirida eng oxirgi ishlatilgan entry turadi.

Bu yechim thread-safe emas. Uni Collections.synchronizedMap bilan oʻrash mumkin, lekin real loyihalarda odatda tayyor kutubxona, masalan Caffeine ishlatiladi. Tushunish uchun uni LinkedHashMapsiz — HashMap va oʻzingiz yozgan doubly linked list bilan yozib koʻrish foydali.

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(16, 0.75f, true); // accessOrder: get ham tartibni yangilaydi
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
Java 21 dagi sequenced collections nima beradi?Javob
Qisqa javob

Birinchi va oxirgi element bilan ishlash uchun umumiy interfeyslar. SequencedCollection va SequencedSetda getFirst(), getLast(), addFirst(), removeLast() va reversed() bor, SequencedMapda esa firstEntry(), lastEntry(), pollFirstEntry(), putLast() va reversed().

Ilgari bu har bir kolleksiyada har xil edi: Listda list.get(list.size() - 1), Dequeda getLast(), LinkedHashSetda esa oxirgi elementni olishning qulay yoʻli umuman yoʻq edi — butun setʼni aylanib chiqish kerak edi.

Endi List, Deque, LinkedHashSet va SortedSet umumiy SequencedCollection APIʼsi orqali, LinkedHashMap va SortedMap esa SequencedMap orqali ishlaydi. reversed() nusxa emas, view qaytaradi: teskari tartibda aylanib chiqish uchun qoʻshimcha xotira ketmaydi.

6Kolleksiyani oʻzgartirish: iterator va immutable listlar

for-each sikli aslida iterator orqali ishlaydi. ArrayList va HashMap iteratorlari fail-fast: aylanib chiqish paytida kolleksiya chetdan strukturaviy oʻzgarsa (element qoʻshilsa yoki oʻchirilsa), keyingi next() exception tashlaydi. set(i, x) kabi qiymatni almashtirish strukturani oʻzgartirmaydi. Buni modCount hisoblagichi orqali bilishadi:

1/6for (String s : list) aslida iterator yaratadi. U listning modCountini eslab qoladi: expectedModCount = 4 (list 4 ta add bilan toʻldirilgan).

Toʻgʻri yoʻllar: iterator.remove(), list.removeIf(...) yoki kerakli elementlarni yangi listga yigʻish. Fail-fast tekshiruvi kafolat emas, xatoni erta topish uchun: masalan, oxiridan oldingi elementni oʻchirsangiz, exception chiqmay qolishi mumkin. Concurrent kolleksiyalarning iteratorlari esa exception tashlamaydi — ular boshqacha ishlaydi (keyingi boʻlimda).

Oʻzgarmaydigan listlar ham ikki xil. Collections.unmodifiableList — asl list ustidagi «faqat oʻqish uchun» view: asl list oʻzgarsa, view ham oʻzgaradi. List.of va List.copyOf esa haqiqiy immutable list yaratadi va null qabul qilmaydi. Ikkala holatda ham immutability sayoz: ichidagi obyektlar mutable boʻlsa, ularni oʻzgartirish mumkin.

Tushunganingizni tekshiring

for-each sikli ichida listdan element oʻchirsangiz, nima boʻladi?Javob
Qisqa javob

Odatda ConcurrentModificationException chiqadi: for-each aslida iterator orqali ishlaydi, list.remove esa listni iteratorni chetlab oʻzgartiradi. Toʻgʻri yoʻl — iterator.remove() yoki list.removeIf(...).

ArrayList har bir strukturaviy oʻzgarishda modCount hisoblagichini oshiradi. Iterator yaratilganda shu qiymatni eslab qoladi va har next()da tekshiradi. Qiymat mos kelmasa — ConcurrentModificationException. Bunday iterator fail-fast deyiladi.

Nomiga qaramay, bu exception bitta thread ichida ham chiqadi: gap threadʼlarda emas, listning iteratordan tashqarida oʻzgarishida.

Qiziq holat: oxiridan oldingi elementni oʻchirsangiz, exception chiqmaydi. List qisqargani uchun hasNext() false qaytaradi va sikl jimgina tugaydi — oxirgi element tekshirilmay qoladi.

for (String s : list) {
    if (s.isEmpty()) list.remove(s);  // ConcurrentModificationException
}

list.removeIf(String::isEmpty);        // toʻgʻri

Iterator<String> it = list.iterator(); // yoki iterator orqali
while (it.hasNext()) {
    if (it.next().isEmpty()) it.remove();
}
List.of() bilan Collections.unmodifiableList() farqi nimada?Javob
Qisqa javob

Collections.unmodifiableList — asl list ustidagi «faqat oʻqish uchun» view: asl list oʻzgarsa, view ham oʻzgaradi. List.of esa haqiqiy immutable list yaratadi va nullga ruxsat bermaydi.

Ikkalasida ham add, set, remove UnsupportedOperationException tashlaydi. Farq asl maʼlumotda: view orqasida hali ham oʻzgaradigan list turadi.

List.ofga null element berib boʻlmaydi, hatto contains(null) ham NullPointerException tashlaydi. Mavjud listdan immutable nusxa kerak boʻlsa — List.copyOf. Java 16 dagi stream.toList() ham oʻzgarmaydigan list qaytaradi, lekin nullga ruxsat beradi.

Immutability faqat shallow: listni oʻzgartirib boʻlmaydi, lekin ichidagi obyektlar mutable boʻlsa, ularning oʻzini oʻzgartirish mumkin.

List<String> src = new ArrayList<>(List.of("a"));
List<String> view = Collections.unmodifiableList(src);
List<String> copy = List.copyOf(src);

src.add("b");
view.size(); // 2 — view asl listdagi oʻzgarishni koʻradi
copy.size(); // 1

7Bir nechta thread bilan ishlash

Oddiy HashMap va ArrayList thread-safe emas. Eski yechim — Hashtable yoki Collections.synchronizedMap: har bir metod butun mapʼni bitta lock bilan yopadi, shuning uchun threadʼlar bir-birini kutadi.

ConcurrentHashMap (Java 8+) boshqacha ishlaydi: boʻsh bucketga CAS bilan yozadi, band bucketda faqat oʻsha bucketning birinchi nodeʼini lock qiladi, oʻqish esa deyarli lockʼsiz. Har xil bucketlarga yozayotgan threadʼlar bir-birini kutmaydi:

1/4Uch thread bir vaqtda uch xil kalitga yozmoqchi: T1 → bucket 0, T2 → bucket 2, T3 → bucket 4.

Har bir metod thread-safe boʻlsa ham, ularning ketma-ketligi atomik emas: if (!map.containsKey(k)) map.put(k, v) ikki thread uchun baribir xato. Buning uchun atomik metodlar bor — putIfAbsent, computeIfAbsent, merge.

CopyOnWriteArrayList — boshqa yondashuv: har bir yozish butun massivni nusxalaydi, oʻqish va aylanib chiqish esa lockʼsiz. Oʻqish koʻp, yozish kam boʻlgan joyda (masalan, listenerʼlar roʻyxati) qulay.

Tushunganingizni tekshiring

ConcurrentHashMap qanday ishlaydi? Hashtable va synchronizedMapdan nimasi bilan farq qiladi?Javob
Qisqa javob

Hashtable va synchronizedMap butun mapʼni bitta lock bilan yopadi. ConcurrentHashMap (Java 8+) esa boʻsh bucketga CAS bilan yozadi, band bucketda faqat oʻsha bucketning birinchi nodeʼini lock qiladi, oʻqish esa deyarli lockʼsiz.

Natijada har xil bucketlarga yozayotgan threadʼlar bir-birini kutmaydi. Java 7 va undan oldin map segmentlarga boʻlingan edi (default 16 ta), Java 8 da segmentlar olib tashlandi. Uzun bucketlar HashMapdagidek treeʼga aylanadi.

size() alohida hisoblagichlar yigʻindisidan olinadi, shuning uchun parallel yozish paytida u taxminiy. null kalit ham, null qiymat ham taqiqlangan: aks holda get qaytargan null «kalit yoʻq» degani yoki «qiymat null» degani ekanini ajratib boʻlmasdi.

Iteratorlari weakly consistent: ConcurrentModificationException tashlamaydi.

if (!map.containsKey(k)) map.put(k, v) nega ConcurrentHashMapda ham xato?Javob
Qisqa javob

Har bir metod alohida thread-safe, lekin ikkalasi birgalikda atomik emas: ikki thread bir vaqtda containsKeydan false olib, ikkalasi ham put qilishi mumkin. Buning uchun atomik metodlar bor: putIfAbsent, computeIfAbsent, merge, compute.

Bu «check-then-act» race condition. ConcurrentHashMapdagi computeIfAbsent toʻliq atomik: kalit yoʻq boʻlsa, funksiya bir marta chaqiriladi va natija qoʻyiladi. Sanash uchun map.merge(key, 1L, Long::sum) yoki qiymati LongAdder boʻlgan map ishlatiladi.

Ehtiyot boʻlish kerak: compute va computeIfAbsentdagi funksiya bucket lock ostida ishlaydi. U uzoq ishlasa, boshqa threadʼlarni toʻsib qoʻyadi. Funksiya ichida shu mapʼning boshqa entryʼlarini oʻzgartirish mumkin emas: bu IllegalStateExceptionga, osilib qolishga yoki deadlockʼga olib kelishi mumkin, baʼzan esa jimgina ishlagandek koʻrinadi.

// xato: ikki thread ikkalasi ham put qilishi mumkin
if (!sessions.containsKey(id)) sessions.put(id, new Session(id));

// toʻgʻri: atomik
Session s = sessions.computeIfAbsent(id, Session::new);
CopyOnWriteArrayListni qachon ishlatish kerak?Javob
Qisqa javob

Oʻqish juda koʻp, yozish esa kam boʻlganda. Har bir yozish butun massivni nusxalaydi, oʻqish va aylanib chiqish esa lockʼsiz. Klassik misol — listenerʼlar roʻyxati.

add yoki remove har safar yangi massiv yaratadi: n elementli listga yozish O(n). Iterator yaratilgan paytdagi massivni aylanib chiqadi, shuning uchun ConcurrentModificationException tashlamaydi, lekin keyingi oʻzgarishlarni koʻrmaydi va iterator.remove()ni qoʻllab-quvvatlamaydi.

Tez-tez yoziladigan yoki katta list uchun yomon tanlov: xotira va CPU nusxalashga ketadi. Bunday holda ConcurrentLinkedQueue, ConcurrentHashMap yoki lock bilan himoyalangan oddiy ArrayList mosroq.

8Katta hajm va real vazifalar

Million elementda kolleksiya tanlovi xotiraga sezilarli taʼsir qiladi. Asosiy sabab — boxing: List<Integer>dagi har bir son alohida obyekt, ustiga unga reference. Taxminiy hisob (64-bit JVM, compressed oops):

1/4int[]: har bir son 4 bayt — 1 million son ≈ 4 MB.

Hajm maʼlum boʻlsa, capacityʼni oldindan bering (new ArrayList<>(n), HashMap.newHashMap(n)). Kalitlar enum boʻlsa — EnumMap va EnumSet. Millionlab primitiv uchun — oddiy massiv yoki fastutil, Eclipse Collections kabi primitiv kolleksiyalar.

Amalda koʻpincha shunday vazifalar uchraydi: «eventʼlar oqimidan eng koʻp uchragan N tasini top», «cacheʼdan muddati oʻtgan entryʼlarni tez oʻchir». Bunday vazifalarda toʻgʻri kolleksiyani tanlash va murakkablikni asoslab berish muhim.

Tushunganingizni tekshiring

Katta hajmdagi maʼlumotda kolleksiyalar qancha xotira oladi? Nimaga eʼtibor berasiz?Javob
Qisqa javob

Eng katta xarajat — boxing va obyekt headerʼlari: List<Integer>dagi har bir son alohida obyekt. Million elementda bu int[]ga qaraganda bir necha baravar koʻp xotira degani. Capacityʼni oldindan berish va primitiv kolleksiyalar yordam beradi.

64-bit JVMda (compressed oops bilan) Integer obyekti taxminan 16 bayt, listdagi reference yana 4 bayt; int[]da esa bitta son 4 bayt. HashMapning har bir entryʼsi alohida Node obyekti (taxminan 32 bayt), ustiga kalit va qiymat obyektlari. LinkedListning har bir nodeʼi taxminan 24 bayt qoʻshimcha.

Amalda: hajm maʼlum boʻlsa, new ArrayList<>(n) va HashMap.newHashMap(n) — qayta koʻchirish boʻlmaydi. Kalitlar enum boʻlsa — EnumMap va EnumSet, ular massiv va bit mask asosida ishlaydi. Millionlab primitiv uchun — oddiy massiv yoki fastutil, Eclipse Collections kabi primitiv kolleksiyalar.

Integer cache -128…127 oraligʻidagi qiymatlarni qayta ishlatadi. Bu oraliqdan tashqarida har bir boxing yangi obyekt yaratishi mumkin, bu esa GC yukini oshiradi.

Millionlab eventʼlar oqimidan eng koʻp uchragan N tasini qanday topasiz?Javob
Qisqa javob

Avval HashMap bilan sanaladi, keyin N oʻlchamli min-heap (PriorityQueue) bilan eng kattalari tanlab olinadi. Event turlari m ta boʻlsa, tanlash O(m log N), hammasini sort qilish esa O(m log m).

Heapʼda doim eng yaxshi N tasi turadi, eng kichigi tepada. Har bir yangi entry qoʻshiladi va heap N tadan oshsa, tepadagisi chiqarib tashlanadi. N kichik boʻlsa, bu sort qilishdan ancha tez. Xotirada esa sanash uchun m ta entryʼli map va N+1 elementli heap turadi.

Masalani murakkablashtirish mumkin: kalitlar xotiraga sigʻmasa (hash boʻyicha boʻlaklarga boʻlish yoki Count-Min Sketch kabi taxminiy tuzilmalar), oqim cheksiz boʻlsa (vaqt oynasi boʻyicha sanash).

Map<String, Long> counts = new HashMap<>();
for (String e : events) counts.merge(e, 1L, Long::sum);

PriorityQueue<Map.Entry<String, Long>> top =
        new PriorityQueue<>(Map.Entry.comparingByValue());
for (Map.Entry<String, Long> en : counts.entrySet()) {
    top.offer(en);
    if (top.size() > n) top.poll(); // eng kichigini chiqaramiz
}
Cacheʼdan muddati oʻtgan entryʼlarni qanday tez oʻchirasiz?Javob
Qisqa javob

Hamma entryʼning yashash muddati bir xil boʻlsa — insertion order rejimidagi LinkedHashMap: eng eskilari boshida turadi, boshidan muddati oʻtganlarini oʻchirib, birinchi yangi entryʼda toʻxtash kifoya. Muddatlar har xil boʻlsa — tugash vaqti boʻyicha PriorityQueue.

Butun mapʼni har safar aylanib chiqish O(n). Insertion order saqlansa, faqat haqiqatan eskirganlar koʻriladi: O(k), bunda k — oʻchiriladigan entryʼlar soni.

Muddatlar har xil boʻlsa, entryʼlar tugash vaqti boʻyicha min-heapʼga qoʻyiladi va tepadagisi eng birinchi eskiradigani boʻladi. Bir nechta thread uchun DelayQueue bor. Real loyihada bu ishni odatda Caffeine kabi kutubxona qiladi: TTL, hajm cheklovi va statistika tayyor.

Muhim nuqta: insertion order rejimidagi LinkedHashMapda mavjud kalitga qayta put qilinsa, entry oxirga surilmaydi, eski joyida qoladi. Buning uchun avval remove, keyin put qilinadi yoki Java 21 dagi putLast ishlatiladi.

record Entry(String value, long expiresAt) {}
Map<String, Entry> cache = new LinkedHashMap<>();

void evictExpired(long now) {
    Iterator<Entry> it = cache.values().iterator();
    while (it.hasNext()) {
        if (it.next().expiresAt() > now) break; // qolganlari yangiroq
        it.remove();
    }
}

Tushunganingizni suhbatda sinab koʻring

Mavzuli mock intervyuda «Kolleksiyalar»ni tanlang. AI shu kabi savollarni beradi, javobingizga qarab chuqurroq savol soʻraydi va har javobingizga fikr bildiradi.

Mock intervyuni boshlash