เรื่อง ตารางแฮช (Hash Table)
ตารางข้อมูลแบบตรง
สมมติว่ามีการกำหนดให้คีย์มาจากเอกภพสัมพัทธ์U={0,1.....,m-1}
การแก้ไขปัญหาคือใช้ตาราง T[0...m-1]การสร้างดัชนีโดยคีย์เพื่อใช้ในการเชื่อมโยงข้อมูล เข้าด้วยกันเพื่อเก็บข้อมูลตำแหน่งที่ถูกต้อง
การชนกันของข้อมูล (Collision)
การแทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกัน
ทางปฏิบัติใช้เทคนิค ฮิวริสติก ในการสร้างฟังก์ชั่นแฮซ แนวทางหนึ่งที่ดีคือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่
ฟังก์ชั่นแฮช คือ การกำหนอกค่าคีย์ที่เกิดขึ้นในเอกภพสัมพัทธจากตัวเลขธรรมชาติ
วิธีการสร้างฟังก์ชั่นแฮช
1.วิธีการหาร
2.วิธีการคูณ
3.วิธีทั่วไป
เทคนิคลำดับของการตรวจสอบ
1. การตรวจสอบเชิงเส็น
2.การตรวจสอบด้วยสมการกำลังสอง
3.การสร้างฟังก์ชั่นแฮชแบบสองเท่า
วันจันทร์ที่ 21 กันยายน พ.ศ. 2552
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
ไม่อนุญาตให้มีความคิดเห็นใหม่