পাইথনে হ্যাশসেট ডিজাইন করুন

ধরুন আমরা কোনো বিল্ট-ইন হ্যাশ টেবিল লাইব্রেরি ব্যবহার না করে একটি হ্যাশসেট ডেটা স্ট্রাকচার ডিজাইন করতে চাই। −

• add(x) − হ্যাশসেটে একটি মান x সন্নিবেশ করায়।
• ধারণ করে(x) − হ্যাশসেটে x মান আছে কিনা তা পরীক্ষা করে।
• রিমুভ(x) - হ্যাশসেট থেকে x সরিয়ে দেয়। হ্যাশসেটে মানটি বিদ্যমান না থাকলে, কিছুই করবেন না।

সুতরাং, এটি পরীক্ষা করার জন্য হ্যাশ সেট শুরু করুন, তারপর যোগ করুন (1), যোগ করুন (3), অন্তর্ভুক্ত (1), অন্তর্ভুক্ত (2), যোগ করুন (2), অন্তর্ভুক্ত (2), অপসারণ(2), অন্তর্ভুক্ত (2) কল করুন। ), তাহলে আউটপুট যথাক্রমে সত্য (1 উপস্থিত), মিথ্যা (2 উপস্থিত নয়), সত্য (2 উপস্থিত), মিথ্যা (2 উপস্থিত নয়) হবে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• বাকেট নামে একটি ডেটা স্ট্রাকচার সংজ্ঞায়িত করুন, নিচের মত শুরু করুন
• বালতি :=একটি নতুন তালিকা
• একটি ফাংশন আপডেট () সংজ্ঞায়িত করুন। এটি কী লাগবে
• পাওয়া :=মিথ্যা
• বালতিতে প্রতিটি সূচক i এবং কী k-এর জন্য, করুন
  • কি যদি k এর মত হয়, তাহলে
    • বালতি[i]:=কী
    • found:=সত্য
    • লুপ থেকে বেরিয়ে আসুন
  • যদি মিথ্যা পাওয়া যায়, তাহলে
    • বালতির শেষে কী সন্নিবেশ করান
• একটি ফাংশন get() সংজ্ঞায়িত করুন। এটি কী
  নেবে
  • বালতিতে প্রতিটি k-এর জন্য, করুন
    • যদি k কী এর মত হয়, তাহলে
      • সত্য ফেরান
    • মিথ্যে ফেরত দিন
• একটি ফাংশন রিমুভ () সংজ্ঞায়িত করুন। এটি কী
  নেবে
  • বালতিতে প্রতিটি সূচক i এবং কী k-এর জন্য, করুন
    • কি যদি k এর মত হয়, তাহলে
      • বালতি মুছুন[i]
• এখন কাস্টম হ্যাশসেট তৈরি করুন। নিম্নরূপ কিছু পদ্ধতি থাকবে
• নিম্নলিখিতভাবে এটি শুরু করুন -
• কী_স্পেস :=2096
• হ্যাশ_টেবিল:=কী_স্পেস আকারের বাকেট টাইপ অবজেক্টের একটি তালিকা
• একটি ফাংশন সংজ্ঞায়িত করুন()। এটি কী
  নেবে
  • হ্যাশ_কি:=কী মোড কী_স্পেস
  • হ্যাশ_টেবল[হ্যাশ_কি]-এর কল আপডেট(কী)
• একটি ফাংশন রিমুভ () সংজ্ঞায়িত করুন। এটি কী
  নেবে
  • hash_key:=keymodkey_space
  • হ্যাশ_টেবল[হ্যাশ_কি] থেকে কী মুছুন
• একটি ফাংশন সংজ্ঞায়িত করুন যেটিতে রয়েছে()। এটি কী
  নেবে
  • hash_key:=keymodkey_space
  • হ্যাশ_টেবল[হ্যাশ_কি] এর গেট(কী) ফেরত দিন।

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Bucket:
   def __init__(self):
      self.bucket=[]
   def update(self, key):
      found=False
      for i,k in enumerate(self.bucket):
         if key==k:
            self.bucket[i]=key
            found=True
            break
      if not found:
         self.bucket.append(key)
   def get(self, key):
      for k in self.bucket:
         if k==key:
            return True
      return False
   def remove(self, key):
      for i,k in enumerate(self.bucket):
         if key==k:
            del self.bucket[i]
class MyHashSet:
   def __init__(self):
      self.key_space = 2096
      self.hash_table=[Bucket() for i in range(self.key_space)]
   def add(self, key):
      hash_key=key%self.key_space
      self.hash_table[hash_key].update(key)
   def remove(self, key):
      hash_key=key%self.key_space
      self.hash_table[hash_key].remove(key)
   def contains(self, key):
      hash_key=key%self.key_space
      return self.hash_table[hash_key].get(key)
ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

ইনপুট

ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

আউটপুট

True
False
True
False