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

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

• put(key, value) - यह हैश मैप में कुंजी से जुड़ा एक मान डालेगा। यदि मान पहले से हैश मैप में मौजूद है, तो मान को अपडेट करें।
• get(key) - यह वह मान लौटाएगा जिस पर निर्दिष्ट कुंजी मैप की गई है, अन्यथा -1 जब इस मानचित्र में कुंजी के लिए कोई मैपिंग नहीं है।
• remove(key) - यदि इस मैप में कुंजी के लिए मैपिंग है तो यह वैल्यू की के लिए मैपिंग को हटा देगा।

इसलिए, यदि इनपुट इनिशियलाइज़ेशन के बाद जैसा है, तो पुट को कॉल करें और निम्नानुसार विधियाँ प्राप्त करें -

• पुट(1, 1);
• पुट(2, 2);
• प्राप्त करें(1);
• प्राप्त करें(3);
• पुट(2, 1);
• प्राप्त(2);
• निकालें(2);
• प्राप्त(2);

तो आउटपुट क्रमशः 1, -1 (मौजूद नहीं), 1, -1 (मौजूद नहीं) होगा।

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

• नोड नामक एक नई डेटा संरचना बनाएं, और इसे प्रारंभ करने के लिए, कुछ फ़ील्ड जैसे (कुंजी, वैल, अगला) होंगे, अगला प्रारंभ में शून्य है
• एक लिंक्ड सूची को परिभाषित करें, कुछ विधियाँ इस प्रकार हैं -
• एक प्रारंभकर्ता को परिभाषित करें, यह इस प्रकार काम करेगा -
  • प्रीहेड:=एक नया नोड नोड जिसमें कुंजी =नल और वैल =नल
• फ़ंक्शन खोज को परिभाषित करें ()। यह कुंजी लेगा
• p :=prehead.next
• जबकि p रिक्त नहीं है, करें
  • यदि p.key कुंजी के समान है, तो
    • वापसी पी
  • p :=p.next
• कोई नहीं लौटाएं
• एक फंक्शन ऐड () को परिभाषित करें। यह कुंजी लेगा, वैल
• p :=खोज (कुंजी)
• यदि p रिक्त नहीं है, तो
  • p.val:=वैल
• अन्यथा,
  • नोड:=नया नोड (कुंजी, वैल) के साथ
  • prehead.next:=नोड, node.next:=prehead.next
• एक फ़ंक्शन को परिभाषित करें ()। यह कुंजी लेगा
• p :=खोज (कुंजी)
• यदि p रिक्त नहीं है, तो
  • पी.वैल लौटाएं
• अन्यथा,
  • वापसी शून्य
• एक फंक्शन रिमूव को परिभाषित करें। यह कुंजी लेगा
• पिछला :=शीर्षासन
• वक्र:=पिछला.अगला
• जबकि वक्र शून्य नहीं है, करें
  • यदि cur.key कुंजी के समान है, तो
    • लूप से बाहर आएं
  • पिछला :=curr, cur :=cur.next
  • यदि वक्र शून्य नहीं है, तो
    • पिछला.अगला:=cur.next
• एक फ़ंक्शन को क्रमबद्ध करें () परिभाषित करें।
• p :=prehead.next
• रिट:=एक नई सूची
• जबकि p रिक्त नहीं है, करें
  • अंत में रिट में [p.key, p.val] डालें
  • p :=p.next
• रिटर्न रिटर्न
• कस्टम हैशमैप से, विधियों को निम्नानुसार परिभाषित करें -
• एक प्रारंभकर्ता को परिभाषित करें।
• आकार :=1033
• गिरफ्तारी:=LinkedList() की एक सरणी जिसकी लंबाई आकार के समान है
• एक फ़ंक्शन को परिभाषित करें _hash()। यह कुंजी लेगा
• रिटर्न की मॉड साइज
• फ़ंक्शन को परिभाषित करें put() । यह कुंजी, मान लेगा
• ज:=_हैश(कुंजी)
• गिरफ्तारी का (कुंजी, मान) जोड़ें[h]
• एक फ़ंक्शन को परिभाषित करें ()। यह कुंजी लेगा
• ज:=_हैश(कुंजी)
• ret :=arr[h]
. की प्राप्त (कुंजी) प्राप्त करें
• यदि रिट शून्य नहीं है, तो
  • रिटर्न रिटर्न
• अन्यथा,
  • वापसी -1
• एक फंक्शन रिमूव () को परिभाषित करें। यह कुंजी लेगा
• ज:=_हैश(कुंजी)
• गिरफ्तारी से कुंजी हटाएं[h]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Node:
   def __init__(self, key, val):
      self.key = key
      self.val = val
      self.next = None
class LinkedList:
   def __init__(self):
      self.prehead = Node(None, None)
   def search(self, key):
      p = self.prehead.next
      while p:
         if p.key == key:
            return p
         p = p.next
      return None
   def add(self, key, val):
      p = self.search(key)
      if p:
         p.val = val
      else:
         node = Node(key, val)
         self.prehead.next, node.next = node, self.prehead.next
   def get(self, key):
      p = self.search(key)
      if p:
         return p.val
      else:
         return None
   def remove(self, key):
      prev = self.prehead
      cur = prev.next
      while cur:
         if cur.key == key:
            break
         prev, cur = cur, cur.next
      if cur:
         prev.next = cur.next
   def serialize(self):
      p = self.prehead.next
      ret = []
      while p:
         ret.append([p.key, p.val])
         p = p.next
      return ret
class MyHashMap:
   def __init__(self):
      self.size = 1033
      self.arr = [LinkedList() for _ in range(self.size)]
   def _hash(self, key):
      return key % self.size
   def put(self, key, value):
      h = self._hash(key)
      self.arr[h].add(key, value)
   def get(self, key):
      h = self._hash(key)
      ret = self.arr[h].get(key)
      if ret is not None:
         return ret
      else:
         return -1
   def remove(self, key):
      h = self._hash(key)
      self.arr[h].remove(key)
ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

इनपुट

ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

आउटपुट

1
-1
1
-1