CoE KKU

กล่าวโดยทั่วไปแล้ว โครงสร้างข้อมูลของ hash table ก็คือ อะเรย์ที่มีขนาดคงที่และมีหน่วยข้อมูล เรียกว่า keys บรรจุอยู่ เช่น หน่วยข้อมูลอาจจะประกอบด้วยสตริง (ซึ่งถูกกำหนดให้ใช้เป็น key) และฟิลด์อื่น ๆ (เช่น ชื่อลูกจ้างที่เป็นส่วนประกอบหนึ่งของโครงสร้างข้อมูลของลูกจ้าง)

เราจะใช้คำแทนขนาดของตารางว่า TableSize ซึ่งกำหนดให้เป็นองค์ประกอบหนึ่งที่อยู่ในโครงสร้างข้อมูลแฮชที่ใช้ ดังนั้นหมายเลขเซลล์ในตารางแฮชเริ่มต้นที่ 0 จนถึง TableSize – 1

แต่ละค่าของ key จะถูก mapped ไปเป็นตัวเลข (หมายเลขเซลล์) ที่อยู่ในช่วง 0 ถึง TableSize – 1 และค่าของ key นั้นก็จะถูกบรรจุลงในเซลล์ตามหมายเลขดังกล่าว

การ mapping กระทำโดยการใช้ฟังก์ชันเรียกว่า hash function ซึ่งตามปกติแล้วhash function ควรจะต้องเป็นฟังก์ชันที่ง่ายในการคำนวณและผลการคำนวณควรจะให้ผลเป็นตำแหน่งเซลล์ที่แตกต่างกันถ้าค่าของ key แตกต่างกัน ซึ่งโดยปกติแล้วเป็นเรื่องที่เป็นไปไม่ได้ ดังนั้น hash function จึงต้องสามารถกระจายการบรรจุค่าของ key ลงในเซลล์ต่าง ๆ ของตารางแฮชได้อย่างสม่ำเสมอกัน รูปที่ 5.1 เป็นตัวอย่างของสถานการณ์สมบูรณ์ของตารางแฮช

ปัญหาที่เหลืออยู่คือ การเลือกฟังก์ชันที่จะใช้ และสิ่งที่ต้องทำเมื่อมี key สองตัวที่ hash ได้ค่าเดียวกัน (เรียกว่าเกิดการชน, collision), และการกำหนดขนาดตารางที่ต้องใช้เป็นตารางแฮช

รูปที่ 5.1 สถานการณ์สมบูรณ์ของตารางแฮช