การจัดการ Overflow ในโครงสร้างข้อมูล Hash Table

Overflow คืออะไร?

Overflow ใน Hash Table เกิดขึ้นเมื่อ Home Bucket (บัคเก็ตหลัก) ของคู่ (Key, Element) ใหม่เต็มแล้ว ไม่สามารถจัดเก็บเพิ่มได้

วิธีจัดการ Overflow 2 แบบหลัก

1. Open Addressing (การกำหนดที่อยู่เปิด) - ค้นหาที่ว่างในตาราง

พยายามหา Bucket ว่างใน Hash Table เอง โดยวิธีต่างๆ:

• Linear Probing: ตรวจสอบช่องถัดไปเรื่อยๆ (h(k) + i) mod m
• Quadratic Probing: ใช้ฟังก์ชันกำลังสอง (h(k) + i²) mod m
• Random Probing: ใช้ลำดับสุ่มที่กำหนดไว้ล่วงหน้า

Linear Probing - รายละเอียด

วางข้อมูลในช่องว่างถัดไปเมื่อเกิด Collision

• Worst-case: Θ(m) โดย m = จำนวนคู่ในตาราง (เกิดเมื่อทุกคู่อยู่ใน Cluster เดียวกัน)
• ปัญหา: Primary Clustering - ข้อมูลรวมกันเป็นกลุ่มใหญ่ ทำให้ค้นหาช้าลง

Quadratic Probing

ใช้ Increment แบบกำลังสอง: ตรวจสอบ H(x), (H(x)+i²)%b, (H(x)-i²)%b สำหรับ 1 ≤ i ≤ (b-1)/2
b = จำนวนเฉพาะรูปแบบ 4j+3 (j เป็นจำนวนเต็ม) เพื่อให้ครอบคลุมทุกช่อง

Random Probing

H(x) := (H'(x) + S[i]) % b
S[i] = ตารางขนาด b-1 ที่เป็น Random Permutation ของ [1, b-1]

2. Chaining (การเชื่อมโยง) - ยอมให้ Bucket เก็บหลายค่า

แต่ละ Bucket เก็บ Linked List (หรือ Array) ของคู่ทั้งหมดที่ Hash มายัง Bucket นั้น

• Array Linear List: ใช้ Array ในแต่ละ Bucket
• Chain (Linked List): ใช้ Linked List ในแต่ละ Bucket (ยืดหยุ่นกว่า)

สรุปการเลือกใช้