DSA xesh jadvallar

Xesh jadval

Xesh jadval (Hash Table) — tez ishlashga mo‘ljallangan ma’lumotlar tuzilmasi.

Xesh jadvallar ba’zan massivlar yoki bog‘langan ro‘yxatlar o‘rniga afzal ko‘rilishining sababi shundaki, katta hajmdagi ma’lumotlarda ham ma’lumotlarni qidirish, qo‘shish va o‘chirish juda tez bajariladi.

Bog‘langan ro‘yxatda "Bob" ismli odamni topish vaqt oladi, chunki "Bob" joylashgan tugun topilguncha har bir tugunni tekshirib, bir tugundan keyingisiga o‘tishimiz kerak bo‘ladi.

Massivda esa, agar indeksni bilsak, "Bob"ni topish tez bo‘lishi mumkin, lekin faqat "Bob" ismini bilganimizda har bir elementni solishtirishimiz kerak (bog‘langan ro‘yxatlardagi kabi) va bu vaqt oladi.

Xesh jadvalda esa "Bob"ni topish juda tez amalga oshadi, chunki xesh funksiya deb ataladigan narsa yordamida to‘g‘ridan-to‘g‘ri "Bob" saqlangan joyga borish usuli mavjud.

Xesh jadvalni noldan yaratish

Xesh jadval nima ekanini tushunish uchun unda noyob ismlarni saqlash maqsadida uni noldan yaratib ko‘raylik.

Xesh to‘plamni (Hash Set) 5 qadamda yaratamiz:

1. Massivdan boshlash.
2. Ismlarni xesh funksiya yordamida saqlash.
3. Elementni xesh funksiya yordamida qidirish.
4. To‘qnashuvlarni hal qilish.
5. Oddiy xesh to‘plam kodi misoli va simulyatsiyasi.

1-qadam: Massivdan boshlash

Massivdan foydalanib, ismlarni quyidagicha saqlashimiz mumkin:

my_array = ['Pete', 'Jones', 'Lisa', 'Bob', 'Siri']

Bu massivda "Bob"ni topish uchun "Bob"ni topgunimizcha har bir ismni element-element solishtirishimiz kerak.

Agar massiv alifbo tartibida saralangan bo‘lsa, ismni tez topish uchun Binary Search’dan foydalanishimiz mumkin edi, ammo massivga ism qo‘shish yoki undan ismni o‘chirish xotiradagi elementlarni siljitishdek katta amalni talab qiladi.

Ismlar ro‘yxati bilan ishlashni haqiqatan tez qilish uchun buning o‘rniga xesh jadvaldan yoki xesh jadvalning soddalashtirilgan ko‘rinishi bo‘lgan xesh to‘plamdan (Hash Set) foydalanaylik.

Soddalik uchun ro‘yxatda ko‘pi bilan 10 ta ism bor deb faraz qilaylik, demak massiv 10 ta elementdan iborat qat’iy o‘lchamga ega bo‘lishi kerak. Xesh jadvallar haqida gap ketganda bu elementlarning har biri bucket (savat) deb ataladi.

my_hash_set = [None,None,None,None,None,None,None,None,None,None]

2-qadam: Ismlarni xesh funksiya yordamida saqlash

Endi biz yaratayotgan xesh to‘plam bilan ishlashning o‘ziga xos usuli keladi.

Biz ismni to‘g‘ridan-to‘g‘ri massivdagi to‘g‘ri joyiga saqlamoqchimiz va aynan shu yerda xesh funksiya yordamga keladi.

Xesh funksiyani ko‘p usullar bilan yaratish mumkin, bu xesh jadvalni yaratuvchiga bog‘liq. Keng tarqalgan usullardan biri — qiymatni xesh to‘plamning indeks raqamlaridan biriga, bu holatda 0 dan 9 gacha bo‘lgan songa teng keladigan raqamga aylantirish yo‘lini topish. Misolimizda har bir belgining Unicode raqamidan foydalanamiz, ularni qo‘shib chiqamiz va 0–9 indeks raqamlarini olish uchun 10 bo‘yicha modulo amalini bajaramiz.

def hash_function(value):
    sum_of_chars = 0
    for char in value:
        sum_of_chars += ord(char)

    return sum_of_chars % 10

print("'Bob' has hash code:",hash_function('Bob'))

"B" belgisining Unicode kod nuqtasi 66, "o" belgisiniki 111, "b" belgisiniki esa 98. Ularni qo‘shsak, 275 hosil bo‘ladi. 275 ning 10 bo‘yicha modulosi 5 ga teng, demak "Bob" massivning 5-indeksidagi element sifatida saqlanishi kerak.

Xesh funksiya qaytargan son xesh kod deb ataladi.

"Bob"ni xesh kod ko‘rsatgan joyga (5-indeks) saqlaganimizdan so‘ng massivimiz quyidagicha ko‘rinadi:

my_hash_set = [None,None,None,None,None,'Bob',None,None,None,None]

Xesh funksiyadan boshqa ismlar — "Pete", "Jones", "Lisa" va "Siri"ni ham qayerga saqlash kerakligini aniqlash uchun foydalanishimiz mumkin.

Bu ismlarni xesh funksiya yordamida to‘g‘ri joylarga saqlaganimizdan so‘ng massivimiz quyidagicha ko‘rinadi:

my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]

3-qadam: Ismni xesh funksiya yordamida qidirish

Endi biz juda oddiy xesh to‘plam yaratdik, chunki "Pete" massivda bor-yo‘qligini bilish uchun massivni element-element tekshirishimiz endi shart emas — to‘g‘ridan-to‘g‘ri kerakli elementga borish uchun xesh funksiyadan foydalanishimiz kifoya!

"Pete" massivda saqlanganini aniqlash uchun "Pete" ismini xesh funksiyamizga beramiz, 8 xesh kodini qaytarib olamiz, to‘g‘ridan-to‘g‘ri 8-indeksdagi elementga boramiz — u o‘sha yerda. Biz "Pete"ni boshqa hech qanday elementni tekshirmasdan topdik.

my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]

def hash_function(value):
    sum_of_chars = 0
    for char in value:
        sum_of_chars += ord(char)

    return sum_of_chars % 10
    
def contains(name):
    index = hash_function(name)
    return my_hash_set[index] == name

print("'Pete' is in the Hash Set:",contains('Pete'))

Xesh to‘plamdan ismni o‘chirishda ham xesh funksiyadan foydalanib, to‘g‘ridan-to‘g‘ri ism joylashgan joyga borishimiz va o‘sha element qiymatini Nonega o‘rnatishimiz mumkin.

4-qadam: To‘qnashuvlarni hal qilish

Xesh to‘plamimizga "Stuart"ni ham qo‘shaylik.

"Stuart"ni xesh funksiyamizga beramiz va 3 xesh kodini olamiz, ya’ni "Stuart" 3-indeksda saqlanishi kerak.

"Stuart"ni saqlashga urinish to‘qnashuv (collision) deb ataladigan holatni yuzaga keltiradi, chunki 3-indeksda allaqachon "Lisa" saqlangan.

To‘qnashuvni bartaraf etish uchun bitta bucketda ko‘proq element uchun joy ajratishimiz mumkin, to‘qnashuv muammosini bu tarzda hal qilish zanjirlash (chaining) deb ataladi. Har bir bucketni bog‘langan ro‘yxat yoki massiv sifatida amalga oshirib, bitta bucketda ko‘proq element uchun joy ajratishimiz mumkin.

Har bir bucketni massiv sifatida amalga oshirib, har bir bucketda bittadan ortiq ism uchun joy ajratganimizdan so‘ng "Stuart"ni ham 3-indeksda saqlash mumkin va endi xesh to‘plamimiz quyidagicha ko‘rinadi:

my_hash_set = [
    [None],
    ['Jones'],
    [None],
    ['Lisa', 'Stuart'],
    [None],
    ['Bob'],
    [None],
    ['Siri'],
    ['Pete'],
    [None]
]

Endi xesh to‘plamimizda "Stuart"ni qidirishda xesh funksiya yordamida to‘g‘ridan-to‘g‘ri 3-bucketga tushamiz, biroq "Stuart"ni 3-bucketning ikkinchi elementi sifatida topishdan oldin o‘sha bucketdagi "Lisa"ni tekshirishimiz kerak.

5-qadam: Xesh to‘plam kodi misoli va simulyatsiyasi

Juda oddiy xesh to‘plam kodimizni yakunlash uchun endi ikki o‘lchovli massiv bo‘lgan xesh to‘plamga ism qo‘shish va undan ism qidirish funksiyalarini yarataylik.

Xesh to‘plam qanday ishlashini yaxshiroq tushunish uchun quyidagi kod misolini ishga tushiring va uni turli qiymatlar bilan sinab ko‘ring.

my_hash_set = [
    [None],
    ['Jones'],
    [None],
    ['Lisa'],
    [None],
    ['Bob'],
    [None],
    ['Siri'],
    ['Pete'],
    [None]
]

def hash_function(value):
    return sum(ord(char) for char in value) % 10
    
def add(value):
    index = hash_function(value)
    bucket = my_hash_set[index]
    if value not in bucket:
        bucket.append(value)
        
def contains(value):
    index = hash_function(value)
    bucket = my_hash_set[index]
    return value in bucket

add('Stuart')

print(my_hash_set)
print('Contains Stuart:',contains('Stuart'))

Keyingi ikki sahifada xesh to‘plamlar va xesh jadvallarning yanada yaxshiroq va batafsilroq amalga oshirilishi ko‘rsatilgan.

Xesh to‘plam amalda qanday ishlashi haqida yaxshiroq tasavvurga ega bo‘lish uchun quyidagi xesh to‘plam simulyatsiyasini sinab ko‘ring.

Xesh jadvallardan foydalanish

Xesh jadvallar quyidagilar uchun juda mos:

• Biror narsa to‘plamda bor-yo‘qligini tekshirish (kutubxonadan kitob topish kabi).
• Noyob elementlarni saqlash va ularni tez topish (telefon raqamlarini saqlash kabi).
• Qiymatlarni kalitlarga bog‘lash (ismlarni telefon raqamlariga bog‘lash kabi).

Xesh jadvallar bu vazifalar uchun juda mos kelishining eng muhim sababi — ular massivlar va bog‘langan ro‘yxatlarga nisbatan, ayniqsa katta to‘plamlarda, juda tez ishlaydi. Massivlar va bog‘langan ro‘yxatlarda qidirish va o‘chirishning vaqt murakkabligi \(O(n)\), xesh jadvallarda esa o‘rtacha atigi \(O(1)\)! Vaqt murakkabligi haqida bu yerda ko‘proq o‘qing.

Xesh to‘plam (Hash Set) va xesh map (Hash Map)

Xesh jadval xesh to‘plam (Hash Set) yoki xesh map (Hash Map) bo‘lishi mumkin. Keyingi ikki sahifada bu ma’lumotlar tuzilmalari batafsilroq tasvirlangan.

Xesh to‘plamlar va xesh map’lar o‘rtasidagi farqlar va o‘xshashliklar:

Xesh jadvallar haqida qisqacha

Xesh jadval elementlari bucketlar (savatlar) deb ataladigan saqlash konteynerlarida saqlanadi.

Har bir xesh jadval elementining kalit deb ataladigan noyob qismi bor.

Xesh funksiya xesh kod hosil qilish uchun elementning kalitini oladi.

Xesh kod element qaysi bucketga tegishli ekanini ko‘rsatadi, shuning uchun endi to‘g‘ridan-to‘g‘ri o‘sha xesh jadval elementiga borishimiz mumkin: uni o‘zgartirish, o‘chirish yoki shunchaki mavjudligini tekshirish uchun. Muayyan xesh funksiyalar keyingi ikki sahifada batafsil tushuntirilgan.

To‘qnashuv ikki xesh jadval elementi bir xil xesh kodga ega bo‘lganda yuz beradi, chunki bu ularning bitta bucketga tegishli ekanini bildiradi. To‘qnashuvni ikki usulda hal qilish mumkin.

Zanjirlash (chaining) — ushbu darslikda to‘qnashuvlarni hal qilish usuli bo‘lib, bunda bitta bucketda bittadan ortiq elementga joy berish uchun massivlar yoki bog‘langan ro‘yxatlardan foydalaniladi.

Ochiq manzillash (open addressing) — to‘qnashuvlarni hal qilishning yana bir usuli. Ochiq manzillashda, agar elementni saqlamoqchi bo‘lsak-u, lekin o‘sha bucketda allaqachon element bo‘lsa, element keyingi bo‘sh bucketga saqlanadi. Buni turli usullar bilan amalga oshirish mumkin, lekin bu yerda ochiq manzillashni boshqa tushuntirmaymiz.

Xulosa

Xesh jadvallar dasturlashdagi kuchli vositalar bo‘lib, ma’lumotlarni samarali boshqarish va ularga murojaat qilishga yordam beradi.

Xesh to‘plam yoki xesh map’dan foydalanish nimaga ehtiyojingiz borligiga bog‘liq: shunchaki biror narsa bor-yo‘qligini bilishmi yoki u haqida batafsil ma’lumot topishmi.