পাইথনে হ্যাশসেট ডিজাইন (Design HashSet)

সমস্যা বিবরণ

বিল্ট-ইন হ্যাশ টেবিল ছাড়া একটি HashSet ডিজাইন করুন যা সাপোর্ট করে:

• add(key) — ভ্যালু ইনসার্ট।
• contains(key) — উপস্থিতি চেক।
• remove(key) — ভ্যালু মুছে দিন।

ডিজাইন (Bucket Array + List)

1. Bucket ক্লাস: ইন্টারনালি একটি লিস্ট রেখে update, get, remove মেথড।
2. MyHashSet ক্লাস:
   • key_space = 2096 (বাল্টি সংখ্যা)।
   • hash_table = [Bucket() for _ in range(key_space)]।
   • _hash(key) = key % key_space।
   • add: হ্যাশ করে বাল্টিতে update।
   • remove: হ্যাশ করে বাল্টি থেকে remove।
   • contains: হ্যাশ করে বাল্টিতে get।

পাইথন বাস্তবায়ন

class Bucket:
    def __init__(self):
        self.bucket = []
    
    def update(self, key):
        for i, k in enumerate(self.bucket):
            if k == key:
                self.bucket[i] = key
                return
        self.bucket.append(key)
    
    def get(self, key):
        return key in self.bucket
    
    def remove(self, key):
        for i, k in enumerate(self.bucket):
            if k == key:
                del self.bucket[i]
                return

class MyHashSet:
    def __init__(self):
        self.key_space = 2096
        self.hash_table = [Bucket() for _ in range(self.key_space)]
    
    def add(self, key):
        self.hash_table[key % self.key_space].update(key)
    
    def remove(self, key):
        self.hash_table[key % self.key_space].remove(key)
    
    def contains(self, key):
        return self.hash_table[key % self.key_space].get(key)

# টেস্ট
ob = MyHashSet()
ob.add(1); ob.add(3)
print(ob.contains(1))  # True
print(ob.contains(2))  # False
ob.add(2)
print(ob.contains(2))  # True
ob.remove(2)
print(ob.contains(2))  # False

আউটপুট

True False True False