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

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

มีสามวิธีที่นิยมใช้กันสำหรับเทคนิคการระบุที่อยู่แบบเปิด วิธีการเหล่านี้คือ −

• การตรวจวัดเชิงเส้น

• การตรวจสอบกำลังสอง

• ดับเบิ้ลแฮชชิ่ง

ในเทคนิคนี้ เราใช้ฟังก์ชันแฮชเหมือนกับเทคนิคแฮชอื่นๆ หากสถานที่นั้นว่าง ให้แทรกองค์ประกอบนั้นลงในตำแหน่งนั้น ตอนนี้ถ้าสถานที่นั้นไม่ว่าง เราจะหาองค์ประกอบอิสระอื่นโดยใช้สมการ สำหรับการตรวจวัดเชิงเส้น เราจะใช้สมการเชิงเส้นบางส่วน สำหรับการตรวจสอบแบบกำลังสอง เราจะใช้สมการกำลังสองบางส่วน

ในการแฮชสองครั้ง เมื่อเกิดการชนกัน เราจะใช้ฟังก์ชันแฮชอื่น แล้วใส่ลงในตำแหน่งนั้น ฟังก์ชันแฮชนั้นเรียกว่าฟังก์ชันแฮชรอง ที่จะไม่ใช้โดยตรงถ้าไม่มีการชนกัน