Hash tuzilmalari JS'da va LRU kesh: Object, Map, Set va O(1) kesh

Qisqacha: JavaScript'da uchta hash tuzilma bor. Obyekt — oldindan ma'lum maydonli "yozuv" uchun: kalitlari faqat satr (yoki Symbol), prototipdan meros kalitlari bor. Lug'at Map esa istalgan kalitni oladi: kalit soni ko'p, tez-tez qo'shilib-o'chiriladi, kalit son yoki obyekt bo'ladi. To'plam Set — faqat "bormi?" savoli uchun. Shuningdek, Map kalitlarni qo'shilgan tartibda saqlaydi — shu xususiyat bilan LRU kesh bir necha qatorda yoziladi. Katta keshda esa klassik yechim — Map + ikki tomonlama bog'langan ro'yxat: har amal haqiqiy O(1).

Bu darsda

• Object, Map va Set ni kalit turi, tartib, tezlik va xavfsizlik bo'yicha solishtirib, vazifaga mosini tanlay olasiz.
• Obyektning yashirin tuzoqlarini ("1" va 1, constructor, raqamli kalitlar tartibi) oldindan ko'rasiz.
• LRU keshni Map bilan va Map + ikki tomonlama ro'yxat bilan yoza olasiz.
• Nega katta keshda ikkinchi usul tezroq ekanini o'lchov bilan ko'rsata olasiz.

Oldin bilishingiz kerak: Hash table ichidan, Linked list masalalari, Map, Set, Memoization.

1. Nega bu kerak?

O'tgan darsda hash jadvalni o'zimiz qurdik. Real ishda uni yozmaymiz: JavaScript'ning o'zida uchta tayyor hash tuzilma bor — obyekt, Map va Set. Lekin ular bir xil emas, va noto'g'ri tanlov sezilmaydigan xatolarga olib keladi.

«Bahor» ilovasida Sardor ikkita narsani yozdi. Birinchisi — so'zlar hisoblagichi: mehmonlar izohlarida qaysi so'z necha marta uchrashini sanaydi. Ikkinchisi — kesh: mehmon taom sahifasini ochganda tafsilotlar serverdan keladi, Sardor ularni obyektda saqlaydi, toki qayta ochilganda server bezovta bo'lmasin.

Bir hafta o'tib ikki muammo chiqdi. Hisoblagich bitta izohda g'alati natija berdi: "function Object() { [native code] }1". Kesh esa hech qachon tozalanmadi — telefonda ilova sekinlashdi. Bugun ikkala muammoning sababini topamiz va tuzatamiz.

2. Obyekt, Map va Set: farqlar

2.1 Kalit turlari

Obyekt kaliti — faqat satr yoki Symbol. Boshqa narsa berilsa, JavaScript uni jimgina satrga aylantiradi:

const prices = {};
prices[1] = "osh";
prices["1"] = "manti"; // xuddi shu kalit!
const table = { id: 7 };
prices[table] = "stol 7";
console.log(prices);
console.log(Object.keys(prices));

const map = new Map();
map.set(1, "osh");
map.set("1", "manti");
map.set(table, "stol 7");
map.set(NaN, "noma'lum");
console.log(map.size, map.get(1), map.get("1"));
console.log(map.get(table), map.get({ id: 7 }), map.get(NaN));

Konsolda:

{ '1': 'manti', '[object Object]': 'stol 7' }
[ '1', '[object Object]' ]
4 osh manti
stol 7 undefined noma'lum

Obyektda 1 va "1" — bitta kalit: "manti" "osh" ning ustiga yozildi. Kalit sifatidagi table obyekti esa "[object Object]" satriga aylandi — boshqa har qanday obyekt ham aynan shu kalitga tushadi. Lekin Map kalitni o'zgartirmaydi: son, satr, obyekt va hatto NaN — to'rtta alohida kalit.

E'tibor bering: map.get({ id: 7 }) — undefined. Obyekt kalit havola bo'yicha solishtiriladi (Tenglik): ko'rinishi bir xil bo'lsa ham, bu boshqa obyekt. Obyekt kalitga yozilgan qiymatni o'sha obyektning o'zi bilan olasiz.

2.2 Meros qolgan kalitlar

Endi Sardorning hisoblagichidagi xato:

const counts = {};
for (const word of ["osh", "constructor", "osh"]) {
  counts[word] = (counts[word] || 0) + 1;
}
console.log(counts.osh, counts.constructor);
console.log("toString" in counts, Object.hasOwn(counts, "toString"));
const safe = Object.create(null);
console.log("toString" in safe);

Konsolda:

2 function Object() { [native code] }1
true false
false

Bo'sh obyekt aslida bo'sh emas: u Object.prototype dan constructor, toString, hasOwnProperty kabi kalitlarni meros oladi (Prototip zanjiri). counts["constructor"] bo'sh joyda 0 emas, funksiyani qaytardi, + 1 esa uni satrga aylantirib, 1 ni yopishtirdi. Foydalanuvchi yozgan har qanday so'z kalitga aylansa, bunday so'z albatta topiladi.

Ikki yechim bor. Object.create(null) — prototipsiz, "toza" obyekt. Yoki Map — unda meros kalitlar umuman yo'q. Foydalanuvchidan kelgan kalitlar uchun xavfsizroq yo'l — Map. __proto__ kabi kalitlar orqali prototipni buzish hujumini Prototype pollution darsida ko'rgan edik — Map unga ham chidamli.

2.3 Aylanish tartibi

Map kalitlarni doim qo'shilgan tartibda aylanadi. Obyektning tartibi esa boshqacha qoidaga bo'ysunadi:

const orders = {};
orders.osh = 3;
orders["12"] = "stol";
orders.manti = 2;
orders["2"] = "stol";
orders["-1"] = "xato";
console.log(Object.keys(orders));

const ordersMap = new Map([
  ["osh", 3], ["12", "stol"], ["manti", 2], ["2", "stol"],
]);
console.log([...ordersMap.keys()]);

Konsolda:

[ '2', '12', 'osh', 'manti', '-1' ]
[ 'osh', '12', 'manti', '2' ]

Obyektda avval butun son ko'rinishidagi kalitlar ("2", "12") — o'sish tartibida, keyin qolgan satrlar — qo'shilgan tartibda. "-1" butun son kaliti hisoblanmaydi (indeks manfiy bo'lmaydi), shuning uchun u oddiy satr kabi oxirida. Stol raqamlari yoki buyurtma id'lari bilan ishlasangiz, obyekt ularni "o'z-o'zidan" saralab yuboradi va siz kutgan tartib buziladi.

2.4 Hajm, tezlik va JSON

V8 obyektni odatda yashirin klass bilan saqlaydi (Hidden classes): bir xil maydonli ko'p obyekt uchun bu juda tez. Lekin kalitlar tez-tez qo'shilib-o'chirilsa, delete obyektni sekinroq "lug'at rejimi"ga o'tkazadi. Sinab ko'rdik: n ta kalit qo'shiladi, har birida 100 qadam oldingisi o'chiriladi (oyna kabi). 100 000 dan 800 000 gacha qadamda obyekt Map dan taxminan 1,4–1,6 baravar sekin chiqdi. Ikkalasi ham O(n) — farq o'zgarmas ko'paytuvchida.

JSON bilan ishlashda Map ni avval obyektga aylantirish kerak:

const menu = new Map([["osh", 35000], ["manti", 30000]]);
console.log(JSON.stringify(menu));
const json = JSON.stringify(Object.fromEntries(menu));
console.log(json);
const back = new Map(Object.entries(JSON.parse(json)));
console.log(back.get("osh"), back.size);

Konsolda:

{}
{"osh":35000,"manti":30000}
35000 2

JSON.stringify(map) — bo'sh {}: Map yozuvlari oddiy xususiyat emas, JSON ularni ko'rmaydi. Bu jim xato — ma'lumot yo'qoladi, lekin hech qanday ogohlantirish chiqmaydi.

2.5 Qaysi birini tanlash

Set — qiymati yo'q Map: takrorlarni olib tashlash va "ko'rdimmi?" tekshiruvi uchun. Ikki to'plamning kesishmasi kabi amallarni Set to'plam metodlari darsida ko'rgan edik. WeakMap esa kalit obyektni xotirada ushlab turmaydi — obyekt boshqa joyda kerak bo'lmay qolsa, yozuv ham yo'qoladi (WeakMap va WeakRef).

Tekshirib ko'ring: Qaysi kalit birinchi chiqadi: Object.keys({ b: 1, 10: 2, a: 3, 2: 4 })?

3. LRU kesh: muammo

Endi Sardorning keshi. Har ochilgan taom sahifasi obyektga yoziladi va hech qachon o'chmaydi. Menyuda 300 ta taom, har biri rasmlar ro'yxati va izohlari bilan — kesh telefon xotirasini asta-sekin yeydi. Keshga sig'im kerak: masalan, ko'pi bilan 50 ta taom. Joy tugasa, qaysi birini chiqarish kerak?

Memoization darsida javobni ko'rgan edik: LRU (Least Recently Used) — eng uzoq vaqt hech kim so'ramagan yozuv chiqariladi. Mehmon hozirgina ochgan taomni yana ochishi ehtimoli katta, bir soat oldin ko'rganini — kamroq.

Keshdan foydalanishning ikki natijasi bor. Kalit keshda bo'lsa — keshga tushish (cache hit): javob darhol. Bo'lmasa — keshdan o'tish (cache miss): serverga borish kerak. Yaxshi keshning maqsadi — tushishlar ulushini oshirish.

Bizga ikki amal kerak, ikkalasi ham O(1):

• get(key) — qiymatni qaytaradi va yozuvni "yangi ishlatilgan" qiladi;
• put(key, value) — yozadi; sig'imdan oshsa, eng eskisini chiqaradi.

Bu masala LeetCode'da "146. LRU Cache" nomi bilan mashhur (leetcode.com/problems/lru-cache) — intervyularning eng ko'p so'raladigan dizayn masalalaridan biri.

4. Sodda yechim: tartib massivda

Eng birinchi g'oya: kalitlarni ishlatilish tartibida massivda saqlash. Boshida — eng eskisi, oxirida — eng yangisi. Qiymatlar alohida Map da:

class ArrayLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.order = []; // eng eskisi — boshida
    this.values = new Map();
  }
  get(key) {
    const i = this.order.indexOf(key); // O(k)
    if (i === -1) return undefined;
    this.order.splice(i, 1); // O(k)
    this.order.push(key);
    return this.values.get(key);
  }
  put(key, value) {
    const i = this.order.indexOf(key);
    if (i !== -1) this.order.splice(i, 1);
    this.order.push(key);
    this.values.set(key, value);
    if (this.order.length > this.capacity) {
      this.values.delete(this.order.shift()); // O(k)
    }
  }
}

const cache = new ArrayLRU(2);
cache.put("osh", 35000);
cache.put("manti", 30000);
cache.get("osh");
cache.put("choy", 5000);
console.log(cache.order); // [ 'osh', 'choy' ]

Ishlaydi, lekin har amalda indexOf, splice va shift bor — har biri butun massivni ko'radi (JS o'rnatilgan amallarining narxi). Sig'im k bo'lsa, har amal O(k). 50 ta taomda sezilmaydi, lekin serverdagi 10 000 yozuvli keshda har so'rov 10 000 qadam.

5. Yaxshi yechim: Map tartibi

5.1 G'oya

Map kalitlarni qo'shilgan tartibda saqlaydi. Demak, tartib massivi kerak emas — Map ning o'zi tartib:

• Yangilash: kalitni delete qilib, qayta set qilsak — u oxiriga o'tadi.
• Eng eskisi: map.keys().next().value — birinchi kalit.

Ikkalasi ham hash jadval amallari — o'rtacha O(1). Qadamlarda Map ichidagi tartibni kuzating:

Memoization darsida xuddi shu hiyla funksiya o'ramida (lruKesh) ishlatilgan edi. Bu yerda u alohida klass: keshni istalgan joyda — taom tafsilotlari, rasm, server javobi uchun — ishlatish mumkin.

5.2 Murakkablik

get — has, get, delete, set: to'rtta hash amali, O(1). put — delete, set va kerak bo'lsa birinchi kalitni olib o'chirish, O(1). Xotira — O(k): ko'pi bilan k + 1 ta yozuv.

Shu yerda nazariya tugadi deb o'yladik. O'lchov boshqacha dedi.

6. O'lchov: Map ning yashirin narxi

Uchta keshni bir xil ish bilan sinadik: 100 000 ta so'rov, kalitlar 0 dan 2k gacha (urug'li generator bilan — har safar bir xil ketma-ketlik). So'ralgan kalit keshda bo'lsa — get, bo'lmasa — put. Sig'im k ni ikki baravar oshirib boramiz (benchmarking darsidagi usul: har k alohida jarayonda, isitish, 7 o'lchov medianasi):

ArrayLRU kutilganidek: k ikki baravar — vaqt ham taxminan ikki baravar, har amal O(k). Uchinchi ustundagi Map + ro'yxat (keyingi bo'limda) deyarli joyida turibdi — haqiqiy O(1). Lekin Map LRU ham asta o'syapti: har safar 1,4–1,6 baravar. Nega?

Sababini topish uchun faqat chiqarib yuborishni o'lchadik: kesh to'la, har put yangi kalit qo'shadi va eng eskisini chiqaradi:

// tayyorlash (o'lchanmaydi): k ta yozuvli to'la kesh
const cache = new LRUCache(k);
for (let i = 0; i < k; i++) cache.put(i, i);
// o'lchanadi: 100 000 ta yangi kalit — har biri bittasini chiqaradi
const start = performance.now();
for (let i = k; i < k + 100000; i++) cache.put(i, i);
const ms = performance.now() - start;

Map LRU da chiqarib yuborish narxi sig'imga chiziqli bog'liq bo'lib chiqdi: k ikki baravar — vaqt ham deyarli ikki baravar. Sababi V8 ning Map ni qanday saqlashida. O'tgan darsda aytganimizdek, yozuvlar qo'shilish tartibida massivda turadi.

delete yozuvni massivdan darhol olib tashlamaydi — uning o'rniga "o'chirilgan" belgisi qo'yiladi, teshik qoladi. Bu o'tgan darsdagi qabr toshiga o'xshaydi. Aylanish (keys(), for...of) massivni boshidan yuradi va har teshikni tekshirib, o'tkazib yuboradi. Teshiklar faqat jadval qayta qurilganda (rehashing) tozalanadi. Bu V8 manba kodidagi izohlarda yozilgan (ordered-hash-table.h: o'chirilgan yozuvlar ham band joy hisoblanadi, iterator ularni tekshirib o'tadi).

Biz esa doim eng eskisini — massiv boshidagini o'chiramiz. Boshda teshiklar to'planadi, keys().next() esa birinchi tirik kalitni topguncha ularning hammasidan o'tadi. Teshiklar soni k ga yaqin bo'lishi mumkin — demak, chiqarib yuborish o'rtacha O(k). Buni o'lchov tasdiqladi; ichki sabab esa manba kodiga tayangan tushuntirish.

Bu V8 ning ichki tafsiloti, standartda yozilmagan. Kichik keshda (yuzlab yozuv) Map LRU baribir yetarli va juda qisqa. Lekin katta keshda — boshqa yo'l kerak.

Diqqat: "Big-O bo'yicha O(1)" — bu dvigatel amalni haqiqatan O(1) da bajaradi degan taxmin. Taxminni o'lchov bilan tekshiring (Performansni o'lchash). Bu yerda bitta qator (keys().next()) butun algoritmning sinfini o'zgartirdi.

7. Klassik yechim: Map + ikki tomonlama ro'yxat

7.1 G'oya

Tartibni Map ga ishonmay, o'zimiz saqlaymiz — ikki tomonlama bog'langan ro'yxat (doubly linked list) bilan (Linked list masalalari). Har tugunda prev va next havolasi bor, shuning uchun tugunni ro'yxatning istalgan joyidan O(1) da uzib olish mumkin — qo'shnilari bir-biriga ulanadi, xolos. Map esa kalitdan tugunning o'ziga olib boradi:

map: osh → ●   manti → ●   choy → ●

head ⇄ [manti] ⇄ [osh] ⇄ [choy] ⇄ tail
       eng eski             eng yangi

• get: map dan tugunni topamiz (O(1)), uni joyidan uzamiz (O(1)) va dumning oldiga qo'yamiz (O(1)).
• put sig'imdan oshsa: head.next — eng eski tugun. Uni uzamiz va map dan o'chiramiz.

head va tail — soxta tugunlar (dummy nodes): ular hech qanday ma'lumot saqlamaydi, faqat ro'yxat chetlarini belgilaydi. Shunda bo'sh ro'yxat yoki chetdagi tugun uchun alohida if yozish shart emas — Linked list masalalari darsidagi dummy head hiylasi.

7.2 Kod

class CacheNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LinkedLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // kalit → tugun
    // soxta bosh va dum: chetlarda null tekshiruvi kerak bo'lmaydi
    this.head = new CacheNode(null, null); // eng eskisidan oldin
    this.tail = new CacheNode(null, null); // eng yangisidan keyin
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  append(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (node === undefined) return undefined;
    this.remove(node);
    this.append(node); // eng yangi — dumning oldiga
    return node.value;
  }

  put(key, value) {
    const old = this.map.get(key);
    if (old !== undefined) {
      old.value = value;
      this.remove(old);
      this.append(old);
      return;
    }
    const node = new CacheNode(key, value);
    this.map.set(key, node);
    this.append(node);
    if (this.map.size > this.capacity) {
      const oldest = this.head.next; // boshdan keyingisi — eng eski
      this.remove(oldest);
      this.map.delete(oldest.key);
    }
  }

  keys() {
    const result = [];
    for (let n = this.head.next; n !== this.tail; n = n.next) {
      result.push(n.key);
    }
    return result;
  }
}

const cache = new LinkedLRU(3);
cache.put("osh", 35000);
cache.put("manti", 30000);
cache.put("lag'mon", 28000);
console.log(cache.get("osh"));
cache.put("choy", 5000);
console.log(cache.get("manti"));
console.log(cache.keys().join(", "));

Konsolda:

35000
undefined
lag'mon, osh, choy

Natija vizualdagi Map LRU bilan aynan bir xil. Farq ichkarida: endi eng eskisini topish — this.head.next, bitta havola. Teshiklar yo'q, chunki biz Map ning tartibiga tayanmayapmiz — Map faqat "kalit → tugun" qidiruvi uchun.

Tugun klassi ListNode ga o'xshaydi, lekin unda prev va key ham bor — shuning uchun alohida nom: CacheNode. Node deb atamadik: Linked list darsida aytilganidek, brauzerda bu nom DOM klassiga tegishli.

Nima uchun tugunda key ham saqlanadi? Eng eski tugunni chiqarganda uni map dan ham o'chirish kerak — buning uchun kalitni bilishimiz shart. Bu intervyuda eng ko'p unutiladigan detal.

7.3 Murakkablik

* V8 da chiqarib yuborish teshiklar tufayli amalda O(k) gacha. Ro'yxatli versiyaning xotirasi biroz ko'p (har yozuvga tugun obyekti), lekin hammasi O(k).

Tekshirib ko'ring: LinkedLRU(2) ga ketma-ket: put("osh"), put("manti"), get("osh"), put("choy"), put("manti"). Oxirida keshda qaysi kalitlar qoladi va qaysi tartibda (eskidan yangiga)?

8. Chegaraviy holatlar

• Sig'im 0. put yozuvni qo'shadi va darhol o'zini chiqaradi — kesh doim bo'sh. Kod buni to'g'ri bajaradi, lekin bunday keshning ma'nosi yo'q: konstruktorda sig'im musbat butun son ekanini tekshirgan ma'qul.
• Sig'im 1. Har yangi kalit oldingisini chiqaradi. Testda albatta sinang — "bitta element" xatolari shu yerda chiqadi.
• Bor kalitni put qilish. Qiymat yangilanadi va kalit "yangi" bo'ladi, lekin hech kim chiqarilmasligi kerak: size o'zgarmagan.
• Qiymat undefined bo'lsa. Bizning get "topilmadi" uchun ham undefined qaytaradi — ikkalasini farqlab bo'lmaydi. Kerak bo'lsa has(key) metodini qo'shing yoki undefined ni saqlashni taqiqlang.
• Bo'sh keshdan eng eskisi. Map versiyada keys().next().value — undefined; ro'yxatda head.next — tail. Bizning kod bu holatga tushmaydi (chiqarish faqat size > capacity da), lekin uni o'zgartirsangiz — esda tuting.

9. Ko'p uchraydigan xatolar

9.1 get da yangilashni unutish

get faqat qiymatni qaytarib, kalitni oxiriga ko'chirmasa — bu LRU emas, FIFO (birinchi kelgan — birinchi chiqadi). Tez-tez so'raladigan taom ham vaqti kelib chiqib ketadi. Tuzatish: get da ham delete + set (yoki remove + append).

9.2 Obyektni kesh qilish

cache[id] = data — raqamli id'lar o'z-o'zidan saralanadi (tartib buziladi), size yo'q, "constructor" kabi kalitlar meros. Tuzatish: kesh — doim Map.

9.3 Chiqarilgan tugunni map da qoldirish

Ro'yxatli versiyada tugunni ro'yxatdan uzib, map.delete(oldest.key) ni unutsangiz — map o'sib boraveradi va get ro'yxatda yo'q tugunni "topadi". Xotira sizib chiqadi (Xotira sizishlari). Tuzatish: chiqarishda ikkala tuzilmadan ham o'chiring.

9.4 JSON.stringify(map)

Natija — {}, ma'lumot jimgina yo'qoladi. Tuzatish: Object.fromEntries(map) yoki [...map].

10. Mashqlar

1-mashq (oson): Qaysi tuzilma?

Har vazifa uchun obyekt, Map, Set yoki WeakMap ni tanlang va bir gap bilan sababini yozing:

1. Taom kartasi: name, price, category.
2. Bugun buyurtma bergan stol raqamlari — takrorsiz.
3. Mehmonlar izohlaridagi so'zlar soni.
4. Har DOM elementiga qo'shimcha ma'lumot (element sahifadan o'chsa — ma'lumot ham ketsin).

2-mashq (o'rta): Keshga tushish ulushi

LinkedLRU ga hits va misses hisoblagichlarini qo'shing (get da yangilanadi) hamda hitRate() metodini yozing — tushishlar ulushi, foizda, butun songa yaxlitlangan. Keyin sig'im 2 li keshga quyidagi so'rovlarni bering (keshda yo'q bo'lsa — put): osh, manti, osh, choy, manti, osh. Ulush necha foiz?

get(key) {
  const node = this.map.get(key);
  if (node === undefined) {
    this.misses++;
    return undefined;
  }
  this.hits++;
  this.remove(node);
  this.append(node);
  return node.value;
}

hitRate() {
  const total = this.hits + this.misses;
  return total === 0 ? 0 : Math.round((this.hits / total) * 100);
}

3-mashq (qiyin): Muddatli LRU va testlar

kurs/mashqlar/14/22-lru/lru.test.mjs faylida TtlLRU klassini yozing: LinkedLRU kabi, lekin har yozuvning yashash muddati bor (TTL — time to live, millisekundlarda). Konstruktor: new TtlLRU(capacity, ttl, now = () => Date.now()). put yozuvga expires = now() + ttl qo'yadi. get muddati o'tgan yozuvni o'chiradi va undefined qaytaradi. Vaqtni testda boshqarish uchun now funksiyasi parametr sifatida beriladi — haqiqiy soatni kutmaymiz (node:test).

Testlar:

1. Muddat ichida — qiymat qaytadi.
2. Muddat o'tgach — undefined va yozuv keshdan o'chgan.
3. Sig'im oshganda eng uzoq ishlatilmagani chiqadi.
4. Bor kalitni put qilish muddatni yangilaydi.

// kurs/mashqlar/14/22-lru/lru.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

class TtlLRU {
  constructor(capacity, ttl, now = () => Date.now()) {
    this.capacity = capacity;
    this.ttl = ttl;
    this.now = now;
    this.map = new Map();
    this.head = { next: null, prev: null };
    this.tail = { next: null, prev: this.head };
    this.head.next = this.tail;
  }
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  append(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
  }
  get(key) {
    const node = this.map.get(key);
    if (node === undefined) return undefined;
    if (this.now() >= node.expires) {
      this.remove(node); // muddati o'tgan — o'chiramiz
      this.map.delete(key);
      return undefined;
    }
    this.remove(node);
    this.append(node);
    return node.value;
  }
  put(key, value) {
    const old = this.map.get(key);
    if (old !== undefined) {
      this.remove(old);
      this.map.delete(key);
    }
    const expires = this.now() + this.ttl;
    const node = { key, value, expires, prev: null, next: null };
    this.map.set(key, node);
    this.append(node);
    if (this.map.size > this.capacity) {
      const oldest = this.head.next;
      this.remove(oldest);
      this.map.delete(oldest.key);
    }
  }
}

function fakeClock() {
  let time = 0;
  return { now: () => time, pass: (ms) => (time += ms) };
}

test("muddat ichida qiymat qaytadi", () => {
  const clock = fakeClock();
  const cache = new TtlLRU(2, 1000, clock.now);
  cache.put("osh", 35000);
  clock.pass(999);
  assert.equal(cache.get("osh"), 35000);
});

test("muddat o'tgach — undefined va o'chgan", () => {
  const clock = fakeClock();
  const cache = new TtlLRU(2, 1000, clock.now);
  cache.put("osh", 35000);
  clock.pass(1000);
  assert.equal(cache.get("osh"), undefined);
  assert.equal(cache.map.size, 0);
});

test("sig'im oshsa — eng uzoq ishlatilmagani chiqadi", () => {
  const clock = fakeClock();
  const cache = new TtlLRU(2, 1000, clock.now);
  cache.put("osh", 35000);
  cache.put("manti", 30000);
  cache.get("osh");
  cache.put("choy", 5000);
  assert.equal(cache.get("manti"), undefined);
  assert.equal(cache.get("osh"), 35000);
});

test("qayta put muddatni yangilaydi", () => {
  const clock = fakeClock();
  const cache = new TtlLRU(2, 1000, clock.now);
  cache.put("osh", 35000);
  clock.pass(800);
  cache.put("osh", 36000);
  clock.pass(800); // birinchi put'dan 1600 ms, ikkinchisidan 800
  assert.equal(cache.get("osh"), 36000);
});

✔ muddat ichida qiymat qaytadi (0.8395ms)
✔ muddat o'tgach — undefined va o'chgan (0.1475ms)
✔ sig'im oshsa — eng uzoq ishlatilmagani chiqadi (0.1185ms)
✔ qayta put muddatni yangilaydi (0.0996ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 84.4077

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga LRU uchun uchta qator qo'shing: massivli, Map li va ro'yxatli. Uchinchisiga "Amaliy chegara" ustunida o'lchovdagi raqamni yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| LRU kesh | massiv + indexOf | O(k) | O(k) |
| LRU kesh | Map tartibi | O(1)*, V8 da chiqarish O(k) gacha | O(k) |
| LRU kesh | Map + ikki tomonlama ro'yxat | O(1) | O(k) |

git add 14/MURAKKABLIK.md 14/22-lru
git commit -m "14/22: LRU kesh — Map va ikki tomonlama ro'yxat, TTL testlari"

11. Real ishda

• Brauzer va server keshlari. HTTP keshi, rasm keshi, DNS keshi, ma'lumotlar bazasining sahifa keshi — hammasida sig'im va chiqarish siyosati bor; LRU — eng ko'p uchraydigani. Redis'da maxmemory-policy allkeys-lru sozlamasi bor (Redis ni 27-qismda o'rganamiz).
• Kutubxonalar. npm'dagi lru-cache (sig'im, TTL, hajm bo'yicha cheklash) ichida ikki tomonlama ro'yxatdan foydalanadi. TanStack Query kabi so'rov kutubxonalari ham server javoblarini keshlaydi — ularni React qismlarida ko'ramiz.
• Obyekt yoki Map. Kod ko'rib chiqishda (code review) "foydalanuvchi kalitlari obyektda" — ko'p uchraydigan izoh. Object.create(null) yoki Map so'raladi.
• Intervyu. "LRU keshni O(1) da yozing" — klassik savol. Javobda Map + ikki tomonlama ro'yxat kutiladi; Map tartibi bilan qisqa yechimni aytsangiz, "u qaysi taxminga tayanadi?" deb so'rashadi.

Xulosa

• Obyekt kaliti satrga aylanadi (1 = "1", har obyekt = "[object Object]"), meros kalitlar bor, butun son kalitlar o'z-o'zidan saralanadi.
• Map — istalgan kalit, qo'shilish tartibi, size O(1), ko'p qo'shish-o'chirishda tezroq; Set — faqat "bormi?"; WeakMap — obyektga ma'lumot bog'lash.
• LRU kesh: get yozuvni yangilaydi, put sig'imdan oshsa eng eskisini chiqaradi.
• Map tartibi bilan LRU qisqa, lekin V8 da keys().next() o'chirilgan teshiklardan o'tadi: chiqarish k = 8 000 da ≈ 248 ms ga qarshi ≈ 10 ms.
• Map + ikki tomonlama ro'yxat (soxta bosh va dum bilan) — har amal haqiqiy O(1); tugunda kalit ham saqlanadi.

Keyingi dars: Rekursiv fikrlash — masalani o'zining kichikroq nusxasi orqali ifodalash, "ishonch sakrashi", rekursiya daraxti va rekursiyani stek bilan siklga aylantirish.

Manbalar

• MDN: "Map — Objects vs. maps" — developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
• ECMAScript 2025, 10.1.11.1 OrdinaryOwnPropertyKeys — butun son kalitlar tartibi — tc39.es/ecma262
• V8 manba kodi: src/objects/ordered-hash-table.h — o'chirilgan yozuvlar va qayta qurish — github.com/v8/v8
• LeetCode 146. LRU Cache — leetcode.com/problems/lru-cache
• npm: lru-cache — github.com/isaacs/node-lru-cache