সমস্যা বিবরণ
বিল্ট-ইন হ্যাশ টেবিল লাইব্রেরি ছাড়া একটি HashMap ডিজাইন করুন যা নিম্নলিখিত অপারেশন সাপোর্ট করে:
put(key, value)— কী-ভ্যালু জোড়া ইনসার্ট/আপডেট।get(key)— ভ্যালু রিটার্ন করুন, না থাকলে -1।remove(key)— কী-ভ্যালু জোড়া মুছুন।
ডিজাইন (Chaining with Linked List)
- একটি
Nodeক্লাস:key, val, next। - একটি
LinkedListক্লাস:preheadডামি নোড দিয়ে চেইনিং।search, add, get, remove, serializeমেথড। MyHashMapক্লাস:size = 1033(প্রাইম সংখ্যা)।arr = [LinkedList() for _ in range(size)]।_hash(key) = key % size।put: হ্যাশ করে বাল্টি খুঁজেadd।get: হ্যাশ করে বাল্টি থেকেget।remove: হ্যাশ করে বাল্টি থেকেremove।
পাইথন বাস্তবায়ন
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)
node.next = self.prehead.next
self.prehead.next = node
def get(self, key):
p = self.search(key)
return p.val if p else None
def remove(self, key):
prev = self.prehead
cur = prev.next
while cur:
if cur.key == key:
prev.next = cur.next
return
prev, cur = cur, cur.next
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):
self.arr[self._hash(key)].add(key, value)
def get(self, key):
ret = self.arr[self._hash(key)].get(key)
return ret if ret is not None else -1
def remove(self, key):
self.arr[self._hash(key)].remove(key)
# টেস্ট
ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1)) # 1
print(ob.get(3)) # -1
ob.put(2, 1)
print(ob.get(2)) # 1
ob.remove(2)
print(ob.get(2)) # -1আউটপুট
1 -1 1 -1
