DTS10-15/09/2009

เรื่องตารางแฮช
คือการเข้าถึงข้อมูลโดยตรง กำหนดให้ k เป็นคีย์ถูกจัดเก็บอยู่ใน ช่อง k ด้วยการทำแฮช ด้วยพื้นฐานการจัดเก็บในช่องที่h(k) โดยฟังก์ชั่น h เพื่อคำนวณหาช่องของคีย์โดยการจับคู่กับดอกภพสัมพันธ์ U ในตาราง T

การชนกับของข้อมูล
การแทรกในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ถูกสร้างจากฟังก์ชั้น อย่างไรก็ตามการเกิดการชนกันยังคงมีอย่างน้อย 1 ครั้ง

วิธีการสร้างฟังก์ชั่นแฮช
1. วิธีการหาร คือ การจับคู่คีย์ K ในช่องของ m โดยนำเศษที่เหลือของ k จากการหารด้วย m ด้วยฟังก์ชั่นคือ h(k) = mod m.
2. วิธีการคูณ ปรกอบด้วย 2 ขั้นตอน
ขั้นที่ 1 คูณด้วย k ด้วยค่าคงที่ h(k) = *m(kA mod 1)
เมื่อ " kA mod 1" หมายถึง เศษส่วนของ kA, นั้นคือ , kA-*kA
ประโยชน์ของวิธีนี้คือ ค่าของm จะไม่วิกฤติ และสามารถดำเนินการในครื่องคอมพิวเตอร์ส่วนมากได้
3. วิธีทั่วไป คือ Open Addressing ฟังก์ชั่นแฮช คือ h:V{0,1,.....m-1}-->{0,1,...,m-1}

เทคนิคลำดับของการตรวจสอบ
1. การตรวจสอบเชิงเสน
2. การตรวจสอบด้วยสมการกำลังสอง
3. การสร้างฟังก์ชั่นแฮชแบบสองท่า