Hashing by Open Addressing
Open Addressing เป็นเทคนิคแก้ไข Collision อีกวิธีหนึ่ง ต่างจาก Chaining ที่ไม่ได้แทรกข้อมูลในโครงสร้างอื่น แต่วางข้อมูลใน Hash Table เอง ขนาด Hash Table ต้องใหญ่กว่าจำนวน Keys
3 วิธียอดนิยม
- Linear Probing
- Quadratic Probing
- Double Hashing
หลักการทำงาน
ใช้ Hash Function ปกติ ถ้าที่ว่าง ใส่เลย ถ้าไม่ว่าง หาที่ว่างอีกแห่งด้วยสมการ:
- Linear Probing: สมการเชิงเส้น
- Quadratic Probing: สมการกำลังสอง
- Double Hashing: ใช้ Hash Function ตัวที่ 2 (Secondary Hash Function) เมื่อชนกัน เท่านั้น
