Design HashMap ใน Python: สร้าง HashMap แบบกำหนดเอง

ออกแบบ HashMap โดยไม่ใช้ไลบรารี built-in รองรับ 3 เมธอด: put(key, value), get(key), remove(key) ใช้การจัดการชนกันแบบ Separate Chaining ด้วย Linked List

โครงสร้างข้อมูล

• Node: เก็บ key, val, next
• LinkedList: จัดการโหนด (search, add, get, remove)
• MyHashMap: อาร์เรย์ของ LinkedList ขนาดคงที่ (prime number เช่น 1033) ใช้ key % size เป็น hash

ตัวอย่างการใช้งาน

put(1,1); put(2,2); get(1)→1; get(3)→-1; put(2,1); get(2)→1; remove(2); get(2)→-1

การติดตั้งใน Python

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.buckets = [LinkedList() for _ in range(self.size)]
    def _hash(self, key):
        return key % self.size
    def put(self, key, value):
        self.buckets[self._hash(key)].add(key, value)
    def get(self, key):
        ret = self.buckets[self._hash(key)].get(key)
        return ret if ret is not None else -1
    def remove(self, key):
        self.buckets[self._hash(key)].remove(key)

# Test
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