DSA xesh map’lar (Hash Map)

Xesh map’lar (Hash Map)

Xesh map (Hash Map) — odatda ko‘p sonli yozuvlarni saqlaydigan xesh jadval ma’lumotlar tuzilmasining bir ko‘rinishi.

Xesh map yordamida yozuvlarni juda tez qidirish, qo‘shish, o‘zgartirish va olib tashlash mumkin.

Xesh map’lar biror narsa haqida batafsil ma’lumot topish uchun ishlatiladi.

Quyidagi simulyatsiyada odamlar xesh map’da saqlanadi. Odamni uning noyob ijtimoiy xavfsizlik raqami (xesh map kaliti) orqali qidirish mumkin, so‘ngra o‘sha odamning ismini (xesh map qiymati) ko‘rishimiz mumkin.

Agar avval xesh jadvallar va xesh to‘plamlar haqidagi oldingi ikki sahifani ko‘rib chiqsangiz, xesh map’lar qanday ishlashini tushunish osonroq bo‘ladi. Quyidagi so‘zlarning ma’nosini tushunish ham muhim.

• Yozuv (entry): Kalit va qiymatdan iborat bo‘lib, kalit-qiymat juftligini hosil qiladi.
• Kalit: Xesh map’dagi har bir yozuv uchun noyob. Yozuvning xesh map’dagi bucketini aniqlaydigan xesh kodni hosil qilish uchun ishlatiladi. Bu har bir yozuvni samarali topish mumkinligini ta’minlaydi.
• Xesh kod: Xesh map yozuvi qaysi bucketga tegishli ekanini aniqlash uchun yozuv kalitidan hosil qilingan son.
• Bucket (savat): Xesh map yozuvlarni saqlash uchun shunday ko‘plab bucketlar, ya’ni konteynerlardan iborat.
• Qiymat: Deyarli har qanday ma’lumot bo‘lishi mumkin, masalan, odamning ismi, tug‘ilgan sanasi va manzili. Qiymat bir nechta turli ma’lumotlarning birikmasi bo‘lishi mumkin.

Xesh kodni topish

Xesh kod xesh funksiya tomonidan hosil qilinadi.

Yuqoridagi simulyatsiyadagi xesh funksiya ijtimoiy xavfsizlik raqamidagi raqamlarni (chiziqchani emas) oladi, ularni qo‘shadi va xesh kodni 0 dan 9 gacha bo‘lgan son sifatida olish uchun belgilar yig‘indisi ustida 10 bo‘yicha modulo amalini (% 10) bajaradi.

Bu shuni anglatadiki, odam o‘zining ijtimoiy xavfsizlik raqami xesh kodiga ko‘ra xesh map’dagi o‘nta mumkin bo‘lgan bucketdan birida saqlanadi. Xesh map’dan odamni qidirish yoki olib tashlash kerak bo‘lganda ham xuddi shu xesh kod hosil qilinadi va ishlatiladi.

Tegishli bucketda faqat bitta odam bo‘lsa, xesh kod bizga darhol murojaat qilish imkonini beradi.

Yuqoridagi simulyatsiyada Charlottening ijtimoiy xavfsizlik raqami 123-4567. Raqamlarni qo‘shsak, 28 yig‘indisi hosil bo‘ladi, uning 10 bo‘yicha modulosi esa 8. Shuning uchun u 8-bucketga tegishli.

Xesh map’larda to‘g‘ridan-to‘g‘ri murojaat

Xesh map’da Charlotteni qidirish uchun yuqorida tushuntirilganidek, 8 xesh kodini hosil qiluvchi 123-4567 ijtimoiy xavfsizlik raqamidan (xesh map kalitidan) foydalanishimiz kerak.

Bu shuni anglatadiki, xesh map’dagi boshqa yozuvlarni ko‘rib chiqmasdan, uning ismini (xesh map qiymatini) olish uchun to‘g‘ridan-to‘g‘ri 8-bucketga borishimiz mumkin.

Bunday hollarda xesh map yozuvlarni qidirish, qo‘shish va olib tashlash uchun konstant vaqt \(O(1)\) ga ega deymiz, bu massiv yoki bog‘langan ro‘yxatdan foydalanishga qaraganda juda tez.

Biroq eng yomon holatda barcha odamlar bitta bucketda saqlanadi va agar biz topmoqchi bo‘lgan odam shu bucketdagi oxirgi odam bo‘lsa, izlayotgan odamimizni topishdan oldin o‘sha bucketdagi boshqa barcha ijtimoiy xavfsizlik raqamlari bilan solishtirishimiz kerak bo‘ladi.

Bunday eng yomon holatda xesh map’ning vaqt murakkabligi \(O(n)\) bo‘ladi, bu massivlar va bog‘langan ro‘yxatlarning vaqt murakkabligi bilan bir xil.

Shu sababli xesh map’larni tez saqlash uchun yozuvlarni bucketlar o‘rtasida teng taqsimlaydigan xesh funksiyaga ega bo‘lish va taxminan xesh map yozuvlari soncha bucketga ega bo‘lish muhim.

Xesh map yozuvlariga qaraganda ancha ko‘p bucketga ega bo‘lish xotirani isrof qilishdir, xesh map yozuvlariga qaraganda ancha kam bucketga ega bo‘lish esa vaqtni isrof qilishdir.

Xesh map’ni amalga oshirish

Python’da xesh map’lar odatda Python’ning o‘zining dictionary ma’lumot turi yordamida yaratiladi, ammo xesh map’lar qanday ishlashini yaxshiroq tushunish uchun bu yerda undan foydalanmaymiz.

Python’da xesh map’ni amalga oshirish uchun SimpleHashMap sinfini yaratamiz.

SimpleHashMap sinfi ichida xesh map’ni initsializatsiya qilish uchun __init__ metodi, xesh funksiya uchun hash_function metodi hamda xesh map’ning asosiy amallari uchun metodlar bor: put, get va remove.

Shuningdek, xesh map qanday ko‘rinishini yaxshiroq ko‘rish uchun print_map metodini ham yaratamiz.

class SimpleHashMap:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

SimpleHashMap sinfidan foydalanib, ushbu sahifaning yuqorisidagi xesh map’ning aynan o‘zini yaratishimiz mumkin:

class SimpleHashMap:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

# Creating the Hash Map from the simulation
hash_map = SimpleHashMap(size=10)

# Adding some entries
hash_map.put("123-4567", "Charlotte")
hash_map.put("123-4568", "Thomas")
hash_map.put("123-4569", "Jens")
hash_map.put("123-4570", "Peter")
hash_map.put("123-4571", "Lisa")
hash_map.put("123-4672", "Adele")
hash_map.put("123-4573", "Michaela")
hash_map.put("123-6574", "Bob")

hash_map.print_map()

# Demonstrating retrieval
print("\nName associated with '123-4570':", hash_map.get("123-4570"))

print("Updating the name for '123-4570' to 'James'")
hash_map.put("123-4570","James")

# Checking if Peter is still there
print("Name associated with '123-4570':", hash_map.get("123-4570"))