- ตารางการเข้าถึงข้อมูลแบบตรง
- ตารางแฮช
- การชนกันของข้อมูล
- การแก้ปัญหาการชนกันของข้อมูล
- วิธีการสร้างฟังก์ชันแฮช
จุดประสงค์การเรียนรู้
1. เพื่อให้นักศึกษาทราบถึงวิธีการเข้าถึงข้อมูลแบบตรง
2. เพื่อให้นักศึกษาทราบวิธีการสร้างฟังก์ชันแฮช
3. เพื่อให้นักศึกษาทราบวิธีการตรวจสอบข้อมูล
4. เพื่อให้นักศึกษาสามารถแก้ไขปัญหาการชนกันของข้อมูล
5. เพื่อให้นักศึกษาทราบวิธีการชนกันของข้อมูล
ตารางข้อมูลแบบตรง (Direct-address table)
สมมติว่ามีการกำหนดให้คีย์มาจากเอกภพสัมพัทธ์ U = {0,1,…,m-1} การแก้ไขปัญหาคือใช้ตาราง T[0..m-1] การสร้างดัชนีโดยคีย์ เพื่อใช้ในการ เชื่อมโยงข้อมูล เข้าด้วยกันเพื่อเก็บข้อมูลเข้าในตำแหน่งที่ถูกต้อง
เมื่อขนาดของเอกภพสัมพัทธ์เพิ่มมากขึ้น ตามหลักการยังคง สามารถทำงานได้ แต่ขนาดของตาราง T จะมีผลกระทบทางแก้ปัญหาคือต้องหาวิธีการจับคู่คีย์ให้มีช่วงกว้างที่เล็กลงโดยเรียกวิธีการนี้ว่า
ฟังก์ชันแฮช (Hash Function)
ผลลัพธ์ที่ได้เรียกว่า
ตารางแฮช (Hash Table)
การเข้าถึงข้อมูลโดยตรง กำหนด ให้ k เป็นคีย์ ถูกจัดเก็บอยู่ใน ช่อง k ด้วยการทำแฮชด้วยพื้นฐาน การจัดเก็บในช่องที่ h(k) โดย
ใช้ฟังก์ชัน h เพื่อคำนวณหาช่องของคีย์โดยการจับคู่กับเอกภพสัมพัทธ์U ในตาราง T
h: U {0,1,…,m-1}
ฟังก์ชัน แฮช จะทำงานแบบสุ่ม ตัวอย่างเช่น h(k) = k mod m เมื่อ m เป็นค่าหลัก (prime number) จำนวนช่อง (Slot)
แนวคิดการจัดเก็บ ค่าคีย์ของ k ในตำแหน่ง ที่ T[h(k)] เมื่อ k ∈ U , h(k) ∈ [0..m-1] แนวคิดหลัก คือ ลด ขนาดอะเรย์ของดัชนีการที่แทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกันอย่างไรก็ตามการเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง
จากรูป ฟังก์ชัน h การจับคู่ระหว่าง k กับ j ในช่องทางเดียวกันซึ่ง อาจจะชนกันสามารถแบ่งวิธีการในการรองรับการชนกันของ
ตารางแฮชคือการทำแบ่งห่วงโซ่ (Chaining) แบบการเปิดที่อยู่ (Open Addressing)
การแก้ไขปัญหาชนกันของข้อมูล แบบห่วงโซ่(Chaining)
1. กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ o(1)
2. การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ o(1)
ทางปฏิบัติ ใช้เทคนิค ฮิวริสติก (Heuristic) ในการสร้างฟังก์ชันแฮช แนวทางหนึ่งที่ดีคือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่ (วิธีการหาร:Division method) ฟังก์ชันแฮช คือการกำหนดค่าคีย์ที่เกิดขึ้นในเอกภพสัมพัทธ์จากตัวเลขธรรมชาติ
วิธีการสร้างฟังก์ชันแฮช (Method for Creating Function)
1.วิธีการหาร (The Division Method)
2.วิธีการคูณ(The Multiplication Method)
3.วิธีทั่วไป (Universal hashing)
วิธีการหาร (The Division Method)
Open Addressing
ฟังก์ชันแฮช คือ
h: ν{0, 1, . . . m -1 }--> {0, 1, . . . , m-1}
ลำดับในการตรวจสอบ(probe sequence) คือ
<>
เทคนิคลำดับของการตรวจสอบ
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-1
h` คือ auxiliary ของฟังก์ชันแฮช
2. การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)รูปแบบของ ฟังก์ชันคือ
h(k, i) = (h` (k) + c1i + c2i2) mod m เมื่อ i = 0, 1, 2, . . . , m-1
h` คือ auxiliary ของฟังก์ชันแฮช c1 + c2 ≠ 0 เป็นค่าคงที่แบบ auxiliary
3. การสร้างฟังก์ชันแฮชแบบสองเท่า (Double Hashing)รูปแบบของ ฟังก์ชันคือ
h(k, i) = (h1, 9k) + ih2 (k)) mod m เมื่อ h1 และ h2 เป็น auxiliary ของฟังก์ชัน
ค่า k เป็นค่าเริ่มต้นของ ตำแหน่งการตรวจสอบ และค่า offset
แบบฝึกหัด
1.จงจัดชุดข้อมูลลงในตาราง Hash Table 13,25,63,69,45,78,59,17ขนาด 9 ช่อง โดยการแก้ปัญหาการชนกัน ใน
ลักษณะแบบเชน
2. จงอธิบายวิธีการแก้ไขปัญหาการชนกันของข้อมูล
3. วิธีในการสร้าง Hash Function มีวิธีใดบ้าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น