การแฮชด้วยการโยงในโครงสร้างข้อมูล

ในส่วนนี้เราจะมาดูกันว่า hashing กับ chaining คืออะไร Chaining เป็นเทคนิคการแก้ปัญหาการชนกันอย่างหนึ่ง เราไม่สามารถหลีกเลี่ยงการชนกัน แต่เราสามารถพยายามลดการชนกัน และพยายามเก็บองค์ประกอบหลายรายการสำหรับค่าแฮชเดียวกัน

เทคนิคนี้สมมติว่าฟังก์ชันแฮชของเรา h(x) มีตั้งแต่ 0 ถึง 6 ดังนั้นสำหรับองค์ประกอบมากกว่า 7 รายการ จะต้องมีองค์ประกอบบางอย่างที่จะอยู่ภายในห้องเดียวกัน เพื่อที่เราจะสร้างรายการเพื่อจัดเก็บตามนั้น ในแต่ละครั้งเราจะเพิ่มที่จุดเริ่มต้นของรายการเพื่อทำการแทรกใน O(1) ครั้ง

ให้เราดูตัวอย่างต่อไปนี้เพื่อรับแนวคิดที่ดีขึ้น ถ้าเรามีองค์ประกอบบางอย่างเช่น {15, 47, 23, 34, 85, 97, 65, 89, 70} และฟังก์ชันแฮชของเราคือ h(x) =x mod 7

ค่าแฮชจะเป็น

Hashing กับ chaining จะเป็นเช่น −