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

ধরুন আমরা কোনো বিল্ট-ইন হ্যাশ টেবিল লাইব্রেরি ব্যবহার না করে একটি হ্যাশম্যাপ ডিজাইন করতে চাই। নিচের মত বিভিন্ন ফাংশন থাকবে -

• পুট(কী, মান) - এটি হ্যাশম্যাপে কী-এর সাথে যুক্ত একটি মান সন্নিবেশ করবে। যদি হ্যাশম্যাপে মানটি ইতিমধ্যেই বিদ্যমান থাকে তবে মানটি আপডেট করুন।
• get(key) − এটি সেই মানটি ফেরত দেবে যেখানে নির্দিষ্ট কী ম্যাপ করা হয়েছে, অন্যথায় -1 যখন এই মানচিত্রে কীটির জন্য কোনও ম্যাপিং থাকবে না৷
• রিমুভ(কী) − যদি এই ম্যাপে কী-এর ম্যাপিং থাকে তাহলে এটি মান কী-এর ম্যাপিং সরিয়ে দেবে৷

সুতরাং, যদি ইনপুটটি আফটার ইনিশিয়ালাইজেশনের মত হয়, তাহলে পুটকে কল করুন এবং নিম্নলিখিত পদ্ধতিগুলি পান −

• পুট(1, 1);
• পুট(2, 2);
• পান(1);
• গেট(3);
• পুট(2, 1);
• পান(2);
• সরান(2);
• পান(2);

তাহলে আউটপুট হবে যথাক্রমে 1, -1 (বর্তমান নয়), 1, -1 (বর্তমান নয়)।

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

• নোড নামে একটি নতুন ডেটা স্ট্রাকচার তৈরি করুন এবং এটিকে আরম্ভ করার জন্য কিছু ক্ষেত্র থাকবে যেমন (কী, ভ্যাল, নেক্সট), পরবর্তীটি প্রাথমিকভাবে শূন্য হয়
• একটি লিঙ্কযুক্ত তালিকা সংজ্ঞায়িত করুন, নিম্নরূপ কয়েকটি পদ্ধতি রয়েছে -
• একটি ইনিশিয়ালাইজার সংজ্ঞায়িত করুন, এটি নিম্নরূপ কাজ করবে -
  • প্রিহেড :=কী =নাল এবং ভ্যাল =নাল সহ একটি নতুন নোড নোড
• একটি ফাংশন অনুসন্ধান () সংজ্ঞায়িত করুন। এটি কী লাগবে
• p :=prehead.next
• যদিও p শূন্য না, do
  • যদি p.key কী এর মত হয়, তাহলে
    • রিটার্ন p
  • p :=p.next
• কিছুই ফেরত দেবেন না
• একটি ফাংশন সংজ্ঞায়িত করুন()। এটি কী, ভ্যাল
লাগবে
• p :=অনুসন্ধান(কী)
• যদি p শূন্য না হয়, তাহলে
  • p.val :=val
• অন্যথায়,
  • নোড :=(কী, ভ্যাল) সহ নতুন নোড
  • prehead.next :=নোড, node.next :=prehead.next
• একটি ফাংশন get() সংজ্ঞায়িত করুন। এটি কী লাগবে
• p :=অনুসন্ধান(কী)
• যদি p শূন্য না হয়, তাহলে
  • রিটার্ন p.val
• অন্যথায়,
  • রিটার্ন নাল
• একটি ফাংশন অপসারণ সংজ্ঞায়িত করুন। এটি কী লাগবে
• পূর্ববর্তী :=প্রিহেড
• cur :=prev.next
• যদিও cur নাল না হয়, do
  • যদি cur.key কী এর মত হয়, তাহলে
    • লুপ থেকে বেরিয়ে আসুন
  • পূর্ববর্তী :=curr, cur :=cur.next
  • যদি cur শূন্য না হয়, তাহলে
    • prev.next :=cur.next
• একটি ফাংশন সিরিয়ালাইজ () সংজ্ঞায়িত করুন।
• p :=prehead.next
• ret :=একটি নতুন তালিকা
• যদিও p শূন্য না, do
  • শেষে ret এ [p.key, p.val] ঢোকান
  • p :=p.next
• রিটার্ন রিটার্ন
• কাস্টম হ্যাশম্যাপ থেকে, নিম্নলিখিত পদ্ধতিগুলি সংজ্ঞায়িত করুন -
• একটি ইনিশিয়ালাইজার সংজ্ঞায়িত করুন।
• আকার :=1033
• arr :=LinkedList() এর একটি অ্যারে যার দৈর্ঘ্য আকারের সমান
• একটি ফাংশন _hash() সংজ্ঞায়িত করুন। এটি কী লাগবে
• রিটার্ন কী মোড সাইজ
• একটি ফাংশন সংজ্ঞায়িত করুন put()। এটি কী, মান নিবে
• h :=_hash(কী)
• add(key, value) of arr[h]
• একটি ফাংশন get() সংজ্ঞায়িত করুন। এটি কী লাগবে
• h :=_hash(কী)
• ret :=get(key) of arr[h]
• যদি ret নাল না হয়, তাহলে
  • রিটার্ন রিটার্ন
• অন্যথায়,
  • রিটার্ন -1
• একটি ফাংশন রিমুভ () সংজ্ঞায়িত করুন। এটি কী লাগবে
• h :=_hash(কী)
• Arr[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