Hash map bilan hisoblash naqshlari: chastota, ikki son yig'indisi, anagramma va takror

Qisqacha: Ko'p masalada sekinlik bitta savoldan keladi: "buni oldin ko'rganmidim?". Ro'yxatdan qidirsangiz — har savol O(n), jami O(n²). Ko'rilganlarni Map yoki Set ga yozsangiz — har savol o'rtacha O(1), jami O(n). Asosiy naqshlar: chastota hisoblagichi (count.set(x, (count.get(x) ?? 0) + 1)), "juftim oldin keldimi?" (two sum: seen.has(target - x)), kalit bo'yicha guruhlash (anagrammalar — harflari saralangan kalit), birinchi takror (Set). Narxi — O(n) qo'shimcha xotira.

Bu darsda

• Chastota hisoblagichi bilan eng ko'p uchragan narsani saralashsiz, O(n) da topasiz.
• Tartibsiz massivda yig'indisi berilgan songa teng juftni Map bilan bir o'tishda topasiz.
• Anagrammalarni (bir xil harflardan iborat so'zlarni) kalit bo'yicha guruhlaysiz.
• Set bilan takrorni tekshirasiz va Map hamda oddiy obyekt orasida to'g'ri tanlov qilasiz.

Oldin bilishingiz kerak: Prefix sum va difference array, Map, Set, Guruhlash: Object.groupBy, Ikki ko'rsatkich.

1. Nega bu kerak?

Asosiy murakkablik sinflari darsida savol bergan edik: «Bahor» bazasida 200 000 mijoz, takror telefon raqamlarini topish kerak. Hamma juftlarni solishtirish — 20 milliard amal. O'shanda javob "Set ishlatish" edi. Bugun shu javobni naqshga aylantiramiz — ko'p masalaga qo'llanadigan qolipga.

Bu naqshni bir necha darsdan beri ko'ryapmiz. Big-O da includes o'rniga Set.has. Suriluvchi oynada — oynadagi taomlar hisoblagichi. O'tgan darsda — prefixlar Map i. Hammasida bitta g'oya: ko'rganingizni eslab qoling, keyin qidirmang — so'rang.

Oshxonadan o'xshatish. Omborchi har kuni "guruch bormi?" deb so'rashsa, butun omborni aylanib chiqadi. Aqlli omborchi eshik oldiga daftar qo'yadi: nima, qancha, qaysi tokchada. Daftarni yuritish biroz vaqt va joy oladi, lekin har savolga bir zumda javob beradi. Map — o'sha daftar.

2. Chastota hisoblagichi

2.1 Eng ko'p buyurtilgan taom

Kun oxirida Jasur aka so'radi: "Bugun qaysi taom eng ko'p buyurtildi?" Uch xil yechim bor:

1. Har taom uchun butun ro'yxatni sanash (filter(...).length) — O(n · k), k — turli taomlar. Eng yomoni O(n²).
2. Saralab, yonma-yon turganlarni sanash — O(n log n).
3. Chastota hisoblagichi (frequency counter) — har buyurtmani bir marta ko'rib, Map da sanash — O(n). "Chastota" — biror narsa necha marta uchragani: oshning chastotasi 3 — osh uch marta buyurtilgan.

Uchinchisini qadamma-qadam ko'ramiz. Pastdagi "o'zgaruvchilar" — hisoblagichning holati:

Hisoblagich qatori naqshning yuragi: count.set(dish, (count.get(dish) ?? 0) + 1). Taom hali yo'q bo'lsa count.get — undefined, ?? 0 uni nolga aylantiradi (?? operatori). Ikkinchi sikl hisoblagichni aylanadi — turli taomlar soni k, odatda n dan ancha kichik. Jami O(n). Xotira — O(k).

Bir qatorlik variant ham bor: Object.groupBy(orders, (d) => d) (Guruhlash) — har taomga uning nusxalari massivi. Soni kerak bo'lsa — .length. U ham O(n), lekin har buyurtmani massivga yozadi, ya'ni xotira O(n). Bizga faqat son kerak — hisoblagich tejamkorroq.

2.2 Map yoki oddiy obyekt?

Hisoblagichni oddiy obyekt bilan ham yozish mumkin: counts[w] = (counts[w] ?? 0) + 1. Ko'pincha ishlaydi. Lekin bitta tuzoq bor:

const words = ["osh", "constructor", "osh"];

const counts = {};
for (const w of words) counts[w] = (counts[w] ?? 0) + 1;
console.log(counts.osh); // 2
console.log(counts.constructor);

const map = new Map();
for (const w of words) map.set(w, (map.get(w) ?? 0) + 1);
console.log(map.get("constructor")); // 1

Konsolda:

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

Oddiy obyekt prototipdan meros olgan kalitlarga ega: constructor, toString, hasOwnProperty. counts.constructor bo'sh emas edi — u Object funksiyasi. ?? 0 ishlamadi (qiymat null ham, undefined ham emas), va funksiya satrga aylanib, 1 qo'shildi. Foydalanuvchi matni (izoh, so'z, teg) kalit bo'lsa — bu haqiqiy xato manbai. Map da faqat siz qo'ygan kalitlar bor.

Algoritmlarda — Map va Set. Oddiy obyekt — JSON bilan ishlaganda va kalitlar oldindan ma'lum bo'lganda. Object.create(null) — prototipsiz obyekt, u ham xavfsiz, lekin qolgan farqlar qoladi.

Tekshirib ko'ring: Buyurtmalar [101, 102, 101] — raqamlar. Hisoblagichni oddiy obyektda yuritsak, Object.keys(counts) nima qaytaradi va nega bu muammo bo'lishi mumkin?

3. "Juftim oldin keldimi?" — ikki son yig'indisi

3.1 Tartibsiz to'lovlar

Ikki ko'rsatkich darsida Dilshod aka 58 000 so'mga ikkita taom so'ragan edi. Narxlar saralangan edi. Endi boshqa vaziyat: kassadagi to'lovlar kelish tartibida, saralanmagan. Buxgalter so'radi: "Yig'indisi aniq 58 000 bo'lgan ikki to'lov bormi? Ularning raqami?" Saralasak, to'lovlarning asl raqami (indeksi) yo'qoladi — yoki alohida saqlash kerak.

G'oya — o'tgan darsdagi "prefix + Map" ning soddaroq ko'rinishi. Har to'lovda savol beramiz: "menga juft bo'ladigan summa — target - joriy — oldin kelganmi?" Ko'rilganlarni Map da saqlaymiz: summa → indeks.

E'tibor bering: 35 kelganda uning jufti (23) hali kelmagan edi — seen da yo'q. Lekin 35 ni eslab qoldik. 23 kelganda u "35 kerak" dedi va topdi. Har juft ikkinchi elementi kelganda topiladi. Shuning uchun bir o'tish yetadi.

Tartibga yana e'tibor bering: avval so'raymiz, keyin yozamiz. Teskari qilsak, 29 + 29 = 58 holatida bitta to'lov o'zi bilan juft bo'lib qoladi.

3.2 O'lchov: uch yechim

Juft yo'q holat (eng yomoni), olcha, har n alohida jarayonda:

Hamma juftlar usuli 2 000 dan 16 000 gacha har ikki baravarda to'rt baravar sekinlashdi (1,5 → 6,1 → 23 → 91 ms) — million to'lovda u soatlar oladi, shuning uchun o'lchamadik. Qolgan ikkitasi ikki baravardan biroz ko'proq o'sdi: Map ×2,2–2,3 (katta jadval keshga sig'maydi), saralash ×2,1–2,2 (n log n). Map taxminan uch baravar tez.

Unda saralash kerak emasmi? Tanlov xotiraga bog'liq. Map — O(n) qo'shimcha xotira. Joyida sort + ikki ko'rsatkich — deyarli O(1), lekin asl tartib yo'qoladi. Xotira tor bo'lsa yoki ma'lumot allaqachon saralangan bo'lsa — ikki ko'rsatkich. Aks holda — Map.

Tekshirib ko'ring: To'lovlar [29, 10, 29], maqsad 58. twoSum nima qaytaradi? Agar seen.set ni if dan oldin yozsak-chi?

4. Kalit bo'yicha guruhlash: anagrammalar

4.1 Masala

«Bahor» aksiya uchun promo-kodlar tarqatdi. Ba'zi mijozlar kodni harflarini almashtirib yozib yuboradi: BAHOR o'rniga HOBAR. Tizim bir xil harflardan iborat kodlarni bir guruhga yig'ishi kerak. Bir xil harflardan, boshqa tartibda tuzilgan so'zlar anagramma deyiladi: BAHOR va ROBAH, OSH va SHO.

Ikki so'z anagramma ekanini qanday tekshirish mumkin? Harflarini saralang: ikkalasidan ham ABHOR chiqsa — anagramma. Bu saralangan shakl — guruhning kaliti. Har kodni o'z kaliti bo'yicha Map ga solamiz:

function groupCodes(codes) {
  const groups = new Map(); // kalit → shu kalitli kodlar
  for (const code of codes) {
    const key = [...code].sort().join(""); // harflar tartiblandi
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(code);
  }
  return [...groups.values()];
}

const codes = ["BAHOR", "OSH", "HOBAR", "NON", "SHO", "ROBAH"];
console.log(groupCodes(codes));

Konsolda:

[ [ 'BAHOR', 'HOBAR', 'ROBAH' ], [ 'OSH', 'SHO' ], [ 'NON' ] ]

[...code] — satrni harflar massiviga yoyadi (Spread), sort() — harflarni alifbo tartibida, join("") — qaytadan satr. Narxi: n ta kod, har biri L harfli: har kalit O(L log L), jami O(n · L log L). Hamma juftlarni anagrammaga tekshirish esa O(n² · L log L) bo'lardi.

4.2 Kalit tanlash — naqshning asosi

Guruhlash naqshida eng muhim qaror — kalit. U shunday bo'lishi kerakki, "bir guruh" degan narsalar aynan bir xil kalit bersin, boshqalari — boshqa. Misollar:

4.3 Ikki so'zni tekshirish: saralashsiz

Faqat ikkita kodni solishtirish kerak bo'lsa ("bu mijoz kodi BAHOR ning anagrammasimi?"), saralash shart emas. Hisoblagich bilan bir o'tishda tekshirsa bo'ladi: birinchi so'z harflarini sanaymiz, ikkinchisinikini ayiramiz. Biror harf manfiyga tushsa — ikkinchi so'zda u ortiqcha:

function isAnagram(a, b) {
  if (a.length !== b.length) return false; // eng arzon tekshiruv
  const count = new Map();
  for (const ch of a) count.set(ch, (count.get(ch) ?? 0) + 1);
  for (const ch of b) {
    const left = (count.get(ch) ?? 0) - 1;
    if (left < 0) return false; // b da ortiqcha harf
    count.set(ch, left);
  }
  return true;
}

console.log(isAnagram("BAHOR", "ROBAH")); // true
console.log(isAnagram("OSH", "OSS")); // false

Saralash bilan — O(L log L), hisoblagich bilan — O(L). Uzunliklar teng va hech bir harf manfiyga tushmagan bo'lsa, hammasi aynan nolga tushgan — qo'shimcha tekshiruv kerak emas. Bu funksiya hali "Bahor" va "bahor" ni turli deb hisoblaydi, bo'sh joylarni ham harf deb sanaydi. Matnni avval normallash kerak — keyingi darsda.

4.4 Kalit — satr

Kalit satr bo'lishi muhim. Map da obyekt yoki massiv kalit bo'lsa, u havola bo'yicha solishtiriladi: ikkita ["A","B"] — ikki xil kalit (Havola semantikasi). Shuning uchun massivni join bilan satrga aylantirdik.

5. Set: borligini tekshirish va birinchi takror

Ba'zan son ham, indeks ham kerak emas — faqat "bormi?" savoli. Buning uchun Set. Ikki tipik masala:

function firstRepeat(ids) {
  const seen = new Set();
  for (const id of ids) {
    if (seen.has(id)) return id; // ikkinchi marta ko'rdik
    seen.add(id);
  }
  return null;
}

console.log(firstRepeat([104, 101, 107, 101, 104])); // 101
console.log(firstRepeat([1, 2])); // null

const phones = ["+998 90 000 00 01", "+998 90 000 00 02",
  "+998 90 000 00 01"];
console.log(new Set(phones).size === phones.length); // false

Birinchi funksiya — "ikkinchi nusxasi eng birinchi kelgan" raqam: 101. Diqqat: shartni aniq o'qing. "Birinchi takrorlanadigan element" boshqa ma'noni ham berishi mumkin — ro'yxatda birinchi turgan va takrorlanadigan: 104. Bu ikkinchi ma'no uchun avval hisoblagich yasash va keyin ro'yxatni boshidan aylanish kerak — 2-mashq shu haqida.

Ikkinchi misol — "hamma qiymat takrorsizmi?" savolining eng qisqa javobi: Set takrorlarni tashlaydi, o'lchami kichraysa — takror bor edi. O(n) vaqt va xotira.

6. Narxi va chegaralari

6.1 Xotira

Har naqsh tezlikni xotira evaziga oladi (vaqt va xotira almashinuvi). n ta element — Map da n tagacha yozuv. Million yozuvli Set taxminan 20 MB edi. Xotira tor bo'lsa — saralash + ikki ko'rsatkich (joyida).

6.2 "O'rtacha" so'zi

Map va Set amallari o'rtacha O(1). Juda omadsiz holatda ko'p kalit bitta "katakka" tushadi va qidiruv sekinlashadi. Buning sabablarini va dvigatellar qanday himoyalanishini Hash table ichidan darsida ko'ramiz. Kundalik ishda bu deyarli uchramaydi. O'lchovimizdagi ×2,3 nisbat esa boshqa narsa — katta jadval protsessor keshiga sig'magani (Massiv xotirada).

6.3 Chegaraviy holatlar

• Bo'sh ro'yxat. Hisoblagich bo'sh, top — null. twoSum([], 58) — null. Natija "yo'q" ekanini qaytaring, xato emas.
• Bitta element. Juft yo'q; takror yo'q; chastota — 1.
• Takrorlar. twoSum da [29, 29] — to'g'ri juft. Hisoblagichda tenglik: ikki taom bir xil ko'p bo'lsa, qaysi biri qaytishini kelishib oling (bizda — birinchi uchragani, chunki > ishlatdik).
• Manfiy sonlar va nol. Map uchun farqi yo'q: target - x manfiy bo'lsa ham kalit. Faqat -0 va 0 bitta kalit hisoblanadi.
• NaN. Map va Set da NaN o'ziga teng hisoblanadi (=== dan farqli) — bitta kalit. includes ham NaN ni topadi, indexOf — yo'q.

7. Ko'p uchraydigan xatolar

7.1 Sikl ichida includes yoki indexOf

Eng ko'p uchraydigan yashirin O(n²). Tuzatish: sikldan oldin Set yasang (JS amallarining narxi).

7.2 || 0 va ?? 0

Aslida ikkalasi ham ishlaydi, chunki son 0 bo'lgan kalit hisoblagichda bo'lmaydi. Lekin qiymat 0 bo'lishi mumkin bo'lgan Map da || 0 jim xato beradi. Tuzatish: odat qiling — ?? 0.

7.3 Obyekt yoki massivni kalit qilish

map.set([1, 2], "x"); map.get([1, 2]) — undefined: ikki xil massiv. Tuzatish: satr kalit — [1, 2].join(",").

7.4 Yozishni so'rashdan oldin qilish

twoSum da element o'zi bilan juft bo'ladi. Tuzatish: avval so'rang, keyin yozing.

8. Mashqlar

1-mashq (oson): Naqshni tanlang

Har masala uchun naqshni (hisoblagich, "juftim oldin keldimi", guruhlash, Set) va murakkablikni ayting:

• (a) Har ofitsiant nechta buyurtma olgan?
• (b) Telefon raqamlari ichida takror bormi?
• (c) Ikki mehmonning hisob yig'indisi aniq 100 000 bo'lgan juftlik bormi (tartibsiz)?
• (d) Buyurtmalarni sana bo'yicha kunlarga ajratish.

2-mashq (o'rta): Ro'yxatda birinchi takrorlanadigan

firstRepeatedInOrder(ids) — ro'yxatda birinchi turgan va kamida ikki marta uchraydigan raqamni qaytarsin. [104, 101, 107, 101, 104] → 104 (darsdagi firstRepeat 101 qaytargan edi). O(n) vaqt.

Ishora: ikki o'tish. Birinchisida hisoblagich, ikkinchisida ro'yxatni boshidan aylanib, soni 1 dan katta birinchisini qaytaring.

function firstRepeatedInOrder(ids) {
  const count = new Map();
  for (const id of ids) count.set(id, (count.get(id) ?? 0) + 1);
  for (const id of ids) {
    if (count.get(id) > 1) return id;
  }
  return null;
}

console.log(firstRepeatedInOrder([104, 101, 107, 101, 104])); // 104
console.log(firstRepeatedInOrder([1, 2, 3])); // null

3-mashq (qiyin): Hash naqshlari testlari

kurs/mashqlar/14/10-hash/hash.test.mjs faylida darsdagi twoSum, groupCodes, firstRepeat va eng ko'p taomni topuvchi topDish(orders) ni (bo'sh ro'yxatda null) yozing. Testlar (node:test):

1. twoSum 300 ta urug'li tasodifiy massivda (uzunligi 0–30, manfiylar bilan) — topilgan indekslar har xil va yig'indi to'g'ri; topilmasa — hamma juftlar usuli ham topmaydi.
2. twoSum([29, 29], 58) → [0, 1], twoSum([29], 58) → null.
3. groupCodes — har guruh ichidagi kodlar bir xil kalitga ega, guruhlar soni turli kalitlar soniga teng.
4. topDish — bo'sh → null; "constructor" kabi taom nomi bilan ham to'g'ri sanaydi.

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

function twoSum(payments, target) {
  const seen = new Map();
  for (let i = 0; i < payments.length; i++) {
    const need = target - payments[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(payments[i], i);
  }
  return null;
}

const keyOf = (code) => [...code].sort().join("");

function groupCodes(codes) {
  const groups = new Map();
  for (const code of codes) {
    const key = keyOf(code);
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(code);
  }
  return [...groups.values()];
}

function topDish(orders) {
  const count = new Map();
  for (const dish of orders) {
    count.set(dish, (count.get(dish) ?? 0) + 1);
  }
  let top = null;
  for (const [dish, n] of count) {
    if (top === null || n > count.get(top)) top = dish;
  }
  return top;
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}
const random = makeRandom(2026);

test("twoSum — hamma juftlar usuli bilan mos", () => {
  for (let t = 0; t < 300; t++) {
    const n = random() % 31;
    const arr = Array.from({ length: n }, () => (random() % 41) - 20);
    const target = (random() % 41) - 20;
    const found = twoSum(arr, target);
    if (found) {
      const [i, j] = found;
      assert.ok(i < j);
      assert.equal(arr[i] + arr[j], target);
    } else {
      for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
          assert.notEqual(arr[i] + arr[j], target);
        }
      }
    }
  }
});

test("twoSum — takror va bitta element", () => {
  assert.deepEqual(twoSum([29, 29], 58), [0, 1]);
  assert.equal(twoSum([29], 58), null);
});

test("groupCodes — kalitlar to'g'ri", () => {
  const codes = ["BAHOR", "OSH", "HOBAR", "NON", "SHO", "ROBAH"];
  const groups = groupCodes(codes);
  for (const g of groups) {
    assert.equal(new Set(g.map(keyOf)).size, 1);
  }
  assert.equal(groups.length, new Set(codes.map(keyOf)).size);
});

test("topDish — bo'sh va meros kalitlar", () => {
  assert.equal(topDish([]), null);
  const orders = ["osh", "constructor", "constructor"];
  assert.equal(topDish(orders), "constructor");
});

✔ twoSum — hamma juftlar usuli bilan mos (2.8549ms)
✔ twoSum — takror va bitta element (0.7269ms)
✔ groupCodes — kalitlar to'g'ri (0.7365ms)
✔ topDish — bo'sh va meros kalitlar (0.2052ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 83.0749

4-mashq: Amaliy tajriba — hash qatorlari

kurs/mashqlar/14/MURAKKABLIK.md ga bugungi to'rt naqshni qo'shing. "Juftlik" masalasi uchun uch yechimni yonma-yon yozing: hamma juftlar, saralash + ikki ko'rsatkich, Map.

| Masala | Naqsh | Vaqt | Xotira |
|---|---|---|---|
| Eng ko'p taom | hisoblagich (Map) | O(n) | O(k) |
| Juftlik, tartibsiz | hamma juftlar | O(n²) | O(1) |
| Juftlik, tartibsiz | toSorted + ikki ko'rsatkich | O(n log n) | O(n) |
| Juftlik, tartibsiz | Map — juftim oldin keldimi | O(n) o'rt. | O(n) |
| Anagramma guruhlari | kalit bo'yicha Map | O(n · L log L) | O(n · L) |
| Birinchi takror | Set | O(n) | O(n) |

git add 14/MURAKKABLIK.md 14/10-hash
git commit -m "14/10: hash naqshlari, ikki tomonlama testlar"

9. Real ishda

• Analitika. "Eng ko'p sotilgan mahsulot", "eng faol foydalanuvchi", "sahifa ko'rishlari" — hisoblagichlar. Katta tizimlarda ular Redis kabi xotiradagi kalit-qiymat bazalarida yuritiladi (keyingi qismlarda).
• Takrorni oldini olish. To'lov tizimlari bitta to'lov ikki marta o'tmasligi uchun so'rov identifikatorini Set ga o'xshash joyda eslab qoladi. Bu identifikator "idempotency key" deb ataladi — "takror so'rov kaliti"; uni backend qismida ko'ramiz.
• Ma'lumotni tozalash. Telefon, email, ismlarni normallab, kalit bo'yicha guruhlash — mijozlar bazasidagi takrorlarni birlashtirish.
• Intervyu. LeetCode'ning 1-masalasi — "Two Sum" — aynan shu dars. "Group Anagrams", "Valid Anagram", "Contains Duplicate", "Top K Frequent Elements", "First Unique Character" — hammasi Map/Set naqshlari. Intervyuchilar ko'pincha avval O(n²) yechimni, keyin "tezroq qila olasizmi?" deb so'raydi.

Xulosa

• Naqsh: ko'rganingizni Map/Set ga yozing, keyin qidirmang — so'rang. O(n²) → O(n), narxi — O(n) xotira.
• Hisoblagich: count.set(x, (count.get(x) ?? 0) + 1). Oddiy obyektda constructor kabi meros kalitlar tuzog'i bor — Map ishlating.
• "Juftim oldin keldimi?": avval seen.has(target - x), keyin seen.set(x, i). Million to'lovda Map ≈ 128 ms, saralash + ikki ko'rsatkich ≈ 358 ms.
• Guruhlash — to'g'ri kalit tanlash: anagrammalar uchun saralangan harflar. Kalit satr bo'lsin.
• Set — borligini tekshirish va takror; shartdagi "birinchi takror" ma'nosini aniqlang.

Keyingi dars: Matn algoritmlari — palindrom, anagramma, matnni teskari aylantirish va siqish, qism-satr qidirish va vazifalar ga apostrof va harf farqsiz qidiruv.

Manbalar

• MDN: Map, Set, "Map vs Object" bo'limi — developer.mozilla.org
• ECMAScript 2025: SameValueZero — Map va Set kalitlarni qanday solishtiradi — tc39.es/ecma262
• LeetCode masalalari: "Two Sum", "Group Anagrams", "Contains Duplicate", "Top K Frequent Elements" — leetcode.com (shartlar bu yerda o'zgartirib berilgan)