DSA xesh to‘plamlar (Hash Set)

Xesh to‘plamlar (Hash Set)

Xesh to‘plam (Hash Set) — odatda ko‘p sonli elementlarni saqlaydigan xesh jadval ma’lumotlar tuzilmasining bir ko‘rinishi.

Xesh to‘plam yordamida elementlarni juda tez qidirish, qo‘shish va olib tashlash mumkin.

Xesh to‘plamlar qidirish, ya’ni element to‘plamning bir qismi ekanini tekshirish uchun ishlatiladi.

Xesh to‘plam noyob elementlarni elementning xesh kodiga ko‘ra bucketlarda saqlaydi.

• Xesh kod: Xesh to‘plam elementi qaysi bucketga tegishli ekanini aniqlash uchun elementning noyob qiymatidan (kalitidan) hosil qilingan son.
• Noyob elementlar: Xesh to‘plamda bir xil qiymatli bittadan ortiq element bo‘lishi mumkin emas.
• Bucket (savat): Xesh to‘plam elementlarni saqlash uchun shunday ko‘plab bucketlar, ya’ni konteynerlardan iborat. Agar ikki element bir xil xesh kodga ega bo‘lsa, ular bitta bucketga tegishli bo‘ladi. Shu sababli bucketlar ko‘pincha massivlar yoki bog‘langan ro‘yxatlar sifatida amalga oshiriladi, chunki bucket bittadan ortiq elementni saqlay olishi kerak.

Xesh kodni topish

Xesh kod xesh funksiya tomonidan hosil qilinadi.

Yuqoridagi animatsiyadagi xesh funksiya kiritish maydoniga yozilgan ismni oladi va shu ismdagi har bir belgining Unicode kod nuqtalarini qo‘shib chiqadi.

Shundan so‘ng xesh funksiya 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, ism o‘sha ismning xesh kodiga ko‘ra xesh to‘plamdagi o‘nta mumkin bo‘lgan bucketdan biriga joylashtiriladi. Xesh to‘plamdan ismni qidirish yoki olib tashlash kerak bo‘lganda ham xuddi shu xesh kod hosil qilinadi va ishlatiladi.

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

Xesh to‘plamlarda to‘g‘ridan-to‘g‘ri murojaat

Yuqoridagi xesh to‘plamda Peterni qidirish 2 xesh kodi hosil qilinishini (512 % 10) anglatadi va bu bizni to‘g‘ridan-to‘g‘ri Peter joylashgan bucketga yo‘naltiradi. Agar bu o‘sha bucketdagi yagona ism bo‘lsa, Peterni darhol topamiz.

Bunday hollarda xesh to‘plam elementlarni qidirish, qo‘shish va olib tashlash uchun konstant vaqt \(O(1)\) ga ega deymiz, bu juda tez.

Biroq Jensni qidirsak, Jensni topishdan oldin o‘sha bucketdagi boshqa ismlarni ko‘rib chiqishimiz kerak. Eng yomon holatda barcha ismlar bitta bucketga tushib qoladi va biz qidirayotgan ism eng oxirgisi bo‘ladi. Bunday eng yomon holatda xesh to‘plamning vaqt murakkabligi \(O(n)\) bo‘ladi, bu massivlar va bog‘langan ro‘yxatlarning vaqt murakkabligi bilan bir xil.

Shu sababli xesh to‘plamlarni tez saqlash uchun elementlarni bucketlar o‘rtasida teng taqsimlaydigan xesh funksiyaga ega bo‘lish va taxminan xesh to‘plam elementlari soncha bucketga ega bo‘lish muhim.

Xesh to‘plam elementlariga qaraganda ancha ko‘p bucketga ega bo‘lish xotirani isrof qilishdir, xesh to‘plam elementlariga qaraganda ancha kam bucketga ega bo‘lish esa vaqtni isrof qilishdir.

Xesh to‘plamni amalga oshirish

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

Python’da xesh to‘plamni amalga oshirish uchun SimpleHashSet sinfini yaratamiz.

SimpleHashSet sinfi ichida xesh to‘plamni initsializatsiya qilish uchun __init__ metodi, xesh funksiya uchun hash_function metodi hamda xesh to‘plamning asosiy amallari uchun metodlar bor: add, contains va remove.

Shuningdek, xesh to‘plam qanday ko‘rinishini yaxshiroq ko‘rish uchun print_set metodini ham yaratamiz.

class SimpleHashSet:
    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, value):
        # Simple hash function: sum of character codes modulo the number of buckets
        return sum(ord(char) for char in value) % self.size

    def add(self, value):
        # Add a value if it's not already present
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        # Check if a value exists in the set
        index = self.hash_function(value)
        bucket = self.buckets[index]
        return value in bucket

    def remove(self, value):
        # Remove a value
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value in bucket:
            bucket.remove(value)

    def print_set(self):
        # Print all elements in the hash set
        print("Hash Set Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

SimpleHashSet sinfidan foydalanib, ushbu sahifaning yuqorisidagi xesh to‘plamning aynan o‘zini yaratishimiz mumkin:

class SimpleHashSet:
    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, value):
        # Simple hash function: sum of character codes modulo the number of buckets
        return sum(ord(char) for char in value) % self.size

    def add(self, value):
        # Add a value if it's not already present
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        # Check if a value exists in the set
        index = self.hash_function(value)
        bucket = self.buckets[index]
        return value in bucket

    def remove(self, value):
        # Remove a value
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value in bucket:
            bucket.remove(value)

    def print_set(self):
        # Print all elements in the hash set
        print("Hash Set Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

# Creating the Hash Set from the simulation
hash_set = SimpleHashSet(size=10)

hash_set.add("Charlotte")
hash_set.add("Thomas")
hash_set.add("Jens")
hash_set.add("Peter")
hash_set.add("Lisa")
hash_set.add("Adele")
hash_set.add("Michaela")
hash_set.add("Bob")

hash_set.print_set()

print("\n'Peter' is in the set:",hash_set.contains('Peter'))
print("Removing 'Peter'")
hash_set.remove('Peter')
print("'Peter' is in the set:",hash_set.contains('Peter'))
print("'Adele' has hash code:",hash_set.hash_function('Adele'))