3.5-bob: Hash Table / Map

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 5-mavzu

1. Kirish va motivatsiya

3.1-bobda bir necha marta "Set/Map bilan O(n²) ni O(n) ga tushiramiz" dedik. Endi savol: Map ichkarida qanday qilib O(1) qidiruvni ta'minlaydi? Massivda element qidirish O(n) 3.2-bob, lekin Map'da get/has deyarli darrov. Bu sehrning ortida Hash Table turadi.

Hash Table (yoki hash map) — kalit-qiymat juftliklarini saqlovchi va o'rtacha O(1) da qidirish/qo'shish/o'chirishni ta'minlovchi tuzilma. 2.9-bobda JS'ning Map va Objectini ishlatdik — ular ichkarida aynan Hash Table. Bu bobda uning mexanizmini (hash funksiya, kolliziya) ochamiz.

O'xshatish: kutubxonani tasavvur qiling. Kitobni topish uchun har javonni ko'rib chiqsangiz — O(n) (sekin). Lekin agar kitob nomidan maxsus formula bilan aniq javon raqamini hisoblab chiqarsangiz — to'g'ridan-to'g'ri o'sha javonga borasiz — O(1)! Hash funksiya — aynan shu "nom joy" formulasi.

Nega muhim?

• Eng ko'p ishlatiladigan tuzilma: cache (5.21: Redis), DB indeks 6.3-bob, deduplikatsiya, chastota sanash 3.2-bob.
• "Nega Map O(1)?" — intervyu savoli; mexanizmni bilish kerak.
• Kolliziya, hash funksiya — tizim dizayni 15.7-bob va xavfsizlik (14) uchun muhim.

2. Nazariya — chuqur tushuntirish

2.1. Asosiy g'oya: kalit indeks

Hash Table ichkarida oddiy massiv 3.2-bob bor. Sirq shundaki: kalitni to'g'ridan-to'g'ri massiv indeksiga aylantiramiz — hash funksiya orqali:

  kalit "ism"  ──[hash funksiya]──▶  3     massiv[3] ga saqlash
  kalit "yosh" ──[hash funksiya]──▶  7     massiv[7] ga saqlash

  Indeks:  0    1    2    3        4    5    6    7
         ┌────┬────┬────┬────────┬────┬────┬────┬────────┐
         │    │    │    │ "Ali"  │    │    │    │ 19     │
         └────┴────┴────┴────────┴────┴────┴────┴────────┘
  get("ism")  hash("ism")=3  massiv[3]  "Ali"  (DARROV, O(1)!)

Murojaat massiv indeksi orqali (O(1) — 3.2) bo'lgani uchun, qidiruv ham O(1).

2.2. Hash funksiya nima?

Hash funksiya — istalgan kalitni (matn, son) belgilangan oraliqdagi songa (indeks) aylantiruvchi funksiya. Xususiyatlari:

1. Determinik — bir xil kalit doim bir xil indeks 0.6-bob.
2. Tez — O(1) hisoblanadi.
3. Bir tekis taqsimot — kalitlarni massiv bo'ylab teng tarqatadi (kolliziya kam).

// Oddiy hash funksiya (matn  indeks)
function hash(kalit, hajm) {
  let yigindi = 0;
  for (const ch of kalit) {
    yigindi += ch.charCodeAt(0);   // har harf kodi (0.1: ASCII/UTF-8)
  }
  return yigindi % hajm;            // massiv hajmiga "o'rab" (qoldiq — 0.6)
}
hash("ism", 10);   // masalan 3

% hajm (modul): natija doim 0..hajm-1 oralig'ida bo'lishini ta'minlaydi — massiv chegarasiga sig'adi (0.1, 0.6: FizzBuzz'dagi %).

2.3. Kolliziya (collision) — muammo

Kolliziya — ikki har xil kalit bir xil indeksga tushishi. Bu muqarrar (cheksiz kalit, cheklangan massiv — "pigeonhole" prinsipi):

  hash("ism")  = 3
  hash("til")  = 3    KOLLIZIYA! ikkalasi ham 3-indeksga

Kolliziyani hal qilishning ikki asosiy usuli bor.

2.4. Kolliziya yechimi 1: Chaining (zanjir)

Har indeksda bitta qiymat emas, ro'yxat (Linked List — 3.3 yoki massiv) saqlanadi:

  Indeks 3:  [("ism","Ali"), ("til","uz")]    bir indeksda ro'yxat
  get("til")  hash=3  ro'yxatda "til"ni qidir  "uz"

// Chaining: har bucket — juftliklar massivi
class HashTable {
  constructor(hajm = 16) { this.buckets = Array.from({ length: hajm }, () => []); }
  set(kalit, qiymat) {
    const i = hash(kalit, this.buckets.length);
    const bucket = this.buckets[i];
    const juft = bucket.find(([k]) => k === kalit);   // bor bo'lsa yangila
    if (juft) juft[1] = qiymat;
    else bucket.push([kalit, qiymat]);                 // yo'q bo'lsa qo'sh
  }
}

Murakkablik: kolliziya kam bo'lsa — ro'yxatlar qisqa — O(1). Lekin hammasi bir indeksga tushsa (yomon hash yoki hujum) — O(n) (3.1: worst case). Shuning uchun yaxshi hash funksiya muhim.

2.5. Kolliziya yechimi 2: Open addressing

Indeks band bo'lsa, keyingi bo'sh joyni qidirish (linear probing):

  hash("til")=3, lekin 3 band  4 ni sina  bo'sh  massiv[4] ga

JS'ning Mapi ichkarida murakkab usullarni ishlatadi; bu g'oyalarni bilish kifoya.

2.6. Load factor va resizing

Load factor = elementlar soni / massiv hajmi. U katta bo'lsa (masalan > 0.75) — kolliziyalar ko'payadi, sekinlashadi. Yechim: massivni kattalashtirish (resize) va hammani qayta hash qilish:

  16 katakdan 12 tasi band (load = 0.75)  32 katakka kengaytir  qayta hash

Resize — O(n) (bir martalik), lekin amortized (taqsimlangan) O(1) saqlaydi. JS Map buni avtomatik qiladi.

2.7. Hash Table vs boshqa tuzilmalar

Hash Table cheklovi: tartib yo'q (kalitlar tartibsiz). Tartiblangan kerak bo'lsa — BST 3.6-bob. JS'da Map qo'shilish tartibini saqlaydi 2.9-bob, lekin "saralangan" emas.

2.8. JS'da: Object vs Map (2.9 takror)

• Object — kalit faqat string/symbol; JSON bilan; sobit struktura 2.8-bob.
• Map — har qanday kalit; .size; tez qo'shish/o'chirish; tartib saqlanadi 2.9-bob.

Ikkalasi ham ichkarida Hash Table. Kalitlar dinamik/ko'p o'zgaradigan bo'lsa — Map 2.9-bob.

3. Sintaksis — tez ma'lumotnoma

HASH FUNKSIYA:  kalit  son  % hajm  indeks (0..hajm-1)
KOLLIZIYA:      bir indeksga ikki kalit  chaining (ro'yxat) yoki probing
LOAD FACTOR:    band/hajm; > 0.75  resize (qayta hash)
MURAKKABLIK:    o'rtacha O(1), worst O(n) (yomon hash/kolliziya)
JS:             Map (har kalit, .size), Object (string kalit, JSON)

4. Batafsil kod namunalari

Misol 1 — Oddiy Hash Table (chaining bilan — 2.4)

function hash(kalit, hajm) {
  let h = 0;
  for (const ch of kalit) h = (h + ch.charCodeAt(0)) % hajm;   // (2.2)
  return h;
}

class HashTable {
  constructor(hajm = 16) {
    this.buckets = Array.from({ length: hajm }, () => []);   // chaining (2.4)
    this.size = 0;
  }
  set(kalit, qiymat) {
    const bucket = this.buckets[hash(kalit, this.buckets.length)];
    const juft = bucket.find(([k]) => k === kalit);
    if (juft) juft[1] = qiymat;                  // yangilash
    else { bucket.push([kalit, qiymat]); this.size++; }   // qo'shish
  }
  get(kalit) {
    const bucket = this.buckets[hash(kalit, this.buckets.length)];
    return bucket.find(([k]) => k === kalit)?.[1];   // topmasa undefined (2.1)
  }
  has(kalit) {
    const bucket = this.buckets[hash(kalit, this.buckets.length)];
    return bucket.some(([k]) => k === kalit);    // (2.7)
  }
}

const ht = new HashTable();
ht.set("ism", "Ali"); ht.set("yosh", 19);
console.log(ht.get("ism"));   // "Ali" — O(1) o'rtacha

Misol 2 — Kolliziyani ko'rsatish (2.3)

// Kichik hajm — kolliziya ehtimoli yuqori
function hashKichik(s) {
  let h = 0;
  for (const ch of s) h += ch.charCodeAt(0);
  return h % 4;   // faqat 4 katak  kolliziya ko'p
}
console.log(hashKichik("ab"), hashKichik("ba"));   // bir xil! (a+b = b+a) — kolliziya
// Saboq: yomon hash funksiya (yig'indi) — anagram'larda kolliziya beradi

Misol 3 — Map bilan amaliy (chastota, dedup — 2.9, 3.2)

// Chastota sanash — O(n) (Hash Table tufayli)
function chastota(arr) {
  const m = new Map();
  for (const x of arr) m.set(x, (m.get(x) || 0) + 1);   // O(1) har element
  return m;
}
chastota(["a", "b", "a"]);   // Map { a2, b1 }

// Deduplikatsiya — Set (3.2, 2.9)
const noyob = [...new Set([1, 2, 2, 3])];   // [1,2,3]

// Two Sum — Map bilan O(n) (3.2 takror)
function twoSum(arr, target) {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(target - arr[i])) return [seen.get(target - arr[i]), i];
    seen.set(arr[i], i);
  }
}

Misol 4 — Cache (memoizatsiya — Hash Table qo'llanishi)

// Hisoblangan natijalarni cache'lash (0.1: caching, 5.21: Redis g'oyasi)
function memoize(fn) {
  const cache = new Map();                  // kalit  natija
  return function (...args) {
    const kalit = JSON.stringify(args);     // argumentlardan kalit (2.8)
    if (cache.has(kalit)) return cache.get(kalit);   // O(1) — qayta hisoblamaydi
    const natija = fn(...args);
    cache.set(kalit, natija);
    return natija;
  };
}
const sekinKvadrat = (n) => { /* og'ir hisob */ return n * n; };
const tezKvadrat = memoize(sekinKvadrat);
tezKvadrat(5);   // hisoblaydi
tezKvadrat(5);   // cache'dan — darrov (O(1))

5. To'g'ri va noto'g'ri holatlar

1) Massivda qidiruv (Map o'rniga)

//  O(n) qidiruv tsiklda  O(n²) (3.1)
if (arr.find(x => x.id === id)) {...}

//  Map bilan O(1) (id  element xaritasi)
const map = new Map(arr.map(x => [x.id, x]));
if (map.has(id)) {...}

2) Obyekt kalitini Object'da ishlatish

//  Object kaliti string'ga aylanadi — obyekt kalit ishlamaydi (2.9)
const obj = {};
obj[{a: 1}] = "x";   // kalit "[object Object]" bo'ladi!

//  Map — har qanday kalit (2.9)
const map = new Map();
map.set({a: 1}, "x");

3) Yomon hash funksiya

//  yig'indi — anagramlarda kolliziya (Misol 2)
//  pozitsiyani hisobga oluvchi (masalan h = h*31 + code)
let h = 0;
for (const ch of s) h = (h * 31 + ch.charCodeAt(0)) | 0;

4) Hash Table'dan tartiblangan natija kutish

//  Hash Table tartibsiz — saralangan kutilsa xato (2.7)
//  tartiblangan kerak bo'lsa: [...map.keys()].sort() yoki BST (3.6)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — get undefined qaytaradi

Sababi: kalit yo'q yoki kalit turi mos emas ("1" vs 1 — 2.1). Yechimi: has bilan tekshiring; kalit turini izchil tuting.

Xato 2 — Object kaliti kutilmagan

Sababi: Object kaliti string'ga majburlanadi 2.9-bob. Yechimi: obyekt/son kalit uchun Map.

Xato 3 — Sekin Map (katta ma'lumotda)

Sababi: odatda kutilmaydi (O(1)), lekin yomon hash/ko'p kolliziya worst case O(n) (2.4, 3.1). Yechimi: JS native Mapga ishoning (yaxshi optimallashgan); o'z hash table'ingizda yaxshi funksiya.

Xato 4 — JSON.stringify kalit tartib muammosi (memoize)

JSON.stringify({a:1, b:2}) !== JSON.stringify({b:2, a:1})   // har xil kalit!

Sababi: obyekt kalit tartibi stringifyda farq qiladi 2.8-bob. Yechimi: kalitlarni saralab stringify yoki barqaror kalit.

Xato 5 — Memory leak (cheksiz cache)

Sababi: cache cheksiz o'sadi (Misol 4 — 0.1: RAM). Yechimi: LRU cache (cheklangan hajm), yoki WeakMap (obyekt kalitlar avtomatik tozalanadi).

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Map/Set 2.9-bob: ichkarida Hash Table; kunlik ishda shular.
• Big-O 3.1-bob: O(1) qidiruv — ko'p optimizatsiyaning asosi.
• Massiv algoritmlari 3.2-bob: Two Sum, chastota, dedup.
• Caching (0.1, 5.21): Redis — taqsimlangan Hash Table; memoize.
• DB indeks (6.3, 6.9): hash indeks; tez qidiruv.
• Xavfsizlik (14): parol xeshlash (boshqacha hash — bir tomonlama), HashDoS hujumi.
• BST 3.6-bob: tartiblangan kerak bo'lsa — muqobil.

8. Eng yaxshi amaliyotlar (best practices)

• Tez qidiruv Map/Set (O(1)), massivda find/includes tsiklda emas 3.1-bob.
• Obyekt/son kalit Map (Object emas — 2.9).
• Kalit turini izchil tuting (1 vs "1" — 2.1).
• Native Map/Objectga ishoning — o'z hash table'ingiz faqat o'rganish/maxsus holat uchun.
• Tartiblangan kerak bo'lsa — BST 3.6-bob yoki [...map].sort() 2.7-bob.
• Cache hajmini cheklang (LRU/WeakMap) — memory leak'dan saqlaydi (6-bo'lim).
• Yaxshi hash funksiya (pozitsiyani hisobga oluvchi) — kolliziya kam (5-bo'lim).
• Memoize bilan og'ir hisoblarni cache'lang (Misol 4).

9. Amaliy loyiha: "Hash Table va Cache Tizimi"

Hash Table mexanizmini va qo'llanishini amalda mustahkamlash.

Maqsad

Hash funksiya, kolliziya yechimi va Hash Table'ni o'zingiz qurib, keyin Map bilan amaliy masalalarni (cache, chastota) yechish.

Talablar (requirements)

1. Hash funksiya: matnni indeksga aylantiruvchi (pozitsiyani hisobga oluvchi — yaxshi taqsimot, 2.2, 5-holat).
2. HashTable class: set, get, has, delete, size — chaining bilan (Misol 1, 2.4).
3. Kolliziya namoyishi: ataylab kichik hajmda kolliziya yuzaga keltiring va to'g'ri ishlashini ko'rsating 2.3-bob.
4. Resize: load factor > 0.75 bo'lganda massivni 2x kengaytirib qayta hash 2.6-bob (bonus).
5. Map bilan amaliy: chastota sanash, deduplikatsiya, Two Sum (Misol 3, 3.2).
6. Memoize: og'ir funksiyani cache'lovchi HOF (Misol 4, 2.3).
7. LRU cache (bonus): cheklangan hajmli cache (eng kam ishlatilganni o'chiradi).
8. Har amal uchun Big-O ni yozing; native Map bilan solishtiring 3.1-bob.

Maslahatlar (hint)

• Hash: h = (h * 31 + ch.charCodeAt(0)) % hajm (yaxshiroq taqsimot).
• Chaining: har bucket — [[kalit, qiymat], ...] massiv (Misol 1).
• Kolliziya: kichik hajm (4) + ko'p kalit.
• Resize: yangi massiv yaratib, eski juftliklarni qayta set.
• Memoize: JSON.stringify(args) kalit (4-holat tuzog'iga e'tibor).
• LRU: Map qo'shilish tartibini saqlaydi 2.9-bob — eng eskisi birinchi kalit.

"Tayyor" mezonlari (acceptance criteria)

• Hash funksiya bir tekis taqsimot beradi (kolliziya kam).
• HashTable set/get/has/delete chaining bilan ishlaydi.
• Kolliziya holati to'g'ri ishlaydi (ikki kalit bir indeksda).
• (Bonus) Resize load factor'da ishga tushadi.
• Map bilan chastota/dedup/Two Sum ishlaydi.
• Memoize qayta hisoblamaydi (cache'dan).
• Har amal Big-O bilan izohlangan.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda eng tez qidiruv tuzilmasi — Hash Tableni ichdan o'rgandik:

• Hash Table — ichkarida massiv; hash funksiya kalitni indeksga aylantiradi (% hajm) murojaat O(1) 3.2-bob.
• Hash funksiya — determinik, tez, bir tekis taqsimotli.
• Kolliziya (ikki kalit bir indeks) muqarrar; yechim: chaining (ro'yxat) yoki open addressing (probing).
• Load factor > 0.75 resize (qayta hash).
• Murakkablik: o'rtacha O(1), worst O(n) (yomon hash). Tartib yo'q (kerak bo'lsa BST — 3.6).
• JS: Map/Object/Set — ichkarida shu; cache/memoize qo'llanishi.

Keyingi bob — 3.6-bob: Tree va Binary Search Tree. Hash Table tez, lekin tartibsiz. Tree (daraxt) — ierarxik tuzilma (oila daraxti, fayl tizimi — 0.2, DOM — 0.5). BST esa tartiblangan + tez (O(log n)) qidiruv beradi — Hash Table va Array o'rtasidagi muvozanat.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — Hash Table murakkabligi (o'rtacha/worst)
• Universal CS — hashing, collision resolution (chaining/probing), load factor
• MDN Web Docs — Map, Set, WeakMap (2.9)