ตารางแฮช (Hash Table)
ตารางข้อมูลแบบตรง (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] แนวคิดหลัก คือ ลด ขนาดอะเรย์ของดัชนีการที่แทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกันอย่างไรก็ตามการเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง
การแก้ไขปัญหาชนกันของข้อมูล แบบห่วงโซ่(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-1h`คือ auxiliary ของฟังก์ชันแฮช c1 + c2 ≠ 0 เป็นค่าคงที่แบบ auxiliary
3. การสร้างฟังก์ชันแฮชแบบสองเท่า (Double Hashing)รูปแบบของ ฟังก์ชันคือh(k, i) = (h1, 9k) + ih2 (k)) mod m เมื่อ h1 และ h2 เป็น auxiliary ของฟังก์ชันค่า k เป็นค่าเริ่มต้นของ ตำแหน่งการตรวจสอบ และค่า offset
ไม่มีความคิดเห็น:
แสดงความคิดเห็น