ฟังก์ชันแฮชแบบหาร
ใช้ฟังก์ชันแฮช:
h(x) = x mod m
การจัดเก็บด้วย Chaining
ดูแลรักษาอาร์เรย์ A[0, ..., m-1] โดยแต่ละองค์ประกอบเป็นตัวชี้ไปยังหัวของ Linked List ลิสต์ Li ที่ชี้โดย A[i] จะเก็บองค์ประกอบ x ทั้งหมดที่ h(x) = i เทคนิคนี้เรียกว่า "Hashing by Chaining"
การดำเนินการ
- Insert: คำนวณ i = h(x) แล้วเพิ่ม x เข้าไปในลิสต์ Li (O(1))
- Search/Delete: หา i = h(x) แล้วเดินทางในลิสต์ Li จนพบค่าที่ต้องการหรือลิสต์หมด ใช้เวลาสัมพันธ์กับขนาดลิสต์ Li
กรณีแย่ที่สุดและการหลีกเลี่ยง
ถ้าเซต S มีค่า 0, m, 2m, 3m... nm ทุกค่าจะเก็บใน L0 ใช้เวลา Linear ในการค้นหา/ลบ แต่กรณีนี้เกิดขึ้นน้อยมาก
ถ้า S แจกแจงแบบ Uniform และ Independent ใน Universal Set U และ u เป็นพหุคูณของ m ขนาดคาดหมายของแต่ละลิสต์ Li คือ n/m การค้นหาและลบใช้เวลา O(1 + α)
คำแนะนำ: หลีกเลี่ยง m เป็นกำลังของ 2 ควรเลือก m เป็นจำนวนเฉพาะ (Prime) ที่ไม่ใกล้เคียงกับกำลังของ 2
