Data Structure Haqida

· 5 min read

Kodni qanchalik chiroyli yozmang, agar noto'g'ri Data Structure (Ma'lumotlar strukturasi) tanlasangiz, loyihangiz katta yuklama (production) ostida baribir crash bo'ladi. Ko'pchilik bularni shunchaki intervyu uchun yodlaydi, lekin bugun biz Java (va umuman back-end) dunyosida har kuni ishlatadigan eng asosiy strukturalarning ichki mexanikasini (under the hood) ko'rib chiqamiz.

Array (Massiv) - Xotiradagi harbiy intizom

Hamma narsaning boshlanishi bu Array. U eng sodda, lekin eng fundamental struktura. Array bu xotiradan ketma-ket (contiguous memory) ajratilgan, o'lchami oldindan aniq bo'lgan uychalar zanjiridir.

Tasavvur qiling, siz poyezddan ketma-ket joylashgan 5 ta kupe sotib oldingiz. 3-kupega borish uchun to'g'ri o'sha yerga qadam bosa olasiz (Random Access).

Xotira manzili: [1001] [1002] [1003] [1004] [1005]
Elementlar:     [ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]
Index:            0      1      2      3      4
  • Nega tez? Arraydan element qidirish (agar indexi ma'lum bo'lsa) $O(1)$ vaqt oladi. Matematika oddiy: Boshlang'ich_Manzil + (Index * Element_Hajmi). CPU srazi manzilni topadi.
  • Nega sekin? Uning o'lchami qat'iy fixed o'zgarmas. Agar 5 talik Arrayga 6-elementni qo'shmoqchi bo'lsangiz tizim bunga ruxsat bermaydi. Yangi kattaroq Array ochib eskisini unga nusxalashingiz kerak.

ArrayList - qlli va rezinka array

Java'da eng ko'p ishlatadiganimiz ArrayList. Arrayning o'lchami cheklangan bo'lsa, ArrayList qanday qilib cheksiz element qabul qiladi?

Siz ArrayList yaratganingizda u orqa fonda default holatda 10 talik oddiy Array ochadi. Unga element qo'shib boraverasiz. Qachonki ichidagi Array to'lib qolsa load factor 100% bo'lsa ArrayList sahna ortida quyidagi ishlarni bajaradi:
1. Eskisidan 1.5 baravar katta yangi Array ochadi (New_Size = Old_Size + (Old_Size >> 1)).
2. System.arraycopy() yordamida eski elementlarni yangisiga ko'chiradi.
3. Eski Arrayni Garbage Collector (GC) ixtiyoriga topshiradi.

  • Katta xato (Misol): Agar siz bazadan 1 millionta ma'lumotni ArrayList'ga o'qib olmoqchi bo'lsangiz va uning boshlang'ich hajmini (Capacity) bermasangiz, ArrayList yo'l-yo'lakay o'nlab marta o'lchamini kattalashtirib, elementlarni nusxalab, CPU va xotirani charchatib yuboradi.

LinkedList - erkinlikni sevuvchilar uchun

ArrayList elementlarni ketma-ket saqlasa LinkedList bunga tupurgan! U xotiraning xohlagan bo'sh burchagiga elementlarni sochib tashlaydi.

LinkedList elementlari bir-birini xotira manzili (pointer/reference) orqali taniydi. Bitta element o'zida qiymatni va keyingi element qayerda yotganini saqlaydi.

[Node 1]           [Node 2]          [Node 3]
| Data: "A" |  -> | Data: "B" | ->  | Data: "C" |
| Next: 105 |     | Next: 302 |     | Next: null|
  • Plyus tomoni: Ro'yxatning boshiga yoki o'rtasiga element qo'shish (Insert) juda oson ($O(1)$). Hech narsani surish shart emas, shunchaki qo'shni Node'larning next pointerini yangi elementga burib qo'ysangiz bo'ldi.
  • Minus tomoni: Unda index yo'q! 500-elementni topish uchun 1-elementdan boshlab zanjir bo'ylab 500 marta yurib chiqishingiz shart ($O(n)$).

HashMap

Backend tizimlarda Key-Value kalit-qiymat juftligi bilan ishlash uchun eng sevimli strukturamiz bu HashMap. U qanday qilib millionlab ma'lumot ichidan siz so'ragan kalitni ko'z ochib yumguncha ($O(1)$ vaqtda) topib beradi?
Asosiy sir: Hashing funksiyasi va ichkarida yashirin yotgan Array!

Siz map.put("user_27", "Abdukarim") deganingizda:
1. Tizim "user_27" kalitining hashCode() funksiyasini chaqirib, uni raqamga o'giradi (Masalan: 45721).
2. Bu raqamni ichki Array o'lchamiga moslab (Bucket index) bo'ladi (Masalan: 45721 % 16 = Index 9).
3. O'sha ichki Arrayning 9-indexiga borib, qiymatni joylashtiradi.

"Collision" (To'qnashuv) nima?

Agar ikkita mutlaqo boshqa kalitning hashCodei bir xil indexni ko'rsatib qolsa masalan, ikkalasi ham 9-indexga tushsa, nima bo'ladi? Buni Collision deyiladi.
* Java buni aqllilik bilan yechadi: Arrayning o'sha katagida LinkedList ochadi.
* Agar collision'lar soni bitta katakda 8 tadan oshib ketsa, LinkedList avtomatik ravishda Red-Black Tree (Daraxt) strukturasiga aylanadi. Bu esa qidiruv tezligini yomon holatda ham $O(\log n)$ da ushlab turadi.

Set (HashSet)

Dasturda takrorlanmaydigan (unique) elementlarni saqlash kerak bo'lsa, Set yordamga keladi. Lekin sizga bir sirni ochaymi? HashSet aslida mustaqil data structure emas!

Shocking Truth 🤯: HashSet — bu orqa fonda oddiygina HashMapni ishlatadigan soxta structure.

Siz set.add("Golang") deganingizda, HashSet ichkarida shunchaki map.put("Golang", PRESENT) kodini ishlatadi (bu yerda PRESENT shunchaki bitta soxta Object). Ya'ni, siz qo'shgan element HashMap'ga Kalit (Key) sifatida yoziladi. Kalitlar esa HashMap'da hech qachon takrorlanishi mumkin emas! Mana Set'dagi unikallik qayerdan keladi.

Cheat Sheet: Qaysi birini qachon ishlatamiz?

Suhbatlarda va real loyihalarda adashmaslik uchun mana bu jadvalni Obsidian'ga yoki ikkinchi miyangizga saqlab qo'ying:

Data Structure Qidirish (Search) Qo'shish (Insert) Qachon ishlatish kerak?
Array $O(1)$ (index bilan) $O(n)$ Ma'lumot soni aniq va o'zgarmas bo'lsa.
ArrayList $O(1)$ (index bilan) $O(1)$ (amortized) Elementlar tez-tez o'qilganda va oxiriga qo'shilganda.
LinkedList $O(n)$ $O(1)$ Ro'yxat boshiga/o'rtasiga tinimsiz element qo'shib/o'chirilganda.
HashMap $O(1)$ $O(1)$ Tezkor Key-Value qidiruv tizimlarida (Keshlar, ID bo'yicha topish).
HashSet $O(1)$ $O(1)$ Faqat elementning bor-yo'qligini (unikalligini) tekshirishda.

Ko'rib turganingizdek, dasturlashda sehr-jodu yo'q. Faqat xotirani to'g'ri boshqarish va matematika bor. Yaxshi backend muhandisi har bir strukturaning "yaxshi va yomon" tomonini bilib, joyiga qarab qaror qabul qiladi.

Dasturchi do'stim, senga bir savol: Agar senga buyurtmalar ro'yxati berilsa va ularni tez-tez o'chirish hamda yangisini qo'shish kerak bo'lsa, lekin deyarli hech qachon index bo'yicha qidirilmasa, qaysi strukturani tanlagan bo'larding?

Post yoqqan bo'lsa, ulashishni unutmang 😊

back to blogs