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

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

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

इसे टेस्ट करने के लिए हैश सेट को इनिशियलाइज़ करें, फिर add(1), add(3), contains(1), contains(2), add(2), contains(2), remove(2), contains(2) कॉल करें। आउटपुट क्रमशः true (1 मौजूद है), false (2 मौजूद नहीं), true (2 मौजूद है), false (2 मौजूद नहीं) होगा।

हल करने के चरण

• Bucket नामक एक डेटा संरचना परिभाषित करें, इसे इस प्रकार इनिशियलाइज़ करें:
  • bucket := एक नई सूची
• update() फ़ंक्शन परिभाषित करें। यह key लेगा
  • found := False
  • bucket में प्रत्येक सूचकांक i और कुंजी k के लिए:
    • यदि key, k के बराबर है, तो:
      • bucket[i] := key
      • found := True
      • लूप से बाहर निकलें
  • यदि found False है, तो:
    • key को bucket के अंत में डालें
• get() फ़ंक्शन परिभाषित करें। यह key लेगा
  • bucket में प्रत्येक k के लिए:
    • यदि k, key के बराबर है, तो True वापस करें
  • False वापस करें
• remove() फ़ंक्शन परिभाषित करें। यह key लेगा
  • bucket में प्रत्येक सूचकांक i और कुंजी k के लिए:
    • यदि key, k के बराबर है, तो:
      • bucket[i] हटाएं
• अब कस्टम हैशसेट बनाएं। कुछ मेथड्स होंगे:
  • इसे इस प्रकार इनिशियलाइज़ करें:
    • key_space := 2096
    • hash_table := Bucket() प्रकार की वस्तुओं की सूची जिसका आकार key_space है
  • add() फ़ंक्शन परिभाषित करें। यह key लेगा
    • hash_key := key mod key_space
    • hash_table[hash_key] का update(key) कॉल करें
  • remove() फ़ंक्शन परिभाषित करें। यह key लेगा
    • hash_key := key mod key_space
    • hash_table[hash_key] से key हटाएं
  • contains() फ़ंक्शन परिभाषित करें। यह key लेगा
    • hash_key := key mod key_space
    • hash_table[hash_key] का get(key) वापस करें

उदाहरण

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