ออกแบบ HashSet ใน Python

สมมติว่าเราต้องการออกแบบโครงสร้างข้อมูล HashSet โดยไม่ต้องใช้ไลบรารีตารางแฮชในตัว จะมีฟังก์ชั่นที่แตกต่างกันเช่น -

• add(x) − แทรกค่า x ลงใน HashSet
• ประกอบด้วย(x) - ตรวจสอบว่าค่า x มีอยู่ใน HashSet หรือไม่
• remove(x) − ลบ x ออกจาก HashSet ในกรณีที่ไม่มีค่าใน HashSet ไม่ต้องทำอะไร

ดังนั้นเพื่อทดสอบ เริ่มต้นชุดแฮช จากนั้นเรียก add(1), add(3), ประกอบด้วย(1), มี(2), เพิ่ม(2), มี(2), ลบ(2), มี(2 ) จากนั้นผลลัพธ์จะเป็นจริง (1 คือปัจจุบัน) เท็จ (2 ไม่มีอยู่) จริง (2 คือปัจจุบัน) เท็จ (2 ไม่มีอยู่) ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดโครงสร้างข้อมูลหนึ่งโครงสร้างที่เรียกว่า Bucket เริ่มต้นตามด้านล่าง
• bucket :=รายการใหม่
• กำหนดฟังก์ชัน update() นี่จะใช้เวลาที่สำคัญ
• พบ :=เท็จ
• สำหรับแต่ละดัชนี i และคีย์ k ในบัคเก็ต ให้ทำ
  • ถ้าคีย์เหมือนกับ k แล้ว
    • bucket[i]:=คีย์
    • พบ:=จริง
    • ออกมาจากวงจร
  • หากพบว่าเป็นเท็จ
    • ใส่คีย์ที่ส่วนท้ายของที่เก็บข้อมูล
• กำหนดฟังก์ชัน get() นี่จะใช้เวลาที่สำคัญ
  • สำหรับแต่ละ k ในถัง ทำ
    • ถ้า k เหมือนกับคีย์ ดังนั้น
      • คืนค่า True
    • คืนค่าเท็จ
• กำหนดฟังก์ชัน remove() นี่จะใช้เวลาที่สำคัญ
  • สำหรับแต่ละดัชนี i และคีย์ k ในบัคเก็ต ให้ทำ
    • ถ้าคีย์เหมือนกับ k แล้ว
      • ลบที่เก็บข้อมูล[i]
• ตอนนี้สร้าง hashSet ที่กำหนดเอง จะมีวิธีการดังต่อไปนี้
• เริ่มต้นสิ่งนี้ดังนี้ −
• key_space :=2096
• hash_table:=รายการของวัตถุประเภทที่เก็บข้อมูลของขนาด key_space
• กำหนดฟังก์ชัน add() นี่จะใช้เวลาที่สำคัญ
  • hash_key:=ตัวดัดแปลงคีย์ key_space
  • เรียก update(key) ของ hash_table[hash_key]
• กำหนดฟังก์ชัน remove() นี่จะใช้เวลาที่สำคัญ
  • hash_key:=keymodkey_space
  • ลบคีย์จาก hash_table[hash_key]
• กำหนดฟังก์ชันมี () นี่จะใช้เวลาที่สำคัญ
  • hash_key:=keymodkey_space
  • ส่งคืน (คีย์) ของ hash_table[hash_key]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Bucket:
   def __init__(self):
      self.bucket=[]
   def update(self, key):
      found=False
      for i,k in enumerate(self.bucket):
         if key==k:
            self.bucket[i]=key
            found=True
            break
      if not found:
         self.bucket.append(key)
   def get(self, key):
      for k in self.bucket:
         if k==key:
            return True
      return False
   def remove(self, key):
      for i,k in enumerate(self.bucket):
         if key==k:
            del self.bucket[i]
class MyHashSet:
   def __init__(self):
      self.key_space = 2096
      self.hash_table=[Bucket() for i in range(self.key_space)]
   def add(self, key):
      hash_key=key%self.key_space
      self.hash_table[hash_key].update(key)
   def remove(self, key):
      hash_key=key%self.key_space
      self.hash_table[hash_key].remove(key)
   def contains(self, key):
      hash_key=key%self.key_space
      return self.hash_table[hash_key].get(key)
ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

อินพุต

ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

ผลลัพธ์

True
False
True
False