Hash table ichidan: hash funksiya, to'qnashuvlar va yuklanish koeffitsiyenti

Qisqacha: Hash jadval (hash table) — kalitni hash funksiya bilan raqamga, raqamni esa massiv indeksiga aylantiradigan tuzilma. Shuning uchun Map.get butun ro'yxatni ko'rmaydi: to'g'ridan-to'g'ri kerakli katakka boradi — o'rtacha O(1). Ikki kalit bitta katakka tushsa — to'qnashuv (collision): u zanjir (bitta katakda ro'yxat) yoki ochiq manzillash (keyingi bo'sh katak) bilan hal qilinadi. Jadval to'lib borsa, kattaroq massivga ko'chiriladi. Yomon yoki oldindan bilinadigan hash funksiyada hamma kalit bitta katakka tushadi va jadval O(n) ga aylanadi — bu hash DoS hujumi.

Bu darsda

• Hash funksiya kalitni qanday qilib massiv indeksiga aylantirishini qo'lda hisoblab ko'rsata olasiz.
• To'qnashuvlarni ikki usulda — zanjir va chiziqli tekshirish bilan — hal qiladigan jadval yoza olasiz.
• Yuklanish koeffitsiyenti va qayta xeshlash nega set ni amortizatsiyalangan O(1) qilishini tushuntira olasiz.
• Hash DoS hujumini o'z jadvalingizda ko'rasiz va Map undan qanday himoyalanganini bilasiz.

Oldin bilishingiz kerak: Hash map bilan hisoblash naqshlari, Queue va deque, Xotira murakkabligi va amortizatsiya, Map.

1. Nega bu kerak?

O'tgan darslarda «Bahor» kassasidagi ko'p masalani Map va Set bilan yechdik: takror buyurtmalar, taomlar sanog'i, "ikki summa". Hamma joyda bitta jumla takrorlandi: "Map.get — O(1)". Sardor bir kuni so'radi: "Qanday qilib? Menyuda 10 ta taom bo'lsa ham, 10 000 ta bo'lsa ham, get bir xil tez. U qidirmaydimi?"

Bu savol to'g'ri. Agar Map ichida oddiy ro'yxat bo'lganida, kalitni topish uchun uni boshidan oxirigacha ko'rish kerak bo'lardi — O(n). Demak, ichida boshqa narsa bor. Bugun o'sha narsani o'zimiz quramiz: hash jadval (hash table).

Oshxonadan o'xshatish. «Bahor» omborida 26 ta tokcha bor, har biriga harf yozilgan. "Guruch" — G tokchasida, "sabzi" — S tokchasida. Oshpaz guruchni qidirib butun omborni aylanmaydi: nomning birinchi harfiga qaraydi va to'g'ri tokchaga boradi. Nomdan tokcha raqamini chiqaradigan qoida — hash funksiya. Bitta tokchada "sabzi" va "sut" birga turib qolsa — bu to'qnashuv. Bugungi dars aynan shu ikki g'oya haqida.

2. Sodda yechim: juftlar ro'yxati

Avval eng oddiy "lug'at"ni yasaymiz: [kalit, qiymat] juftlari massivi. Narxni topish uchun ro'yxatni boshidan ko'ramiz:

const menu = [
  ["osh", 35000],
  ["lag'mon", 28000],
  ["manti", 30000],
  ["ko'k choy", 5000],
];

function findPrice(pairs, name) {
  for (const [key, value] of pairs) {
    if (key === name) return value;
  }
  return undefined;
}

console.log(findPrice(menu, "manti")); // 30000
console.log(findPrice(menu, "pitsa")); // undefined

Bu ishlaydi, lekin har qidiruv — O(n): eng yomon holatda (taom yo'q yoki oxirida) hamma juftni ko'radi. Million buyurtmali jadvalda har get million solishtirish. Bizga kalitdan to'g'ridan-to'g'ri joyini chiqaradigan usul kerak.

3. Hash funksiya: kalitdan indeksga

3.1 G'oya

Massivda arr[5] — O(1): kompyuter 5-katak manzilini darhol hisoblaydi (Massiv xotirada). Agar har kalitni sonli indeksga aylantira olsak, kalit bo'yicha qidiruv ham O(1) bo'ladi. Shu ishni bajaradigan funksiya — hash funksiya (hash function): kalitni oladi va har safar bir xil kalit uchun bir xil son qaytaradi.

Massivning har katagi savat (bucket) deb ataladi — unga bir yoki bir nechta kalit tushadi. Savatlar soni — jadvalning sig'imi (capacity).

Yaxshi hash funksiyaning uch talabi:

1. Bir xil kalit — doim bir xil indeks. Aks holda qo'ygan narsangizni topa olmaysiz.
2. Tez — O(kalit uzunligi), butun jadvalga bog'liq emas.
3. Kalitlarni savatlarga teng sochadi — bir savatga to'planib qolmasin.

3.2 Birinchi urinish: harf kodlari yig'indisi

Har harfning raqamli kodi bor: "o".charCodeAt(0) — 111 (Unicode va emoji). Kodlarni qo'shib, savatlar soniga bo'lgandagi qoldiqni olamiz. % (qoldiq) natijasi doim 0 dan capacity - 1 gacha — demak, to'g'ri indeks:

function sumHash(key, capacity) {
  let sum = 0;
  for (let i = 0; i < key.length; i++) sum += key.charCodeAt(i);
  return sum % capacity;
}

function polyHash(key, capacity) {
  let h = 0;
  for (let i = 0; i < key.length; i++) {
    h = (h * 31 + key.charCodeAt(i)) % capacity;
  }
  return h;
}

for (const key of ["osh", "sho", "hos"]) {
  console.log(key, sumHash(key, 8), polyHash(key, 8));
}

Konsolda:

osh 2 4
sho 2 2
hos 2 4

sumHash da uchala so'z 2-savatga tushdi. Sababi: harflar bir xil, faqat tartibi boshqa — yig'indi esa tartibni sezmaydi (111 + 115 + 104 = 330, 330 ni 8 ga bo'lsak qoldiq 2). Bunday so'zlar anagramlar deyiladi va sumHash ularning hammasini bitta savatga yig'adi.

3.3 Ikkinchi urinish: ko'phadli hash

polyHash har qadamda oldingi natijani 31 ga ko'paytiradi, keyin keyingi harfni qo'shadi. Endi harfning o'rni ham ta'sir qiladi: "osh" va "sho" turli savatga tushdi. Bu ko'phadli hash (polynomial hash) — Java'dagi satr hashi ham shunday hisoblanadi. 31 tanlangani — tarixiy odat: toq son va hisoblash arzon.

"osh" va "hos" baribir to'qnashdi. Bu xato emas: 8 ta savatga cheksiz ko'p so'z sig'maydi, demak, kimdir albatta bir savatga tushadi. To'qnashuvni yo'q qilib bo'lmaydi — uni faqat kamaytirish va to'g'ri hal qilish mumkin.

Tekshirib ko'ring: "non" so'zidagi harflar kodlari: n — 110, o — 111. Unda sumHash("non", 8) nechaga teng?

4. To'qnashuvni hal qilish: zanjir usuli

4.1 Har savat — kichik ro'yxat

Eng ko'p ishlatiladigan yo'l — zanjir usuli (separate chaining): har savat — [kalit, qiymat] juftlarining kichik massivi. Kalit savatga tushadi va ro'yxat oxiriga qo'shiladi. Qidirganda faqat shu savat ro'yxatini ko'ramiz, butun jadvalni emas.

Olti taomni 8 savatli jadvalga qo'yamiz. Qaysi savatlarda to'qnashuv bo'lishini kuzating:

7-savatda uchta kalit zanjir bo'lib qoldi. get("kabob") uchun uchta solishtirish kerak — lekin butun jadval bo'ylab olti emas. Savatlar qancha ko'p va qisqa bo'lsa, qidiruv shuncha tez.

4.2 To'liq jadval

Endi set, get, delete va o'sishni bitta klassga yig'amiz (class sintaksisi). Har metod avval kalitning savatini topadi, keyin faqat o'sha savat bilan ishlaydi:

class HashTable {
  constructor(capacity = 8) {
    this.buckets = Array.from({ length: capacity }, () => []);
    this.size = 0;
  }

  hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = (h * 31 + key.charCodeAt(i)) % this.buckets.length;
    }
    return h;
  }

  set(key, value) {
    const bucket = this.buckets[this.hash(key)];
    for (const entry of bucket) {
      if (entry[0] === key) {
        entry[1] = value; // kalit bor — qiymatni yangilaymiz
        return;
      }
    }
    bucket.push([key, value]);
    this.size++;
    if (this.size / this.buckets.length > 0.75) this.resize();
  }

  get(key) {
    const bucket = this.buckets[this.hash(key)];
    for (const [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }

  delete(key) {
    const bucket = this.buckets[this.hash(key)];
    const i = bucket.findIndex(([k]) => k === key);
    if (i === -1) return false;
    bucket.splice(i, 1);
    this.size--;
    return true;
  }

  resize() {
    const old = this.buckets;
    this.buckets = Array.from({ length: old.length * 2 }, () => []);
    this.size = 0;
    for (const bucket of old) {
      for (const [k, v] of bucket) this.set(k, v);
    }
  }
}

const prices = new HashTable();
prices.set("osh", 35000);
prices.set("lag'mon", 28000);
prices.set("manti", 30000);
prices.set("osh", 36000); // narx oshdi
console.log(prices.get("osh"), prices.get("pitsa"));
console.log(prices.delete("manti"), prices.size);
for (const dish of ["somsa", "norin", "sho'rva", "kabob", "non"]) {
  prices.set(dish, 10000);
}
console.log(prices.size, prices.buckets.length);

Konsolda:

36000 undefined
true 2
7 16

Qatorma-qator:

• set — kalit savatda bo'lsa, faqat qiymatni almashtiradi ("osh" ikkinchi marta qo'shilganda size oshmadi). Yo'q bo'lsa — oxiriga qo'shadi.
• get — faqat bitta savatni ko'radi. Kalit topilmasa — undefined, xuddi Map dagidek.
• delete — savatdan splice bilan olib tashlaydi. Savat qisqa bo'lgani uchun bu ham arzon.
• Oxirgi qator: 7 ta taom qo'shilganda savatlar soni 8 dan 16 ga oshdi. Buni resize qildi — keyingi bo'limda.

4.3 Yuklanish koeffitsiyenti va qayta xeshlash

Yuklanish koeffitsiyenti (load factor) — kalitlar sonining savatlar soniga nisbati: α = size ÷ capacity. α = 0,5 — o'rtacha har ikki savatga bitta kalit. α = 4 — har savatda o'rtacha to'rttadan, ya'ni har get to'rtta solishtirish.

Bu nisbat qidiruv narxiga qanday ta'sir qilishini o'lchaymiz. 1 024 savatli jadvalga turli miqdorda buyurtma raqamini qo'yib, bitta kalitni topish uchun o'rtacha nechta solishtirish kerakligini sanaymiz:

function avgChecks(n, capacity) {
  const hash = (key) => {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = (h * 31 + key.charCodeAt(i)) % capacity;
    }
    return h;
  };
  const buckets = Array.from({ length: capacity }, () => []);
  const keys = Array.from(
    { length: n },
    (_, i) => `buyurtma-${100000 + i}`,
  );
  for (const key of keys) buckets[hash(key)].push(key);
  let checks = 0;
  for (const key of keys) {
    checks += buckets[hash(key)].indexOf(key) + 1;
  }
  return (checks / n).toFixed(2);
}

for (const n of [512, 768, 1024, 2048, 4096]) {
  const alpha = n / 1024;
  console.log(`α = ${alpha}: ${avgChecks(n, 1024)} ta solishtirish`);
}

Konsolda:

α = 0.5: 1.98 ta solishtirish
α = 0.75: 2.16 ta solishtirish
α = 1: 2.33 ta solishtirish
α = 2: 3.95 ta solishtirish
α = 4: 6.59 ta solishtirish

α oshgan sari zanjirlar uzayadi va har get qimmatlashadi. Agar jadval hech qachon kattalashmasa, n ta kalitda α = n ÷ capacity — ya'ni har qidiruv yana O(n) bo'lib qoladi, faqat sekinroq o'sadi.

Shuning uchun jadval α chegaradan oshganda (bizda 0,75) kattaroq massiv oladi va hamma kalitni qaytadan joylaydi. Bu qayta xeshlash (rehashing): savatlar soni o'zgargani uchun har kalitning indeksi ham o'zgaradi — hash qaytadan hisoblanadi. resize aynan shu ishni qiladi.

Qayta xeshlash bitta set ni O(n) qiladi: hamma kalit ko'chadi. Lekin Xotira murakkabligi va amortizatsiya darsidagi dinamik massiv bilan bir xil hisob ishlaydi: sig'im har safar ikki baravar oshadi, ko'chirishlar yig'indisi 1 + 2 + 4 + … < 2n. Demak, set — amortizatsiyalangan O(1).

Tekshirib ko'ring: Jadvalda 16 ta savat va 12 ta kalit bor. Yana bitta kalit qo'shilsa, resize ishlaydimi? Nechta savat bo'ladi?

4.4 Hash sifati muhim

Jadvalimiz ikki baravar o'sdi, lekin yuqoridagi vizualdagi zanjir yo'qolmadi. 16 savatda ham "manti", "somsa" va "kabob" bitta — 15-savatga tushadi. Sababi hash funksiyamizda. Savatlar soni 2 ning darajasi (8, 16, 1 024) bo'lsa, % capacity faqat sonning eng kichik bitlariga qaraydi, 31 esa ularni yaxshi aralashtirmaydi. Natijada ketma-ket kalitlar savatlarga notekis tushadi. O'lchovda ham shu ko'rindi: α = 0,5 da nazariya bo'yicha o'rtacha ≈ 1,25 solishtirish kerak edi, bizda — 1,98.

Haqiqiy jadvallar bitlarni yaxshiroq aralashtiradigan funksiyalarni ishlatadi. Eng sodda mashhurlaridan biri — FNV-1a:

function fnv1a(key) {
  let h = 2166136261; // FNV boshlang'ich soni
  for (let i = 0; i < key.length; i++) {
    h ^= key.charCodeAt(i); // XOR: bitlarni aralashtiramiz
    h = Math.imul(h, 16777619) >>> 0; // 32-bitli ko'paytirish
  }
  return h;
}

console.log(fnv1a("osh"), fnv1a("osh") % 8);
console.log(fnv1a("Aa") === fnv1a("BB"));

Konsolda:

3407902957 5
false

^ — bit amallari darsidagi XOR. Math.imul — ikki sonni 32 bit ichida ko'paytiradi (natija juda katta son bo'lib, aniqligini yo'qotmasin), >>> 0 esa natijani manfiy bo'lmagan 32-bitli songa aylantiradi. Ichki matematikasini yodlash shart emas — muhimi, har harf hamma bitlarga ta'sir qiladi. Shu funksiya bilan yuqoridagi o'lchovni takrorladik:

FNV-1a nazariy qiymatga (1 + α ÷ 2) yaqin ishladi: kalitlar savatlarga teng tarqaldi. Big-O ikkalasida bir xil, lekin amalda qidiruv ikki baravar tezlashdi.

5. Ikkinchi usul: ochiq manzillash

5.1 Band bo'lsa — keyingi katak

Zanjirsiz ham ishlash mumkin. Ochiq manzillash (open addressing) da har katakka faqat bitta kalit tushadi. Kalitning o'z katagi band bo'lsa, boshqa bo'sh katak qidiriladi. Eng sodda qoida — chiziqli tekshirish (linear probing): keyingi katakka o'tish, oxiriga yetganda boshiga qaytish. Bir xil olti taom bilan:

kabob o'z katagi 7 da joy topa olmadi: 7, 0, 1 band edi — to'rtinchi urinishda 2-katakka tushdi. Band kataklar bir joyga yopishib qoldi. Bu to'planish (clustering): to'plam qancha katta bo'lsa, unga tushgan har yangi kalit shuncha uzoq yuradi va to'plamni yana kattalashtiradi.

5.2 Qidiruv va o'chirish

Qidiruv ham xuddi shu yo'ldan yuradi: kalitning hash katagidan boshlaydi va kalitni yoki bo'sh katakni topguncha davom etadi. Bo'sh katak — "bu kalit jadvalda yo'q" degan belgi: agar bo'lganida, shu yerga qo'yilgan bo'lardi.

O'chirishda nozik tuzoq bor. "somsa" ni (0-katak) shunchaki null qilsak, kabob ni qidirish 7 dan boshlab 0 ga keladi, bo'sh katakni ko'radi va "yo'q" deb to'xtaydi. Holbuki kabob 2-katakda turibdi! Shuning uchun o'chirilgan katakka maxsus belgi — qabr toshi (tombstone) qo'yiladi: "bu yerda kalit bo'lgan, qidiruvni davom ettiring". Yangi kalit esa qabr toshi o'rniga qo'yilishi mumkin.

5.3 Qaysi biri yaxshi?

Ochiq manzillashda α 1 ga yaqinlashsa, to'planish keskin uzayadi — shuning uchun u odatda α ≈ 0,5–0,7 da kattalashadi. Uning yutug'i: barcha kalitlar bitta uzluksiz massivda, protsessor keshi uni yaxshi o'qiydi (Massiv xotirada). Python dict, Rust HashMap ochiq manzillashni ishlatadi; Java HashMap — zanjirni.

V8 dagi Map va Set zanjir usulini ishlatadi, lekin bir farq bilan: yozuvlarning o'zi qo'shilish tartibida alohida massivda turadi, savatlar esa ularga ishora qiladi. Shu sababli Map kalitlarni doim qo'shilgan tartibda aylanadi. Bu xususiyatdan keyingi darsda LRU kesh qurishda foydalanamiz.

6. O'lchov: O(1) qachon O(n) ga aylanadi

O'z HashTable imizni ikki xil kalit to'plami bilan o'lchadik (o'lchash usuli):

1. Oddiy kalitlar — buyurtma-100000, buyurtma-100001, … — savatlarga tarqaladi.
2. Ataylab yasalgan kalitlar — hammasi bir xil hash beradi (qanday yasalgani — keyingi bo'limda).

Har o'lchovda bo'sh jadvalga n ta kalit qo'shiladi (har n alohida jarayonda, isitish, 7 o'lchov medianasi). Kalitlar o'lchovdan oldin tayyorlanadi — vaqtga faqat set lar kiradi:

// oddiy kalitlar: tayyorlash o'lchanmaydi
const keys = Array.from(
  { length: n },
  (_, i) => `buyurtma-${100000 + i}`,
);
const start = performance.now();
const table = new HashTable();
for (const key of keys) table.set(key, 1);
const ms = performance.now() - start; // shu o'lchanadi

Oddiy kalitlarda n ikki baravar — vaqt ham taxminan ikki baravar: n ta set, har biri amortizatsiyalangan O(1), jami O(n). Bir xil hashli kalitlarda esa har safar to'rt baravar: hamma kalit bitta savatda, har set butun zanjirni ko'radi — jami O(n²). Eng katta o'lchovda farq yaqqol: 8 192 ta kalitga 416 ms, Map da esa 1,3 ms. O(1) — bu o'rtacha holat va u faqat kalitlar teng tarqalganda rost (eng yomon holat).

7. Hujumchi nigohi: hash DoS

7.1 Hujum

Bir xil hashli kalitlarni yasash qiyinmi? Bizning hash uchun — qiyin emas. "Aa" va "BB" ni tekshiring: 65 × 31 + 97 = 2 112 va 66 × 31 + 66 = 2 112. Ikkala juftni istalgancha ulasangiz ham hash bir xil qoladi:

function hash(key, capacity) {
  let h = 0;
  for (let i = 0; i < key.length; i++) {
    h = (h * 31 + key.charCodeAt(i)) % capacity;
  }
  return h;
}

function collidingKeys(count) {
  let keys = [""];
  while (keys.length < count) {
    keys = keys.flatMap((k) => [k + "Aa", k + "BB"]);
  }
  return keys.slice(0, count);
}

console.log(hash("Aa", 1000), hash("BB", 1000));
const keys = collidingKeys(8);
console.log(keys.join(" "));
const indexes = keys.map((k) => hash(k, 1_000_003));
console.log(new Set(indexes).size, "xil indeks");

Konsolda:

112 112
AaAaAa AaAaBB AaBBAa AaBBBB BBAaAa BBAaBB BBBBAa BBBBBB
1 xil indeks

Million savatli jadvalda ham sakkizta kalit bitta indeksga tushdi. Har qadamda kalitlar ikki baravar ko'payadi: 20 juftli satrlardan million xil kalit chiqadi — hammasi bitta savatda.

Endi server tasavvur qiling. U so'rovdagi parametrlarni (?a=1&b=2…) yoki JSON kalitlarini hash jadvalga yozadi. Hujumchi bitta so'rovda yuz minglab shunday kalit yuboradi. Server har kalitni qo'shganda butun zanjirni ko'radi — O(n²) ish, protsessor daqiqalab band. Bir nechta so'rov — va server boshqa mijozlarga javob bera olmaydi. Bu hash DoS (hash flooding) — xizmatni rad etishga majburlash hujumi.

Bu nazariya emas. 2011-yil dekabrida Alexander Klink va Julian Wälde 28C3 konferensiyasida PHP, Java, Python, Ruby va boshqa platformalar shu hujumga ochiq ekanini ko'rsatdi. Java'da aynan "Aa"/"BB" usuli ishladi. Node.js'da 2017-yilda CVE-2017-11499 tuzatildi: V8 hash funksiyasining tasodifiy urug'i Node'ning har versiyasida bir xil bo'lib qolgan edi.

7.2 Himoya

• Tasodifiy urug' (seed). Hash funksiya har dastur ishga tushganda yangi tasodifiy son bilan aralashtiriladi. Hujumchi urug'ni bilmaydi — demak, qaysi kalitlar to'qnashishini oldindan hisoblay olmaydi. V8 satr hashlarini shunday hisoblaydi — o'lchovda Map ning o'sha kalitlarda chiziqli qolgani shundan. Python 3.3 dan beri, Rust esa boshidanoq (SipHash funksiyasi bilan) shunday qiladi.
• Kirishni cheklash. Server bitta so'rovdagi parametrlar sonini cheklaydi. Masalan, Node'ning querystring moduli va Express ishlatadigan qs kutubxonasi standart holatda bitta so'rovdan 1 000 dan ortiq parametrni o'qimaydi (so'rov parametrlarini backend qismida o'rganamiz).
• Uzun zanjirni daraxtga aylantirish. Java 8 dan beri HashMap savatdagi zanjir 8 tadan oshsa, uni muvozanatli daraxtga aylantiradi — eng yomon holat O(n) emas, O(log n) bo'ladi (Balanslangan daraxtlar).

Amaliy xulosa: foydalanuvchi bergan kalitlarni o'z yozgan hash jadvalingizga solmang — Map dan foydalaning. O'z hash funksiyangiz o'qish uchun foydali, lekin productionda — yo'q.

Tekshirib ko'ring: Sardor: "Hujumchi Map ga ham bir xil hashli kalit yuborsa-chi?" Nima deysiz?

8. Chegaraviy holatlar

• Bo'sh jadval. get istalgan kalitga undefined qaytaradi, delete — false. Testda albatta tekshiring.
• Bo'sh satr kalit. hash("") — 0 (sikl bir marta ham aylanmaydi). Bu to'g'ri kalit, uni ham saqlash kerak.
• Bir kalitni qayta qo'shish. size oshmasligi va qiymat almashishi kerak — aks holda bitta savatda ikki "osh" paydo bo'ladi.
• Satr bo'lmagan kalit. Bizning hash faqat satr bilan ishlaydi: hash(42) da key.length — undefined, sikl aylanmaydi va hamma son 0-savatga tushadi. Haqiqiy Map har turdagi kalitni qabul qiladi — buni keyingi darsda ko'ramiz.
• O'chirishdan keyin qisqarish. Bizning jadval faqat o'sadi. Million kalit qo'shib, hammasini o'chirsangiz, katta massiv qoladi. Ba'zi jadvallar α juda kichik bo'lganda (masalan, 0,25 dan kam) qisqaradi.

9. Ko'p uchraydigan xatolar

9.1 % capacity ni unutish

hash sonni qaytaradi, lekin u massiv uzunligidan katta bo'lsa — buckets[123456] undefined, keyingi qatorda Cannot read properties of undefined (reading 'push') xatosi. Tuzatish: indeks doim % capacity dan o'tsin.

9.2 Qayta xeshlashda eski indeksni ishlatish

Kattalashganda savatlarni shunchaki yangi massivga ko'chirish (newBuckets[i] = old[i]) — xato. Savatlar soni o'zgardi, demak, har kalitning indeksi ham boshqa. Natijada get noto'g'ri savatga qaraydi va mavjud kalitni topmaydi. Tuzatish: har kalitni yangi hash bilan qaytadan joylang.

9.3 Tasodifiy hash

hash ichida Math.random() yoki Date.now() ishlatilsa, bir xil kalit har safar boshqa savatga tushadi. Qo'yilgan narsa hech qachon topilmaydi. Tasodifiy urug' — dastur boshida bir marta tanlanadi va keyin o'zgarmaydi.

9.4 "Map doim O(1)"

Bu o'rtacha holat. Kalitlar bir savatga yig'ilsa — O(n). Intervyuda "O(1) o'rtacha, O(n) eng yomon" deb aniq ayting.

10. Mashqlar

1-mashq (oson): Qo'lda hash

polyHash("non", 8) ni qo'lda hisoblang. Kodlar: n — 110, o — 111. Har qadamda h = (h * 31 + kod) % 8.

Birinchi qadam: (0 × 31 + 110) % 8 = 6. Ikkinchi qadam: (6 × 31 + 111) % 8 = 297 % 8 = 1. Uchinchi qadamda natija:

2-mashq (o'rta): Savatlar xaritasi

HashTable ga stats() metodini qo'shing. U uchta sonni qaytarsin: bo'sh savatlar soni, eng uzun zanjir uzunligi va α (ikki xona aniqlikda). 1 000 ta buyurtma-… kalitini qo'shib, natijani chiqaring. Ishora: this.buckets.filter(...) va Math.max(...lengths).

stats() {
  const lengths = this.buckets.map((b) => b.length);
  return {
    empty: lengths.filter((len) => len === 0).length,
    longest: Math.max(...lengths),
    alpha: (this.size / this.buckets.length).toFixed(2),
  };
}

3-mashq (qiyin): Ochiq manzillash va testlar

kurs/mashqlar/14/21-hash/probing.test.mjs faylida ProbingTable klassini yozing: chiziqli tekshirish, set, get, delete (qabr toshi bilan), α > 0,5 da ikki baravar o'sish. Qabr toshi uchun maxsus obyekt ishlating: const TOMBSTONE = {} — u hech qanday kalitga teng bo'lmaydi. Testlar (node:test):

1. Qo'shilgan narx topiladi, yo'q taom — undefined.
2. To'qnashgan kalitlar (bitta katakka tushadiganlar) ikkalasi ham topiladi.
3. O'rtadagi kalit o'chirilgandan keyin undan keyingi kalit baribir topiladi (qabr toshi ishlaydi).
4. 1 000 ta kalitdan keyin hammasi topiladi va α ≤ 0,5.

// kurs/mashqlar/14/21-hash/probing.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const TOMBSTONE = {}; // "bu yerda kalit bo'lgan" belgisi

class ProbingTable {
  constructor(capacity = 8) {
    this.slots = new Array(capacity).fill(null);
    this.size = 0;
  }
  hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = (h * 31 + key.charCodeAt(i)) % this.slots.length;
    }
    return h;
  }
  // kalit turgan katak yoki -1
  find(key) {
    let i = this.hash(key);
    while (this.slots[i] !== null) {
      const slot = this.slots[i];
      if (slot !== TOMBSTONE && slot.key === key) return i;
      i = (i + 1) % this.slots.length;
    }
    return -1;
  }
  set(key, value) {
    const found = this.find(key);
    if (found !== -1) {
      this.slots[found].value = value;
      return;
    }
    if ((this.size + 1) / this.slots.length > 0.5) this.resize();
    let i = this.hash(key);
    while (this.slots[i] !== null && this.slots[i] !== TOMBSTONE) {
      i = (i + 1) % this.slots.length;
    }
    this.slots[i] = { key, value };
    this.size++;
  }
  get(key) {
    const i = this.find(key);
    return i === -1 ? undefined : this.slots[i].value;
  }
  delete(key) {
    const i = this.find(key);
    if (i === -1) return false;
    this.slots[i] = TOMBSTONE;
    this.size--;
    return true;
  }
  resize() {
    const old = this.slots;
    this.slots = new Array(old.length * 2).fill(null);
    this.size = 0;
    for (const slot of old) {
      if (slot !== null && slot !== TOMBSTONE) {
        this.set(slot.key, slot.value);
      }
    }
  }
}

test("narx topiladi, yo'q taom — undefined", () => {
  const t = new ProbingTable();
  t.set("osh", 35000);
  assert.equal(t.get("osh"), 35000);
  assert.equal(t.get("pitsa"), undefined);
});

test("to'qnashgan kalitlar ikkalasi ham topiladi", () => {
  const t = new ProbingTable(16);
  assert.equal(t.hash("manti"), t.hash("somsa")); // ikkalasi 15
  t.set("manti", 30000);
  t.set("somsa", 8000);
  assert.equal(t.get("manti"), 30000);
  assert.equal(t.get("somsa"), 8000);
});

test("qabr toshi: o'chirilgandan keyingi kalit topiladi", () => {
  const t = new ProbingTable(16);
  t.set("manti", 30000);
  t.set("somsa", 8000);
  t.set("kabob", 40000); // 15 band, 0 band — 1-katak
  t.delete("somsa");
  assert.equal(t.get("kabob"), 40000);
  assert.equal(t.get("somsa"), undefined);
});

test("1000 ta kalit — hammasi topiladi, α ≤ 0.5", () => {
  const t = new ProbingTable();
  for (let i = 0; i < 1000; i++) t.set(`buyurtma-${i}`, i);
  for (let i = 0; i < 1000; i++) {
    assert.equal(t.get(`buyurtma-${i}`), i);
  }
  assert.ok(t.size / t.slots.length <= 0.5);
});

✔ narx topiladi, yo'q taom — undefined (1.5519ms)
✔ to'qnashgan kalitlar ikkalasi ham topiladi (0.1862ms)
✔ qabr toshi: o'chirilgandan keyingi kalit topiladi (0.1575ms)
✔ 1000 ta kalit — hammasi topiladi, α ≤ 0.5 (3.6466ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 101.2003

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga uchta qator qo'shing: hash jadval get (yaxshi hash), get (hamma kalit bir savatda) va set (qayta xeshlash bilan). Har biriga vaqt, xotira va "nega" ustunini to'ldiring.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Kalit bo'yicha qidirish | hash jadval get | O(1) o'rtacha | O(1) |
| Kalit bo'yicha qidirish | bir savatga yig'ilgan | O(n) eng yomon | O(1) |
| Kalit qo'shish | set + rehashing | O(1) amort. | O(n) jadval |

git add 14/MURAKKABLIK.md 14/21-hash
git commit -m "14/21: hash jadval, ochiq manzillash testlari"

11. Real ishda

• Hamma joyda hash jadval. JavaScript Map, Set va obyekt xususiyatlari, Python dict, ma'lumotlar bazasidagi hash indekslar, Redis — hammasining ichida hash jadval. Ichini bilish ularni qachon ishonsa bo'lishini, qachon yo'qligini tushunishga yordam beradi.
• Server xavfsizligi. Foydalanuvchi kiritgan kalitlarni (so'rov parametrlari, JSON, sarlavhalar) cheklash — hash DoS'dan himoyaning bir qismi. Backend kutubxonalari buni standart qiladi, lekin o'z parseringizni yozsangiz — esda tuting.
• Kriptografik hash boshqa narsa. SHA-256 (Git commitlari, parol hashlari) ham "hash funksiya", lekin maqsadi boshqa: teskari hisoblash va to'qnashuv topish amalda mumkin bo'lmasin. Hash jadval uchun esa tezlik muhim. Ikkalasini aralashtirmang.
• Intervyu. "HashMap qanday ishlaydi?", "To'qnashuvlar qanday hal qilinadi?", "Nega get O(1)?", "Load factor nima?" — o'rta darajadagi intervyularning eng ko'p savollaridan.

Xulosa

• Hash funksiya kalitni songa, % capacity esa savat indeksiga aylantiradi — shuning uchun qidiruv butun ro'yxatni ko'rmaydi.
• To'qnashuvni yo'q qilib bo'lmaydi: zanjir usuli savatda ro'yxat tutadi, ochiq manzillash keyingi bo'sh katakni qidiradi (o'chirishda — qabr toshi).
• α = size ÷ capacity; chegaradan oshsa — ikki baravar o'sish va qayta xeshlash. set amortizatsiyalangan O(1).
• Hash sifati muhim: 31 li hash bizda α = 0,5 da 1,98, FNV-1a — 1,13 solishtirish berdi.
• O(1) — o'rtacha holat. Hamma kalit bir savatda bo'lsa, n ta qo'shish O(n²) ga aylanadi: o'lchovda 8 192 kalit 416 ms, Map da 1,3 ms. Himoya — tasodifiy urug' va kirishni cheklash.

Keyingi dars: Hash tuzilmalari JS'da va LRU kesh — Object, Map va Set ni qachon tanlash, kalit turlari, aylanish tartibi va Map tartibidan foydalanib O(1) LRU kesh qurish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 11-bob (hash jadvallar, zanjir, ochiq manzillash).
• A. Klink, J. Wälde, "Efficient Denial of Service Attacks on Web Application Platforms", 28C3, 2011 — oCERT-2011-003.
• Node.js xavfsizlik relizi, 2017-yil iyul: "Constant Hashtable Seeds (CVE-2017-11499)" — nodejs.org/en/blog
• V8 manba kodi: src/objects/ordered-hash-table.h — Map/Set uchun tartibni saqlaydigan hash jadval — github.com/v8/v8
• FNV hash: Fowler, Noll, Vo — isthe.com/chongo/tech/comp/fnv/