เรื่อง ตาราง แฮช (Hash Table)
เมื่อขนาดของเอกภพสัมพัทธ์เพิ่มมากขึ้น ตามหลักการยังคง สามารถทำงานได้ แต่ขนาดของตารางT จะมีผลกระทบทางแก้ปัญหาคือต้องหาวิธีการจับคู่คีย์ให้มีช่วงกว้างที่เล็กลงโดยเรียกวิธีการนี้ว่าฟังก์ชันแฮช (Hash Function)ผลลัพธ์ที่ได้เรียกว่าตารางแฮช (Hash Table)การเข้าถึงข้อมูลโดยตรง กำหนด ให้ k เป็นคีย์ ถูกจัดเก็บอยู่ใน ช่อง k ด้วยการทำแฮชด้วยพื้นฐาน การจัดเก็บในช่องที่ h(k) โดยใช้ฟังก์ชัน h เพื่อคำนวณหาช่องของคีย์โดยการจับคู่กับเอกภพสัมพัทธ์U ในตาราง T
1. กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ o(1)
2. การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ o(1)
ทางปฏิบัติ ใช้เทคนิค ฮิวริสติก (Heuristic) ในการสร้างฟังก์ชันแฮช แนวทางหนึ่งที่ดีคือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่(วิธีการหาร:Division method)ฟังก์ชันแฮช คือการกำหนดค่าคีย์ที่เกิดขึ้นในเอกภพสัมพัทธ์จากตัวเลขธรรมชาติ
1.วิธีการหาร (The Division Method)
2.วิธีการคูณ(The Multiplication Method)
3.วิธีทั่วไป (Universal hashing)
เทคนิคลำดับของการตรวจสอบ
1. การตรวจสอบเชิงเส้น (Linear Probing)
2.การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)
3. การสร้างฟังก์ชันแฮชแบบสองเท่า(Double Hashing)
1.การตรวจสอบเชิงเส้น (Linear Probing)รูปแบบของ ฟังก์ชันคือh(k, i) = (h` (k) + i) mod mเมื่อ i = 0, 1, 2, . . . , m-1h` คือ auxiliary ของฟังก์ชันแฮช
2. การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)
รูปแบบของ ฟังก์ชันคือh(k, i) = (h` (k) + c1i + c2i2) mod mเมื่อ i = 0, 1, 2, . . . , m-1h` คือ auxiliary ของฟังก์ชันแฮชc1 + c2 ≠ 0 เป็นค่าคงที่แบบ auxiliary
3. การสร้างฟังก์ชันแฮชแบบสองเท่า (Double Hashing)รูปแบบของ ฟังก์ชันคือ
h(k, i) = (h1, 9k) + ih2 (k)) mod mเมื่อ h1 และ h2 เป็น auxiliary ของฟังก์ชันค่า k เป็นค่าเริ่มต้นของ ตำแหน่งการตรวจสอบ และค่าoffset
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น