สรุปเรื่องตารางแฮช(Hash Table)
ฟังก์ชัน แฮช จะทำงานแบบสุ่มตัวอย่างเช่น h(k) = k mod m เมื่อ m เป็นค่าหลัก(prime number)
จำนวนช่อง(Slot) แนวคิดการจัดเก็บค่าคีย์ของ k ในตำแหน่งที่ T[h(k)]
การชนกันของข้อมูล(Collision) การที่แทรกคีย์เข้าไปในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกันอย่างไรก็ตามการเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง
การแก้ปัญหาชนกันของข้อมูลแบบห่วงโซ่(Chaining)
1. กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ0(1)
2. การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ0(1)
ฟังก์ชันแฮช คือ การกำหนดค่าคีย์ที่เกิดขึ้นในเอกภพสัมพัทธ์จากตัวเลขธรรมชาติ
วิธีการสร้างฟังก์ชันแฮช(Method for Creating Function)
1.วิธีการหาร (The Division Method)
2. วิธีการคูณ(The Multiplication Method)
3. วิธีทั่วไป(Universal hashing)
เทคนิคลำดับของการตรวจสอบ
1.การตรวจสอบเชิงเส้น(Linear Probing)
2.การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)
3.การสร้างฟังก์ชันแฮชแบบสองเท่า(Double Hashing)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น