Hashing

Tasavvur qiling, kutubxonada millionta kitob bor va sizga kerakli kitobni nomi bo‘yicha topish kerak. Kitoblarni boshidan oxirigacha birma-bir tekshirish mumkin, lekin to‘plam kattalashgan sari bu usul sekinlashadi. Agar har bir kitob nomidan uning qaysi javonda turishini tez hisoblaydigan qoida bo‘lsa-chi?

Masalan, qoida kitob nomini oladi va 0 dan 999 gacha javon raqamini chiqaradi. “Algoritmlar” nomi uchun 214, “Ma’lumotlar bazasi” uchun 731 chiqishi mumkin. Kitob qidirilganda ayni qoida yana ishlatiladi va barcha javonlarni ko‘rmasdan to‘g‘ri javonga boriladi.

Hashing — kalitni maxsus funksiya orqali qayta ishlab, undan ma’lumot saqlanadigan yoki qidiriladigan joyni aniqlashda foydalanish yondashuvidir. Shu yondashuv asosida qurilgan hash table kalit va qiymat juftlarini odatda juda tez saqlash, topish va o‘chirish imkonini beradi.

kalit              hash funksiyasi       bucket
"kitob-42"   ───────────────────────────→   3

Hash table’ning kuchi kalitni array indexiga o‘xshash joyga aylantirishidadir. Lekin turli kalitlar bir xil joyga tushishi mumkin. Bu collision, ya’ni to‘qnashuv deyiladi. To‘qnashuv xato yoki kamdan kam uchraydigan istisno emas; u hashing modelining tabiiy qismi. Yaxshi hash table collisionlarni to‘g‘ri boshqarishi, jadval haddan tashqari to‘lganda esa kattalashishi kerak.

Hash table amallari ko‘pincha kutiladigan yoki o‘rtacha holatda O(1) bo‘ladi. Bu “har qanday sharoitda doimiy vaqt” degani emas. Yomon taqsimot, juda ko‘p collision yoki ataylab tanlangan zararli kalitlar eng yomon holatda qidirishni O(n)gacha yomonlashtirishi mumkin.

Shkaflar analogiyasi

Sport markazida raqamlangan shkaflar bor deb tasavvur qiling. Har bir mijozning a’zolik raqami maxsus qoidadan o‘tkazilib, shkaf raqami olinadi:

shkaf = a’zolik_raqami MOD 10

1234 MOD 10 = 4
5684 MOD 10 = 4

Ikkala mijoz ham 4-shkafga tushdi. Shkaflar soni cheklangan, mumkin bo‘lgan a’zolik raqamlari esa juda ko‘p. Shuning uchun bunday to‘qnashuvdan butunlay qochishning iloji yo‘q.

Muammoni hal qilishning ikki umumiy yo‘li bor:

• 4-shkaf ichida bir nechta yozuvni alohida ro‘yxatda saqlash;
• 4 band bo‘lsa, belgilangan tartibda boshqa bo‘sh shkafni qidirish.

Birinchi usul separate chaining, ikkinchisi open addressing g‘oyasiga mos. Har ikkisi collisionni yo‘q qilmaydi; uni boshqaradi.

Analogiyada bir nozik jihat bor: hash table qiymatni faqat bucket raqami bilan aniqlamaydi. Collision bo‘lishi mumkinligi sababli bucket ichida yoki tekshirilgan slotda asl kalit ham saqlanadi. Qidiruv paytida topilgan kalitning so‘ralgan kalitga tengligi tekshiriladi.

Asosiy terminlar

Kalit va qiymat

Kalit (key) — yozuvni aniqlash va keyin topish uchun ishlatiladigan ma’lumot. Qiymat (value) — kalit bilan bog‘langan foydali ma’lumot.

kalit:  "user-1042"
qiymat: foydalanuvchining profil ma’lumoti

Ikki xil kalitning qiymati bir xil bo‘lishi mumkin. Ammo oddiy map modelida bitta kalit odatda bitta joriy qiymatga mos keladi; shu kalit bilan qayta yozish eski qiymatni yangilaydi. Bir kalitga bir nechta qiymat kerak bo‘lsa, qiymatning o‘zi kolleksiya bo‘lishi mumkin.

Hash funksiya

Hash funksiya (hash function) kalitni qabul qilib, odatda belgilangan diapazondagi son — hash qiymat yoki hash code — hosil qiladi:

hash = HASH(key)

Hash funksiya bir xil kalit uchun jadval ishlayotgan davrda mos, barqaror natija berishi kerak. Aks holda qo‘shilgan yozuvni qayta topib bo‘lmaydi.

Hash qiymat va index

Hash qiymat bilan array indexi har doim aynan bir narsa emas. Hash funksiya juda katta yoki hatto manfiy son berishi mumkin. Hash table bu qiymatni bucketlar soniga mos diapazonga keltiradi:

index = NORMALIZE(hash, capacity)

Soddalashtirilgan modelda:

index = hash MOD capacity

Amaliy implementatsiya bit mask, aralashtirish yoki boshqa usul ishlatishi mumkin. Muhimi, natija mavjud bucket indexlaridan biriga tushadi.

Bucket va slot

Bucket — hash table ichidagi mantiqiy joy. Separate chainingda bucket bir nechta yozuv saqlaydigan zanjir yoki boshqa kolleksiyaga olib borishi mumkin. Open addressingda arrayning bitta katagi ko‘pincha slot deb ataladi va unda bitta yozuv turadi.

Capacity va size

• capacity — jadvalda hozir nechta bucket yoki slot mavjudligi;
• size — amalda nechta kalit-qiymat jufti saqlanayotgani.

Bu ikkisini aralashtirmaslik kerak. Capacity 16, size 10 bo‘lsa, jadvalning tuzilmasida 16 ta joy bor, ularda 10 ta yozuv saqlanmoqda.

Load factor

To‘lish koeffitsiyenti (load factor) jadvalning qanchalik bandligini ko‘rsatadi:

load_factor = size / capacity

Masalan, size 6, capacity 8 bo‘lsa:

load_factor = 6 / 8 = 0.75

Load factor oshgan sari collision ehtimoli va collisionni hal qilish xarajati odatda ortadi. Shu sababli ko‘p hash table implementatsiyalari ma’lum chegaraga yetganda jadvalni kattalashtiradi. Aniq chegara va o‘sish usuli implementatsiyaga bog‘liq.

Collision

Ikki turli kalit bir xil bucket yoki boshlang‘ich indexga tushsa, collision yuz beradi:

HASH("Ali")  → 42
HASH("Vali") → 42

Bu "Ali" = "Vali" degani emas. Hash qiymatlar tengligi kalitlar tengligini kafolatlamaydi. Lekin teng deb qaraladigan kalitlar bir xil hash natijasiga ega bo‘lishi kerak; aks holda hash table bir xil kalitni turli joydan qidiradi.

Hashing, hash function va hash table bir xil emas

Bu atamalar ko‘pincha bir-birining o‘rnida ishlatiladi, lekin ularning vazifasi boshqa:

• hashing — ma’lumotni hash orqali qayta ishlashning umumiy yondashuvi;
• hash function — kalitdan hash qiymat hosil qiladigan funksiya;
• hash table — hash funksiyadan joy tanlash uchun foydalanadigan ma’lumotlar tuzilmasi;
• hash set — faqat kalitlarning mavjudligini saqlaydigan hash table ko‘rinishi;
• hash map — kalitlarni qiymatlar bilan bog‘laydigan hash table ko‘rinishi.

Hash set ichki modelda qiymatsiz mapga o‘xshashi mumkin: yozuv uchun kalitning o‘zi yetarli. U “bu element mavjudmi?” savoliga tez javob berish uchun ishlatiladi.

Xotirada qanday tashkil qilinadi?

Klassik hash table asosida ma’lum capacity’ga ega bucketlar arrayi turadi:

Index:      0        1        2        3        4
          +--------+--------+--------+--------+--------+
Bucket:   | bo‘sh  | yozuv  | bo‘sh  | yozuv  | bo‘sh  |
          +--------+--------+--------+--------+--------+

Kalit hash qilinadi, hash qiymatdan index olinadi va yozuv shu index bilan bog‘liq joyda saqlanadi. Array ishlatilgani sababli bucketga index bo‘yicha murojaat odatda O(1). Ammo kerakli yozuvni bucket ichidan yoki probe ketma-ketligidan topish uchun collision boshqaruvi ishlaydi.

Hash table yozuvi odatda faqat qiymatni emas, kalitni ham saqlaydi:

+----------------+----------------------+
| key="user-42"  | value=profil_reference|
+----------------+----------------------+

Kalit saqlanmasa, bir bucketka tushgan turli kalitlarning qaysi biri qidirilganini tekshirib bo‘lmaydi. Ayrim implementatsiyalar hisobni tezlashtirish uchun tayyor hash qiymatning bir qismini ham yozuv bilan saqlashi mumkin.

Xotiraning aniq ko‘rinishi implementatsiyaga bog‘liq

Separate chaining bucket arrayi va alohida node’lardan foydalanishi mumkin. Open addressing esa yozuvlarni bevosita bitta array ichiga joylaydi. Ba’zi zamonaviy hash table’lar kalit, qiymat va metadata’ni bir yoki bir nechta zich arraylarda saqlab, CPU cache bilan samaraliroq ishlashga harakat qiladi.

Shuning uchun “hash table xotirada doim linked listlardan iborat” yoki “har bucketda faqat bitta element bor” degan gap universal emas. DSAda asosiy collision usullarini o‘rganamiz, amaliy kutubxona esa boshqa optimizatsiya qo‘llashi mumkin.

Yaxshi hash funksiyaning xususiyatlari

Hash table uchun hash funksiya quyidagi maqsadlarga xizmat qilishi kerak.

Deterministik yoki jadval ichida izchil bo‘lishi

Bir xil kalit uchun qidirish paytida qo‘shish paytidagi mos natija olinishi kerak. Ayrim runtime’lar xavfsizlik uchun dastur har ishga tushganda yashirin seedni o‘zgartirishi mumkin. Shunda hash turli ishga tushirishlar orasida farq qiladi, ammo bitta table hayoti davomida izchil qoladi.

Kalitning barcha muhim qismlarini hisobga olish

Faqat birinchi belgi yoki sonning oxirgi raqamidan foydalanish ko‘plab o‘xshash kalitlarni bitta bucketga yig‘ishi mumkin. Masalan, barcha telefon raqamlari bir xil prefiks bilan boshlansa, faqat prefiksni hash qilish yomon taqsimot beradi.

Natijalarni bir tekis taqsimlash

Yaxshi hash funksiya odatiy kirishlarda kalitlarni bucketlar bo‘ylab imkon qadar teng tarqatadi:

Yaxshi taqsimot:   [2] [3] [2] [3] [2]
Yomon taqsimot:    [0] [0] [0] [0] [12]

Mukammal tenglik har doim mumkin emas. Maqsad uzun zanjir yoki clusterlar hosil bo‘lish ehtimolini kamaytirish.

Tez hisoblanish

Hash table har qidirish, qo‘shish va o‘chirishda hash hisoblaydi. Hash funksiyaning o‘zi juda qimmat bo‘lsa, bucketga tez kirishning foydasi kamayadi. Kalit uzun string bo‘lsa, uning barcha belgilarini ko‘rishning o‘zi kalit uzunligiga nisbatan O(k) vaqt olishi mumkin.

Shu sababli hash table amali “O(1)” deyilganda ko‘pincha kalit hajmi cheklangan yoki hash hisoblash narxi alohida hisobga olinmaydi. Uzunligi k bo‘lgan string kalit uchun hashni hisoblash kamida O(k) bo‘lishi mumkin.

Collision nima sababdan muqarrar?

Mumkin bo‘lgan kalitlar soni odatda bucketlar sonidan ancha katta. Masalan, ixtiyoriy uzunlikdagi barcha stringlarni atigi 1000 ta bucketga joylashtirish kerak bo‘lsa, bir nechta string albatta bir bucketka tushadi.

Bu pigeonhole principle deb ataladigan oddiy fikrga borib taqaladi: qutilardan ko‘proq buyum bo‘lsa, kamida bitta qutida bir nechta buyum bo‘ladi.

Cheksiz ko‘p mumkin bo‘lgan kalit
                 ↓
            8 ta bucket
     [0][1][2][3][4][5][6][7]

Shu sababli yaxshi hash funksiya “collision hech qachon bo‘lmaydi” degani emas. U collisionlarni kamroq va taqsimlangan qiladi. Hash table esa collision yuz berganda to‘g‘ri kalitni saqlash va topish mexanizmiga ega bo‘lishi shart.

Collisionni hal qilish usullari

Separate chaining

Separate chaining, ya’ni alohida zanjirlashda har bucket shu indexga tushgan yozuvlar kolleksiyasini saqlaydi. Soddalashtirilgan modelda bu linked list bo‘lishi mumkin:

Index
  0  → NULL
  1  → [Ali:90] → [Vali:85] → NULL
  2  → [Sami:88] → NULL
  3  → NULL

Ali va Vali bir bucketga tushgan, lekin ikkalasining asl kaliti saqlangani uchun farqlanadi.

Qidirish

1. kalitning hash qiymati hisoblanadi;
2. bucket indexi olinadi;
3. bucket ichidagi yozuvlar kalit teng bo‘lguncha tekshiriladi.

FUNCTION GET_CHAINING(table, key)
    index = INDEX_FOR(HASH(key), table.capacity)

    FOR har bir entry table.buckets[index] ichida
        IF entry.key = key
            RETURN entry.value

    RETURN TOPILMADI

Kalitlar yaxshi taqsimlangan va load factor nazoratda bo‘lsa, bucket zanjiri qisqa bo‘ladi va kutiladigan vaqt O(1). Barcha kalit bitta bucketga tushsa, zanjir uzunligi n bo‘lib, eng yomon vaqt O(n).

Qo‘shish va yangilash

Avval bucket ichida kalit mavjudligi tekshiriladi. Mavjud bo‘lsa qiymat yangilanadi; mavjud bo‘lmasa yangi yozuv qo‘shiladi:

FUNCTION PUT_CHAINING(table, key, value)
    IF table kattalashtirilishi kerak bo‘lsa
        RESIZE(table)

    index = INDEX_FOR(HASH(key), table.capacity)

    FOR har bir entry table.buckets[index] ichida
        IF entry.key = key
            entry.value = value
            RETURN

    yangi entry ni table.buckets[index] ga qo‘sh
    table.size = table.size + 1

Bucket boshiga tekshirmasdan yozuv qo‘shish O(1) bo‘lishi mumkin, ammo map semantikasida takroriy kalit yaratmaslik uchun mavjud kalitni topish talab qilinadi. Kutiladigan vaqt O(1), eng yomon holat O(n).

O‘chirish

Kerakli bucket topiladi, so‘ng kalit kolleksiyadan o‘chiriladi. Linked list ishlatilsa, oldingi node bog‘lanishi yangilanadi. Vaqt kutiladigan holatda O(1), uzun bitta zanjirda O(n).

Afzallik va cheklov

Separate chaining load factor 1dan katta bo‘lishiga ham ruxsat bera oladi, chunki bucket bir nechta yozuv saqlaydi. O‘chirish nisbatan sodda. Buning evaziga node/reference uchun qo‘shimcha xotira, ko‘p mayda allocation va tarqoq xotira sabab cache samaradorligi pasayishi mumkin.

Bucket ichida linked list ishlatilishi shart emas. Dynamic array yoki collisionlar juda ko‘payganda tree kabi tuzilma ishlatilishi mumkin. Bu implementatsiyaning maqsadiga bog‘liq.

Open addressing

Open addressingda barcha yozuvlar bucket arrayining o‘zida saqlanadi. Boshlang‘ich slot band bo‘lsa, maxsus probe sequence, ya’ni tekshirish ketma-ketligi bo‘yicha boshqa slot qidiriladi.

Index:   0       1       2       3       4       5       6
       +-------+-------+-------+-------+-------+-------+-------+
Slot:  | bo‘sh |  Ali  |  Vali | bo‘sh |  Sami | bo‘sh | bo‘sh |
       +-------+-------+-------+-------+-------+-------+-------+

Agar Ali va Valining boshlang‘ich indexi 1 bo‘lsa, Ali 1ga, Vali esa probe qoidasi bo‘yicha keyingi mos bo‘sh slotga joylashadi.

Qidirishda ham ayni probe ketma-ketligi ishlatilishi shart. Boshqa yo‘l tanlansa, qo‘shilgan yozuv topilmaydi.

Linear probing

Linear probing band slotdan keyingi slotlarni ketma-ket tekshiradi:

index, index + 1, index + 2, ...

Array oxiriga yetganda qidiruv boshidan davom etadi:

probe_index = (start_index + step) MOD capacity

Usul sodda va xotirada yonma-yon slotlarni tekshirishi sabab cache bilan yaxshi ishlashi mumkin. Ammo ketma-ket band slotlar katta cluster hosil qiladi. Cluster kattalashgan sari yangi collisionlar ham shu hududga qo‘shilib, qidiruvni sekinlashtiradi.

Quadratic probing

Quadratic probing qadamni kvadratlar bo‘yicha oshiradi:

index + 1², index + 2², index + 3², ...

Bu linear probingdagi birlamchi clusterlarni kamaytirishi mumkin. Lekin capacity va formula noto‘g‘ri tanlansa, bo‘sh slot mavjud bo‘lsa ham barcha slotlar tekshirilmasligi mumkin. Aniq formula implementatsiyaga bog‘liq.

Double hashing

Double hashing qadam uzunligini ikkinchi hash funksiya orqali belgilaydi:

start = HASH_1(key)
step = HASH_2(key)
probe = start + attempt × step

Turli kalitlar turli qadam bilan yurishi sababli clusterlar kamayadi. Ikkinchi hash va capacity probe barcha kerakli slotlarga yetadigan qilib tanlanishi kerak.

Open addressingda qidirish

FUNCTION GET_OPEN(table, key)
    start = INDEX_FOR(HASH(key), table.capacity)

    FOR attempt = 0 DAN table.capacity - 1 GACHA
        index = PROBE(start, key, attempt, table.capacity)
        slot = table.slots[index]

        IF slot = NEVER_USED
            RETURN TOPILMADI

        IF slot = OCCUPIED AND slot.key = key
            RETURN slot.value

    RETURN TOPILMADI

Hech qachon ishlatilmagan bo‘sh slotga yetilganda qidiruv to‘xtashi mumkin: agar kalit mavjud bo‘lganida, qo‘shish jarayoni shu bo‘sh joyda to‘xtagan bo‘lardi. Lekin oldin ishlatilgan, keyin o‘chirilgan slot uchun bunday xulosa qilib bo‘lmaydi.

O‘chirish va tombstone

Open addressingda yozuvni oddiy bo‘sh slotga aylantirish qidiruv zanjirini buzishi mumkin:

Boshlang‘ich index ikkalasi uchun 2:

[2: Ali] [3: Vali]

Ali oddiy bo‘sh qilinsa:
[2: bo‘sh] [3: Vali]

Valini qidirish 2dagi bo‘sh joyda to‘xtab, uni yo‘q deb xato xulosa qilishi mumkin. Shu sababli o‘chirilgan slot ko‘pincha tombstone, ya’ni “oldin band bo‘lgan, hozir o‘chirilgan” maxsus belgi bilan belgilanadi:

[2: DELETED] [3: Vali]

Qidiruv tombstone’dan o‘tadi, yangi qo‘shish esa undan qayta foydalanishi mumkin. Tombstone’lar ko‘payib ketsa, probe yo‘llari uzayadi; rehash ularni tozalashi mumkin.

Afzallik va cheklov

Open addressing yozuvlarni zich arrayda saqlab, pointer va alohida node xarajatini kamaytirishi hamda CPU cache’dan yaxshi foydalanishi mumkin. Ammo jadval juda to‘lsa unumdorlik keskin pasayadi, o‘chirish murakkabroq va probe qoidalarini to‘g‘ri loyihalash zarur.

Resizing va rehashing

Hash table to‘lib borganda collisionlar ko‘payadi. Unumdorlikni saqlash uchun table kattaroq bucket arrayiga o‘tadi. Bu jarayon odatda quyidagicha:

1. kattaroq capacity’li yangi array ajratiladi;
2. eski table’dagi har bir faol yozuv olinadi;
3. yangi capacity asosida uning yangi indexi hisoblanadi;
4. yozuv yangi table’ga joylashtiriladi;
5. eski bucket arrayi tashlab yuboriladi yoki bo‘shatiladi.

Eski capacity = 4
index = hash MOD 4

Yangi capacity = 8
index = hash MOD 8

Capacity o‘zgargani uchun eski indexlar to‘g‘ri qolmasligi mumkin. Shu sababli faqat eski arrayni kattalashtirib, yozuvlarni o‘z joyida qoldirish yetarli emas; ular rehash qilinadi.

Bir resizing n ta yozuvni ko‘chirsa O(n) vaqt oladi. Shunga qaramay, capacity geometrik ravishda, masalan, taxminan ikki barobar oshirilsa, ketma-ket ko‘p qo‘shishning amortized narxi kutiladigan O(1) bo‘lishi mumkin. Amortized tahlil har bitta qo‘shish arzon degani emas; kamdan kam qimmat resize xarajati ko‘plab arzon qo‘shishlar orasiga taqsimlanadi.

Ko‘p amallar:  arzon, arzon, arzon, QIMMAT RESIZE, arzon, arzon, ...
O‘rtacha taqsimlangan xarajat: har qo‘shishga doimiy miqdor

Resize vaqtida eski va yangi array bir muddat birga mavjud bo‘lishi mumkin, bu vaqtinchalik qo‘shimcha xotira talab qiladi. Real-time yoki juda katta tizimlarda ishni bosqichma-bosqich bajaradigan incremental rehashing variantlari ishlatilishi mumkin.

Asosiy amallar

Quyidagi murakkabliklarda n — yozuvlar soni, k esa kerak bo‘lsa kalit hajmi. “Kutiladigan O(1)” yaxshi hash taqsimoti va nazoratdagi load factorni nazarda tutadi.

Yaratish

Hash table boshlang‘ich capacity bilan bucket yoki slot arrayini yaratadi:

FUNCTION CREATE_TABLE(capacity)
    table.buckets = capacity ta bo‘sh bucket
    table.capacity = capacity
    table.size = 0
    RETURN table

Barcha bucketlarni aniq bo‘sh holatga o‘rnatish talab qilinsa, yaratish O(capacity) vaqt va xotira oladi. Ayrim muhitlarda xotira ajratishning tashqi ko‘rinishi boshqacha bo‘lishi mumkin, lekin table capacity’ga mutanosib joy egallaydi.

Qo‘shish yoki yangilash

FUNCTION PUT(table, key, value)
    hash = HASH(key)
    index = INDEX_FOR(hash, table.capacity)
    collision qoidasi bilan key ni qidir

    IF key mavjud bo‘lsa
        uning value qismini yangila
    ELSE
        yangi key-value yozuvini joylashtir
        table.size = table.size + 1

    IF load factor chegaradan oshsa
        RESIZE(table)

Hash hisobini doimiy deb olganda, kutiladigan vaqt O(1), eng yomon holat O(n). Resize sodir bo‘lgan aniq amal O(n) bo‘lishi mumkin; ketma-ket qo‘shishlar uchun amortized kutiladigan vaqt O(1).

Qidirish

Qidirish kalitdan ayni hash va ayni collision yo‘lini hosil qiladi. Bucket yoki probe yo‘lida asl kalitlar tengligi tekshiriladi. Kutiladigan vaqt O(1), eng yomon holat O(n). Uzun kalitni hash qilish O(k) bo‘lsa, umumiy kutiladigan xarajat O(k) sifatida qaralishi mumkin.

Mavjudlikni tekshirish

Hash setdagi CONTAINS(element) yoki mapdagi CONTAINS_KEY(key) qidirish bilan bir xil mexanizmga ega. Qiymat NULL bo‘lishi mumkin bo‘lgan mapda GET(key) = NULL natijasi “kalit yo‘q” degani bo‘lmasligi mumkin. Kalitning mavjudligini alohida tekshirish semantik jihatdan muhim.

O‘chirish

Avval kalit topiladi, so‘ng chaining kolleksiyasidan uziladi yoki open addressing slotiga tombstone qo‘yiladi. Kutiladigan vaqt O(1), eng yomon holat O(n). O‘chirishdan keyin size kamayadi. Ayrim implementatsiyalar load factor juda tushsa table’ni kichraytiradi, lekin tez-tez kattalashib-kichrayishni oldini olish uchun chegaralar orasida farq qo‘yilishi mumkin.

Traversal

Hash table’dagi barcha yozuvni ko‘rish uchun bucket arrayi va ulardagi yozuvlar tekshiriladi:

FUNCTION TRAVERSE(table)
    FOR har bir bucket table.buckets ichida
        FOR har bir entry bucket ichida
            VISIT entry.key, entry.value

Capacity m, yozuvlar soni n bo‘lsa, umumiy vaqt ko‘pincha O(m + n). Capacity load factor bilan mutanosib saqlansa, bu odatda O(n) deb soddalashtiriladi. Hash table tartibli traversalni kafolatlamaydi, agar muayyan implementatsiya alohida tartib mexanizmini saqlamasa.

Bosqichma-bosqich dry run

Capacity 5 bo‘lgan separate chaining table va soddalashtirilgan hash qoidani olaylik:

index = sonli_kalit MOD 5

12, 7, 22 kalitlarini qo‘shamiz:

12 MOD 5 = 2
 7 MOD 5 = 2
22 MOD 5 = 2

Uchala kalit ham collision qiladi.

Boshlanish:
0 → NULL
1 → NULL
2 → NULL
3 → NULL
4 → NULL

12 qo‘shilgach:
2 → [12: qiymat_A] → NULL

7 qo‘shilgach:
2 → [12: qiymat_A] → [7: qiymat_B] → NULL

22 qo‘shilgach:
2 → [12: qiymat_A] → [7: qiymat_B] → [22: qiymat_C] → NULL

7ni qidirish:

1. 7 MOD 5 = 2, demak 2-bucket tanlanadi.
2. 12 = 7 tekshiriladi — noto‘g‘ri.
3. 7 = 7 tekshiriladi — to‘g‘ri.
4. qiymat_B qaytariladi.

Bu kichik misolda bitta bucketda uchta element turibdi. Real yaxshi hash funksiya odatiy kalitlarni barcha bucketlarga yaxshiroq tarqatishga harakat qiladi.

Vaqt va xotira murakkabligi

Hash table umumiy xotirada bucket arrayi va n ta yozuvni saqlaydi, shuning uchun load factor nazoratda bo‘lsa O(n) xotira deb qaraladi. Separate chainingda node va reference’lar, open addressingda esa bo‘sh slotlar va metadata qo‘shimcha xarajat keltiradi.

O‘rtacha va kutiladigan holat nimani anglatadi?

Hash table uchun O(1) odatda kalitlar yaxshi tarqalishi haqidagi taxminga tayangan expected complexity. Bu real ma’lumotning har qanday to‘plami avtomatik yaxshi tarqaladi degani emas. Natija hash funksiyaning sifati, kalitlar shakli, load factor va collision strategiyasiga bog‘liq.

Eng yomon O(n) holat faqat nazariy qiziqish emas. Tashqi foydalanuvchi kalitlarni nazorat qilsa va hash xatti- harakatini taxmin qila olsa, ataylab collisionlar yaratib, xizmatni sekinlashtirishi mumkin. Ba’zi runtime’lar randomized hashing yoki uzun collision zanjirini boshqa tuzilmaga aylantirish orqali bu xavfni kamaytiradi.

Kalitlar va o‘zgarmaslik

Hash table ichiga qo‘yilgan kalitning tenglikka yoki hashga ta’sir qiladigan qismi keyin o‘zgarsa, yozuv noto‘g‘ri bucketda qolib ketishi mumkin.

1. key holati A → hash 17 → bucket 1 ga qo‘yildi
2. key ichki holati B ga o‘zgardi → hash 42
3. qidiruv bucket 2 dan izlaydi, yozuv esa bucket 1 da qolgan

Shu sababli ko‘p tizimlarda string, son va o‘zgarmas qiymat obyektlari kalit sifatida qulay. Mutable obyekt kalit bo‘lishi mumkin bo‘lgan muhitda ham, uning hash va tenglikka qatnashadigan maydonlarini table ichida turgan paytda o‘zgartirmaslik kerak.

Bu “hash table qiymatlari o‘zgarmas bo‘lishi kerak” degani emas. Qiymat yangilanishi mumkin; muammo yozuv joyini belgilaydigan kalitning hash xususiyati o‘zgarishidadir.

Tenglik va hash shartnomasi

Hash table ikkita alohida savol beradi:

1. Kalit qaysi bucketdan qidiriladi? — hash orqali.
2. Bucketdagi yozuv aynan shu kalitmi? — tenglik orqali.

Muhim qoida:

A va B teng bo‘lsa → HASH(A) = HASH(B) bo‘lishi shart
HASH(A) = HASH(B) bo‘lsa → A va B teng bo‘lishi shart emas

Birinchi yo‘nalish buzilsa, teng kalitlar turli bucketlarga tushib, table ularni boshqa yozuv deb ko‘rishi mumkin. Ikkinchi yo‘nalish collision sababli tabiiy ravishda to‘g‘ri emas; hash teng bo‘lsa ham asl kalit tekshiriladi.

Hash table tartibni saqlaydimi?

Klassik hash table’ning asosiy maqsadi kalit bo‘yicha tez kirish; elementlarning qo‘shilgan yoki saralangan tartibini saqlash emas. Resize bo‘lganda bucketlar o‘zgarishi mumkin, shuning uchun traversal tartibiga tayanish xavfli.

Ba’zi tillardagi map implementatsiyalari qo‘shilish tartibini saqlashi yoki tasodifan barqaror ko‘rinishi mumkin. Bu hash table’ning universal xususiyati emas. Tartib talab qilinsa:

• qo‘shilish tartibi uchun qo‘shimcha linked list yoki alohida ordered map;
• kalitlar bo‘yicha saralangan tartib uchun balanced search tree;
• kichik va statik to‘plam uchun saralangan array

mos bo‘lishi mumkin.

Tartibni saqlaydigan hash map tez lookup uchun hash table va tartib uchun boshqa mexanizmni birlashtiradi; bu qo‘shimcha xotira va yangilash xarajati evaziga keladi.

Hash table va direct addressing

Agar kalitlar kichik, zich va oldindan ma’lum butun son diapazonida bo‘lsa, hash table shart emas. Masalan, kalitlar faqat 0..999 bo‘lsa, to‘g‘ridan-to‘g‘ri array indexidan foydalanish mumkin:

array[key] = value

Bu direct addressing deyiladi. Collision yo‘q va lookup O(1), ammo mumkin bo‘lgan kalit diapazoni juda katta va faqat oz qismi ishlatilsa, ulkan array xotirani isrof qiladi. Hashing katta kalit olamini kichikroq table’ga siqadi; xotirani tejash evaziga collision boshqaruvi paydo bo‘ladi.

Hashing va kriptografik hashing

DSAdagi hash table uchun ishlatiladigan hash funksiya bilan xavfsizlikdagi kriptografik hash bir xil maqsadga ega emas.

Parol hashing alohida masala

Parollar oddiy tez hash bilan saqlanmasligi kerak. Parol saqlash uchun salt va maxsus sekin, resurs talab qiluvchi password hashing algoritmlari ishlatiladi. Maqsad table bucketini topish emas, o‘g‘irlangan ma’lumotdan parolni taxmin qilishni qimmatlashtirish.

Hashing shifrlash emas

Shifrlashda maxfiy kalit bilan ma’lumotni qayta ochish maqsadi bor. Hashing odatda bir tomonlama qisqa natija hosil qiladi; undan asl ma’lumotni umumiy tartibda qayta tiklash ko‘zda tutilmaydi. Hash table esa hash bilan qiymat joyini topadi va asl kalit hamda qiymatni table ichida saqlaydi.

Real qo‘llanishlar

Foydalanuvchini ID bo‘yicha topish

Server xotirasida aktiv foydalanuvchi sessiyalarini session_id → session_data ko‘rinishida saqlash mumkin. So‘rovdagi session ID hash qilinadi va tegishli yozuv tez topiladi. Sessiyalar tartibi kerak emas, asosiy amal aniq ID bo‘yicha lookup bo‘lgani uchun hash map mos.

Bu faqat xotira ichidagi model. Taqsimlangan tizim, saqlanish muddati va serverlararo ulashish kerak bo‘lsa, alohida cache yoki ma’lumotlar bazasi talab qilinadi.

Takroriy elementlarni aniqlash

Katta ro‘yxatda bir qiymat avval uchraganini bilish uchun hash set ishlatiladi:

FUNCTION HAS_DUPLICATE(values)
    seen = bo‘sh hash set

    FOR har bir value values ichida
        IF seen ichida value mavjud bo‘lsa
            RETURN TRUE

        seen ga value qo‘sh

    RETURN FALSE

n ta element uchun kutiladigan vaqt O(n), qo‘shimcha xotira O(n). Ikki ichma-ich sikl bilan har juftlikni tekshirish O(n²) vaqt olishi mumkin. Hash set vaqtni tejash evaziga qo‘shimcha xotira ishlatadi.

Chastotani hisoblash

Matndagi har so‘z necha marta uchraganini mapda saqlash mumkin:

FUNCTION COUNT_FREQUENCIES(words)
    counts = bo‘sh hash map

    FOR har bir word words ichida
        IF counts ichida word mavjud bo‘lsa
            counts[word] = counts[word] + 1
        ELSE
            counts[word] = 1

    RETURN counts

Kalit — so‘z, qiymat — uchrashlar soni. Saralangan natija kerak bo‘lsa, keyinchalik alohida saralash yoki ordered tuzilma kerak; hash mapning o‘zi alifbo tartibini bermaydi.

Ma’lumotlar bazasidagi hash index

Hash index aniq tenglik so‘rovlari, masalan, id = 1042 uchun bucketni tez topishi mumkin. Lekin id BETWEEN 1000 AND 2000 kabi diapazon so‘rovida hash qiymatlar kalitlarning tabiiy tartibini saqlamagani sababli B-tree turidagi indeks ko‘pincha mosroq. Amaliy ma’lumotlar bazasidagi tanlov engine va workloadga bog‘liq.

Cache

Cache kalitdan oldin hisoblangan natijani tez topish uchun hash map ishlatishi mumkin. Masalan, URL’dan tayyor response yoki funksiya argumentlaridan hisob natijasi olinadi. Lekin sig‘im cheklangan bo‘lsa, qaysi elementni chiqarishni belgilash uchun LRU kabi qo‘shimcha siyosat va ma’lumotlar tuzilmasi kerak.

Compiler va interpreter symbol table’i

Dasturdagi o‘zgaruvchi yoki funksiya nomini uning turi, scope’i yoki xotira ma’lumoti bilan bog‘lash uchun symbol table ishlatiladi. Hash map nom bo‘yicha tez lookup beradi. Scope’lar uchun bir nechta table, stack yoki tree qo‘shilishi mumkin.

Keng tarqalgan algoritmik yondashuvlar

“Ko‘rildi” to‘plami

Array, string, tree yoki graph bo‘ylab yurishda oldin ko‘rilgan elementlarni hash setda saqlash siklni aniqlash va takroriy ishlovni oldini olishga yordam beradi. Graph DFS/BFS’da visited set bir node’ni qayta-qayta navbatga qo‘shishni to‘xtatadi.

Complement qidirish

Ikki qiymat yig‘indisi target bo‘lishi kerak bo‘lgan masalada joriy x uchun target - x oldin ko‘rilganmi, hash set orqali tekshiriladi. Bu barcha juftlikni O(n²) tekshirish o‘rniga kutiladigan O(n) vaqt va O(n) xotira beradi.

Grouping

Bir xil xususiyatga ega elementlar umumiy kalit ostida guruhlanadi. Masalan, anagrammalar uchun har bir so‘zdan kanonik vakil hosil qilinib, signature → so‘zlar ro‘yxati mapiga qo‘shiladi. Hashning o‘zi anagrammani isbotlamaydi; to‘g‘ri kanonik kalit yoki collisiondan keyingi tenglik tekshiruvi zarur.

Memoization

Rekursiv yoki qimmat funksiyaning kirish → natija juftlari hash mapda saqlanadi. Ayni kirish yana uchrasa, hisoblash o‘rniga tayyor natija olinadi. Bu vaqtni tejaydi, ammo memo table uchun xotira ishlatadi va kalit funksiya holatini to‘liq ifodalashi kerak.

Counting orqali saralashga yordam

Element chastotalari hash mapda hisoblanib, keyin kerakli tartibda natija qurilishi mumkin. Ammo kalitlar bo‘yicha saralash talab qilinsa, hash mapdan olingan kalitlarni alohida saralash odatda O(u log u) vaqt oladi; bu yerda u — noyob kalitlar soni.

Afzalliklari

• Kalit bo‘yicha qo‘shish, qidirish va o‘chirish kutiladigan holatda O(1).
• Kalitlar kichik butun index bo‘lishi shart emas; string yoki boshqa hash qilinadigan qiymat bo‘lishi mumkin.
• Hash set takroriy element va mavjudlikni tekshirishni sodda qiladi.
• Chastota hisoblash, grouping, cache va memoization uchun tabiiy model beradi.
• Direct addressingga qaraganda katta, siyrak kalit olamida xotirani samaraliroq ishlatishi mumkin.

Bu tezlik tartibdan voz kechish, bo‘sh capacity saqlash, collision boshqaruvi va vaqti-vaqti bilan resize qilish evaziga keladi.

Cheklovlari

• Eng yomon holatda asosiy amallar O(n)gacha yomonlashishi mumkin.
• Kalitlar bo‘yicha tabiiy yoki saralangan tartibni universal tarzda saqlamaydi.
• Diapazon so‘rovlari uchun mos emas.
• Bucket/slot arrayida foydalanilmayotgan joy bo‘lishi mumkin.
• Separate chaining qo‘shimcha node va reference xotirasini talab qiladi.
• Open addressingda table to‘lishi va tombstone’lar probe’ni uzaytiradi.
• Resize bir amal uchun O(n) vaqt va vaqtinchalik qo‘shimcha xotira talab qilishi mumkin.
• Yaxshi hash, tenglik shartnomasi va collision strategiyasini to‘g‘ri qurish murakkab.
• Mutable kalit hash o‘zgarsa, yozuv topilmay qolishi mumkin.

Keng tarqalgan xatolar va nozik holatlar

Hash table amallarini har doim O(1) deyish

To‘g‘ri ifoda: yaxshi taqsimot va nazoratdagi load factor ostida kutiladigan yoki o‘rtacha vaqt O(1); eng yomon holat O(n). Uzun kalitni hash qilish xarajati ham alohida hisoblanishi kerak.

Collisionni tenglik deb qabul qilish

Bir xil hash asl kalitlar tengligini bildirmaydi. Bucket yoki slotdagi entry.key so‘ralgan kalit bilan tenglik qoidasi bo‘yicha tekshirilishi shart.

Teng kalitlarga turli hash berish

Tenglik ikki obyektni bir kalit deb hisoblasa, ular bir xil hash berishi kerak. Hash va equality bir xil maydonlar mantiqiga asoslanmasa, qidirish va takroriy kalitni aniqlash buziladi.

Mutable kalitdan foydalanish

Kalit table ichida turganda hashga qatnashuvchi maydon o‘zgarsa, u eski bucketda qoladi. Bunday kalitni o‘zgartirishdan oldin table’dan olib, o‘zgartirgach qayta qo‘shish yoki o‘zgarmas kalit ishlatish kerak.

Open addressingda oddiy o‘chirish

Slotni NEVER_USED holatiga qaytarish undan keyingi collision yozuvlarini topilmaydigan qiladi. Tombstone yoki strategiyaga mos qayta joylash ishlatilishi kerak.

Resize’da eski indexlarni saqlash

Index capacity’ga bog‘liq. Yangi arrayga yozuvlarni ayni indexda nusxalash yetarli emas; yangi capacity bilan qayta joylash zarur.

Load factorni e’tiborsiz qoldirish

Table deyarli to‘lsa, open addressingda bo‘sh slot topish uzoqlashadi. Separate chainingda zanjirlar o‘sadi. Capacity’ni oldindan to‘g‘ri baholash yoki avtomatik resize unumdorlik uchun muhim.

Traversal tartibiga tayanish

Testda bir xil tartib chiqishi API kafolati degani emas. Resize, runtime versiyasi yoki hash seed o‘zgarsa tartib almashishi mumkin. Tartib biznes talabining bir qismi bo‘lsa, uni kafolatlaydigan tuzilma tanlanadi.

NULL qiymatni “kalit yo‘q” bilan aralashtirish

Map NULL qiymat saqlashga ruxsat bersa, GET(key)dan NULL olish ikki ma’noga ega bo‘lishi mumkin. Mavjudlikni CONTAINS_KEY yoki topildi/topilmadi holati bilan ajratish kerak.

Parol uchun oddiy hash ishlatish

Tez non-cryptographic hash parol saqlash uchun xavfli. Parol hashing alohida xavfsizlik talablari, salt va maxsus algoritmlarni talab qiladi.

Ishonchsiz kalitlarda hujum xavfini unutish

Foydalanuvchi ko‘p collision beradigan kalitlarni yuborsa, serverdagi hash table amallari O(n)ga tushishi mumkin. Randomized seed, collisionga chidamli implementatsiya, input limiti va boshqa himoyalar real xizmatda e’tiborga olinadi.

Qachon hashing ishlatish kerak?

Hash table yoki hash set quyidagi talablar ustun bo‘lganda mos:

• aniq kalit bo‘yicha tez qo‘shish, topish yoki o‘chirish kerak;
• element oldin ko‘rilganini tekshirish kerak;
• takroriy qiymatlarni olib tashlash kerak;
• chastota, grouping yoki indekslash bajariladi;
• kalitlar katta yoki siyrak olamdan keladi;
• natijaning saralangan tartibi muhim emas;
• qo‘shimcha xotira evaziga qidirish vaqtini kamaytirish ma’qul.

Tanlovdan oldin kalit qanday hash qilinishi, tenglik nimani anglatishi, taxminiy yozuvlar soni va tashqi kalitlar hujumkor bo‘lishi mumkinligini baholash kerak.

Qachon hashing ishlatmaslik kerak?

Quyidagi vaziyatlarda boshqa tuzilma yaxshiroq bo‘lishi mumkin:

• Saralangan traversal yoki minimum/maksimum kerak bo‘lsa, balanced search tree yoki heap maqsadga qarab mosroq.
• Diapazon so‘rovlari kerak bo‘lsa, tartibli tree yoki saralangan array foydali. Hash qiymat kalit tartibini saqlamaydi.
• Kalitlar kichik va zich butun diapazonda bo‘lsa, direct addressing arrayi soddaroq va collisionlarsiz.
• Elementlar soni juda kichik bo‘lsa, oddiy array/list kamroq xotira va sodda kod bilan amalda tezroq bo‘lishi mumkin.
• Xotira keskin cheklangan bo‘lsa, bo‘sh capacity, metadata va chaining node’lari qimmat tushadi.
• Eng yomon vaqt qat’iy kafolatlanishi kerak bo‘lsa, oddiy hash table kutiladigan O(1)ga tayangani uchun mos bo‘lmasligi mumkin; O(log n) kafolatli balanced tree tanlanishi mumkin.
• Prefix bo‘yicha qidirish kerak bo‘lsa, trie yoki maxsus indeks ko‘proq mos keladi.
• Diskda juda katta ma’lumot bilan ishlansa, xotira hash table’i o‘rniga B-tree, LSM-tree yoki tashqi xotiraga mos boshqa indeks talab qilinishi mumkin.

Hash table tez tenglik lookupi uchun kuchli, lekin barcha qidiruv muammolariga universal yechim emas.

Eng muhim xulosa

Hashing kalitni hash funksiya orqali qayta ishlab, hash table ichidagi boshlang‘ich joyni topadi. Table asosan bucketlar arrayi, yozuvlar va collisionni boshqarish mexanizmidan iborat. Hash qiymat kalitning o‘zi emas va bir xil hash turli kalitlardan chiqishi mumkin; shu sababli asl kalit tengligi har doim tekshiriladi.

Separate chaining bir bucketdagi yozuvlarni alohida kolleksiyada saqlaydi. Open addressing esa barcha yozuvni arrayning o‘ziga joylab, collisionda boshqa slotlarni probe qiladi. Birinchisi o‘chirish va yuqoriroq load factorni osonroq boshqaradi; ikkinchisi zich xotira va cache samaradorligini berishi mumkin. Har ikkisi load factor va yaxshi hash taqsimotiga bog‘liq.

Hash table’ning qo‘shish, qidirish va o‘chirish amallari yaxshi sharoitda kutiladigan O(1), eng yomon holatda O(n). Resize alohida O(n) amal bo‘lsa-da, geometrik o‘sishda ketma-ket qo‘shishlar amortized kutiladigan O(1) bo‘lishi mumkin.

Hash table tanlashdan oldin to‘rtta savol bering:

1. Kalitlar uchun tenglik nimani anglatadi?
2. Hash funksiya kalitlarni yaxshi taqsimlaydimi?
3. Tartib yoki diapazon so‘rovi kerakmi?
4. Kutiladigan tezlik yetarlimi yoki eng yomon holat kafolati zarurmi?

Hashingni tushunish hash set, map, cache, memoization va ma’lumotlar bazasi indekslarining ichki mantiqini ochadi. Keyingi tabiiy mavzu sifatida tree asosidagi maplarni o‘rganish foydali: ular hash table’dagi kutiladigan O(1) lookup o‘rniga O(log n) tartibli amallar va diapazon so‘rovlarini beradi.