Tarkibga o'tish

Hash table

Oldingi mavzuda hashlash qanday ishlashini — hash funksiya, collision, separate chaining, open addressing va resize mexanizmlarini — ko'rdik. Bu mavzuda hash table'ni amaliy ma'lumotlar tuzilmasi sifatida qaraymiz: uning ikki asosiy shakli — hash map va hash set — qanday farqlanadi, algoritmik masalalarda qanday fikrlash bilan ishlatiladi va qachon boshqa tuzilmani tanlash kerak.

Hash map va hash set

Hash table'ning ikki asosiy ko'rinishi bor.

Hash map kalit va qiymat juftlarini saqlaydi. Kalit noyob; bir kalit bir qiymatga mos keladi. Qiymatni olish uchun kalit kerak.

kalit          qiymat
"user-101"  →  {ism: "Ali", yoshi: 28}
"user-202"  →  {ism: "Vali", yoshi: 35}
"user-303"  →  {ism: "Sami", yoshi: 22}

Hash set faqat kalitlarni saqlaydi — "bu element mavjudmi?" savoliga tez javob berish uchun. Qiymat yo'q; mavjudlik yoki yo'qligining o'zi ma'lumot.

{"olma", "nok", "uzum", "shaftoli"}

Hash set amalda odatda qiymatsiz map sifatida quriladi. Farq interfeysida: map PUT, GET va CONTAINS_KEY bersa, set ADD, CONTAINS va REMOVE beradi.

Algoritmik masalalarda ikkisini alohida tanlaymiz:

  • "Bu qiymat avval ko'rilganmi?" → hash set yetarli.
  • "Bu kalit uchun qanday qiymat bor?" → hash map kerak.
  • "Qancha marta uchradi?" yoki "Qaysi elementga nima mos?" → hash map kerak.

Asosiy API

Quyidagi pseudocode til-neytral interfeys ko'rinishida yozilgan. Amaliy kutubxona implementatsiyaga qarab qo'shimcha amallar taqdim etishi mumkin.

Hash map

MAP_CREATE()             → bo'sh map
MAP_PUT(map, key, value) → key ga value qo'yadi; mavjud bo'lsa yangilaydi
MAP_GET(map, key)        → key uchun value qaytaradi; yo'q bo'lsa topilmadi
MAP_CONTAINS(map, key)   → key mavjudligi: TRUE yoki FALSE
MAP_REMOVE(map, key)     → key va uning value'sini o'chiradi
MAP_SIZE(map)            → elementlar soni
MAP_KEYS(map)            → barcha kalitlar
MAP_VALUES(map)          → barcha qiymatlar
MAP_ENTRIES(map)         → barcha key-value juftlari

Hash set

SET_CREATE()            → bo'sh set
SET_ADD(set, value)     → value'ni qo'shadi; allaqachon bo'lsa o'zgarmaydi
SET_CONTAINS(set, value)→ mavjudligi: TRUE yoki FALSE
SET_REMOVE(set, value)  → value'ni o'chiradi
SET_SIZE(set)           → elementlar soni

Bosqichma-bosqich dry run

So'zlar chastotasini sanash misoli:

So'zlar: ["olma", "nok", "olma", "uzum", "nok", "olma"]

Boshlang'ich: map = {}

"olma": mavjud emas → map["olma"] = 1        map: {olma:1}
"nok":  mavjud emas → map["nok"]  = 1        map: {olma:1, nok:1}
"olma": mavjud      → map["olma"] = 1 + 1    map: {olma:2, nok:1}
"uzum": mavjud emas → map["uzum"] = 1        map: {olma:2, nok:1, uzum:1}
"nok":  mavjud      → map["nok"]  = 1 + 1    map: {olma:2, nok:2, uzum:1}
"olma": mavjud      → map["olma"] = 2 + 1    map: {olma:3, nok:2, uzum:1}

Natija: olma → 3, nok → 2, uzum → 1

Ko'rilgan elementlar ro'yxatini saqlash (hash set bilan):

Elementlar: [5, 3, 8, 3, 5, 9]

seen = {}

5: mavjud emas → ADD(5)     seen: {5}
3: mavjud emas → ADD(3)     seen: {5, 3}
8: mavjud emas → ADD(8)     seen: {5, 3, 8}
3: mavjud      → takrorlandi!

Vaqt va xotira murakkabligi

Amal Kutiladigan holat Eng yomon holat Sabab
PUT / ADD O(1) O(n) Hash bucket beradi; collision boshqariladi
GET / CONTAINS O(1) O(n) Hash kerakli hududni topadi
REMOVE O(1) O(n) Avval topiladi
SIZE O(1) O(1) Hisoblagich saqlanadi
KEYS / VALUES O(n) O(n) Barcha yozuvlar ko'riladi
Resize — O(n) Barcha yozuv qayta joylashadi
Ketma-ket qo'shish amortized O(1) — Kamdan kam resize taqsimlanadi

Uzun string kalit uchun hash hisoblash o'zi O(k) vaqt oladi (k — kalit uzunligi). Shuning uchun "lookup O(1)" deyilganda ko'pincha kalit hajmi cheklangan deb taxmin qilinadi.

n ta yozuv uchun umumiy xotira O(n). Bucket arrayi load factor bilan nazoratda bo'lsa, xotira n ga mutanosib o'sadi. Separate chainingda node'lar uchun qo'shimcha xotira, open addressingda esa bo'sh slotlar mavjud.

Algoritmik masalalarda hash table fikrlash usullari

Hash table ishlatishni ko'rishga yordam beradigan ikkita asosiy savol:

  1. "Bu ma'lumotni avval ko'rganimni tezda bilishim kerakmi?" → hash set.
  2. "Bir ma'lumotdan boshqa ma'lumotga tez o'tishim kerakmi?" → hash map.

Ko'rildi (seen) pattern

Elementni birinchi uchrashida setga qo'shish, keyingi uchrashda mavjudligini tekshirish. Graph BFS/DFS'dagi visited, takroriy elementni aniqlash, siklni aniqlash shu shaklda yoziladi.

seen = bo'sh set

FOR har bir element ro'yxat ichida
    IF seen CONTAINS element
        // takrorlandi
    ELSE
        seen ADD element

Komplement (complement) pattern

"Ikkita elementning yig'indisi maqsadga teng bo'lsa topish" masalasida joriy x uchun maqsad - x oldin ko'rilganmi, setda tekshiriladi. Bundan kengroq shakl: x uchun undan foydalana oladigan boshqa element oldin uchragan-uchramaganini mapdan qidirish.

seen = bo'sh set

FOR har bir x ro'yxat ichida
    complement = target - x
    IF seen CONTAINS complement
        RETURN (complement, x)
    seen ADD x

Chastota (frequency) pattern

Elementlar necha marta uchraganini mapda hisoblash. Keyinchalik yana o'shani bir marta ko'rib chiqib, chastotalar bilan ish qilish.

freq = bo'sh map

FOR har bir element ichida
    IF freq CONTAINS element
        freq[element] = freq[element] + 1
    ELSE
        freq[element] = 1

Guruhlash (grouping) pattern

Bir xil xususiyatli elementlarni umumiy "imzo" (signature) kalit ostida bir joyga yig'ish. Imzo nima ekaniga qarab bir nechta usul: saralangan shaklni kalit qilish, chastota vektori, birinchi belgi va hokazo.

groups = bo'sh map

FOR har bir element ichida
    key = SIGNATURE(element)
    IF groups CONTAINS key
        groups[key] ga element ni qo'sh
    ELSE
        groups[key] = [element] bilan yangi ro'yxat yarat

Indekslash (index mapping) pattern

Element va uning indeksi yoki boshqa ma'lumotini bog'lash. "Bu qiymat qayerda uchragandi?" savoliga bitta kartada qiymat → indeks saqlab javob berish.

index_map = bo'sh map

FOR i = 0 DAN n-1 GACHA
    index_map[arr[i]] = i

Hash map va BST asosidagi map taqqoslashi

Hash map va balanced search tree (BST) asosidagi map (masalan, red-black tree) bir xil kalit-qiymat interfeysini beradi, lekin turli xarakteristikaga ega.

Xususiyat Hash map BST map
Lookup kutiladigan O(1) O(log n)
Qo'shish amortized kutiladigan O(1) O(log n)
O'chirish kutiladigan O(1) O(log n)
Eng yomon lookup O(n) O(log n)
Tartibli traversal emas (maxsus mexanikomsiz) ha (in-order)
Diapazon so'rovi emas ha
Minimum/maksimum O(n) O(log n)
Yomon taqsimot xavfi bor yo'q

Hash map "odatda tez, tartib kerak emas" talabida qulay. BST map "tartib, diapazon yoki eng yomon holat kafolati" talab qilinganida ustunroq.

Kalit turi haqida

Hash table faqat hash qilinishi va tengligi aniq belgilangan qiymatlarni kalit sifatida ishlatishi kerak.

Qulay kalit turlari: - butun sonlar; - stringlar; - o'zgarmas (immutable) qiymat obyektlari.

Muammoli kalit turlari: - mutable obyektlar — ichki holati o'zgarsa hash va tenglik o'zgarishi mumkin; - o'zini o'zi ko'rsatuvchi yoki tsiklik tuzilmalar — tenglik va hash cheksiz rekursiyaga tushishi mumkin; - float — sonlarni yozishda ishlatiladigan tuzilma sabab bir-biriga "teng" bo'lishi kerak bo'lgan float'lar turli hash berishi mumkin.

Tartib savoli

Hash map elementlarni qo'shilish tartibida yoki kalit tartibida saqlaydimi — bu implementatsiyaga bog'liq va universal kafolat emas.

Ko'p standart kutubxonalar random tartibda traversal qilishi, resize bo'lganda tartib o'zgarishi yoki versiyadan versiyaga tartib almashishi mumkin. Agar tartib talab qilinsa:

  • qo'shilish tartibini saqlovchi maxsus linked hash map variantlari mavjud bo'lishi mumkin;
  • kalit tartibida traversal uchun BST map tanlanadi;
  • kichik to'plam uchun saralangan array va binary search ishlashi mumkin.

Xotira va load factor

Hash table'da foydalanilmayotgan joy doim bo'ladi. Juda kichik load factor katta bo'sh maydon, juda katta load factor esa ko'p collision beradi. Ko'p implementatsiyalar 0.5 dan 0.75 gacha load factorda ishlaydi.

Oldindan taxminiy o'lcham ma'lum bo'lsa, boshlang'ich capacity'ni to'g'ri tanlash keraksiz resize'larni kamaytiradi. Juda kichik boshlang'ich capacity bilan boshlash ko'p resize beradi; juda katta boshlash xotirani isrof qiladi.

Keng tarqalgan xatolar

GET natijasidan kalit mavjudligini aniqlash. Qiymat NULL bo'lishi mumkin bo'lgan mapda GET(key) = NULL ikkita ma'no berishi mumkin: kalit yo'q, yoki kalit bor lekin qiymati NULL. Mavjudlikni CONTAINS bilan alohida tekshirish to'g'riroq.

Chastota hisoblagichini oldindan 0 deb taxmin qilish. Kalit mavjud bo'lmasa, uni hozirgi qiymat + 1 sifatida o'qish xatoga olib keladi. Avval mavjudlik tekshiriladi yoki standart qiymat ko'zda tutiladi.

Bir mapni yaratish o'rniga qayta-qayta CONTAINS + GET chaqirish. Ba'zi vaziyatlarda bitta GET ikkala savolga javob beradi — kalit mavjudligini tekshirish va qiymatni olish. Ikkita alohida chaqiruv ma'no jihatdan bir xil bo'lishi mumkin, lekin keraksiz takror.

Guruhlash mapida birinchi elementni qo'shimcha tekshirmasdan yangilash. Kalit yangi bo'lsa, uning qiymati (ro'yxat) avval yaratilishi kerak. "Mavjud bo'lsa ro'yxatga qo'sh, yo'qsa yangi ro'yxat yaratib qo'sh" mantiqi tushirib qoldirilsa, null-reference xatosi chiqadi.

Hash set va ro'yxatni aralashtirish. Set mavjudlikni tez tekshiradi, lekin elementlar tartibini saqlamaydi. Tartib kerak bo'lsa, setdan foydalanish o'rinli emas.

Qachon hash table ishlatish kerak?

  • Aniq kalit bo'yicha tez lookup — kutiladigan O(1) talab qilinsa.
  • Elementlarni ko'rilganini yoki uchraganini kuzatish kerak bo'lsa.
  • Chastota, guruh yoki indeks ma'lumotini bir joyda saqlash kerak bo'lsa.
  • Kalitlar katta yoki siyrak olamdan kelsa va direct addressing xotirani isrof qilsa.
  • Natijaning saralangan tartibi muhim bo'lmasa.

Qachon hash table ishlatmaslik kerak?

  • Tartibli traversal yoki minimum/maksimum kerak bo'lsa — BST asosidagi map yoki heap mos.
  • Diapazon so'rovlari kerak bo'lsa — hash qiymat tabiiy tartibni saqlamaydi.
  • Eng yomon holat kafolati zarur bo'lsa — kutiladigan O(1) ni ta'minlab bo'lmaydi; O(log n) kafolatli tree tanlanadi.
  • Elementlar soni juda kichik bo'lsa — oddiy array va linear search xotira va kodni sodda saqlaydi.
  • Prefix yoki lexicographic qidirish kerak bo'lsa — trie yoki saralangan array mosroq.

Eng muhim xulosa

Hash table algoritmik masalalarda eng ko'p ishlatiladigan ma'lumotlar tuzilmalaridan biri. Uning kuchi — kalit bo'yicha kutiladigan O(1) da lookup, tartibni saqlamasligi esa asosiy cheklovi.

Hash map kalit-qiymat juftlarini, hash set esa faqat kalitlarni saqlaydi. Ko'rildi, komplement, chastota, guruhlash va indekslash — hash table bilan yechadigan asosiy algoritmik shablonlar.

Hash table tanlaganda to'rtta savolni tekshirish muhim:

  1. Kalit uchun hash va tenglik aniq belgilangan va stabil?
  2. Tartib yoki diapazon so'rovi kerak?
  3. Elementlar soni ma'qul xotira sarfiga olib keladimi?
  4. Eng yomon holat O(n) qabul qilinadimi yoki O(log n) kafolat zarurmi?

Keyingi masalalar — takrorlanish, ikki son yig'indisi, anagramma va anagram guruhlari — bu shablonlarni amalda ko'rsatadi.