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

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

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

उदाहरण के लिए, यदि इनपुट प्रारंभिककरण के बाद put और get मेथड्स को इस प्रकार कॉल किया जाता है:

• put(1, 1);
• put(2, 2);
• get(1);
• get(3);
• put(2, 1);
• get(2);
• remove(2);
• get(2);

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

हल करने के चरण

• node नामक एक नई डेटा संरचना बनाएं, जिसे प्रारंभ करने के लिए (key, val, next) जैसे फ़ील्ड हों, next प्रारंभ में null
• एक लिंक्ड सूची परिभाषित करें, कुछ मेथड्स हैं:
  • एक इनिशियलाइज़र परिभाषित करें, यह इस प्रकार काम करेगा:
    • prehead := key = null और val = null के साथ एक नया नोड Node
  • search() फ़ंक्शन परिभाषित करें। यह key लेगा
    • p := prehead.next
    • जब तक p null नहीं है:
      • यदि p.key, key के बराबर है, तो p वापस करें
      • p := p.next
    • None वापस करें
  • add() फ़ंक्शन परिभाषित करें। यह key, val लेगा
    • p := search(key)
    • यदि p null नहीं है, तो p.val := val
    • अन्यथा:
      • node := (key, val) के साथ नया Node
      • prehead.next := node, node.next := prehead.next
  • get() फ़ंक्शन परिभाषित करें। यह key लेगा
    • p := search(key)
    • यदि p null नहीं है, तो p.val वापस करें
    • अन्यथा, null वापस करें
  • remove फ़ंक्शन परिभाषित करें। यह key लेगा
    • prev := prehead
    • cur := prev.next
    • जब तक cur null नहीं है:
      • यदि cur.key, key के बराबर है, तो लूप से बाहर आएं
      • prev := curr, cur := cur.next
      • यदि cur null नहीं है, तो prev.next := cur.next
  • serialize() फ़ंक्शन परिभाषित करें।
    • p := prehead.next
    • ret := एक नई सूची
    • जब तक p null नहीं है:
      • [p.key, p.val] को ret के अंत में डालें
      • p := p.next
    • ret वापस करें
  • कस्टम हैशमैप से, मेथड्स को इस प्रकार परिभाषित करें:
    • एक इनिशियलाइज़र परिभाषित करें।
      • size := 1033
      • arr := LinkedList() की एक सरणी जिसकी लंबाई size के बराबर है
    • _hash() फ़ंक्शन परिभाषित करें। यह key लेगा
      • key mod size वापस करें
    • put() फ़ंक्शन परिभाषित करें। यह key, value लेगा
      • h := _hash(key)
      • arr[h] का add(key, value)
    • get() फ़ंक्शन परिभाषित करें। यह key लेगा
      • h := _hash(key)
      • ret := arr[h] का get(key)
      • यदि ret null नहीं है, तो ret वापस करें
      • अन्यथा, -1 वापस करें
    • remove() फ़ंक्शन परिभाषित करें। यह key लेगा
      • h := _hash(key)
      • arr[h] से key हटाएं

  उदाहरण

  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