पायथन में हैशसेट डिजाइन करें

मान लीजिए कि हम किसी भी अंतर्निहित हैश टेबल लाइब्रेरी का उपयोग किए बिना हैशसेट डेटा संरचना तैयार करना चाहते हैं। अलग-अलग कार्य होंगे जैसे -

• add(x) - हैशसेट में एक मान x डालें।
• contains(x) - जांचता है कि मान x हैशसेट में मौजूद है या नहीं।
• remove(x) - हैशसेट से x को हटाता है। यदि मान हैशसेट में मौजूद नहीं है, तो कुछ भी न करें।

तो, इसका परीक्षण करने के लिए हैश सेट को प्रारंभ करें, फिर जोड़ें (1), जोड़ें (3), शामिल (1), शामिल (2), जोड़ें (2), शामिल (2), निकालें (2), शामिल करें (2) ), तो आउटपुट क्रमशः सत्य होगा (1 मौजूद है), झूठा (2 मौजूद नहीं है), सत्य (2 मौजूद है), झूठा (2 मौजूद नहीं है)।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• बकेट नामक एक डेटा संरचना को परिभाषित करें, इसे नीचे की तरह प्रारंभ करें
• बकेट :=एक नई सूची
• फ़ंक्शन अपडेट को परिभाषित करें ()। यह कुंजी लेगा
• मिला:=झूठा
• बकेट में प्रत्येक अनुक्रमणिका i और कुंजी k के लिए, करें
  • यदि कुंजी k के समान है, तो
    • बाल्टी[i]:=कुंजी
    • मिला:=सच
    • लूप से बाहर आएं
  • गलत पाए जाने पर
    • बाल्टी के अंत में कुंजी डालें
• एक फ़ंक्शन को परिभाषित करें get() । इसमें कुंजी लगेगी
  • बाल्टी में प्रत्येक k के लिए, करें
    • यदि k कुंजी के समान है, तो
      • सही लौटें
    • झूठी वापसी
• एक फंक्शन रिमूव () को परिभाषित करें। इसमें कुंजी लगेगी
  • बकेट में प्रत्येक अनुक्रमणिका i और कुंजी k के लिए, करें
    • यदि कुंजी k के समान है, तो
      • बकेट हटाएं[i]
• अब कस्टम हैशसेट बनाएं। कुछ तरीके इस प्रकार होंगे
• इसे इस प्रकार प्रारंभ करें -
• की_स्पेस:=2096
• hash_table:=key_space के बकेट टाइप ऑब्जेक्ट की सूची
• एक फंक्शन ऐड () को परिभाषित करें। इसमें कुंजी लगेगी
  • हैश_की:=कुंजी मॉड की_स्पेस
  • हैश_टेबल [हैश_की] का कॉल अपडेट (कुंजी)
• एक फंक्शन रिमूव () को परिभाषित करें। इसमें कुंजी लगेगी
  • हैश_की:=keymodkey_space
  • हैश_टेबल से कुंजी हटाएं[हैश_की]
• एक फ़ंक्शन को परिभाषित करें जिसमें शामिल है ()। इसमें कुंजी लगेगी
  • हैश_की:=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