การตรวจสอบเชิงเส้นในโครงสร้างข้อมูล

ในส่วนนี้ เราจะมาดูกันว่าอะไรคือเทคนิคการตรวจสอบเชิงเส้นในรูปแบบการกำหนดที่อยู่แบบเปิด มีฟังก์ชันแฮชธรรมดา h´(x) :U → {0, 1, . . ., ม. – 1}. ในรูปแบบการกำหนดที่อยู่แบบเปิด ฟังก์ชันแฮชจริง h(x) กำลังใช้ฟังก์ชันแฮชธรรมดา h’(x) และแนบส่วนอื่นด้วยเพื่อสร้างสมการเชิงเส้นหนึ่ง

h´(𝑥) =𝑥 𝑚𝑜𝑑 𝑚

ℎ(𝑥, 𝑖) =(ℎ´(𝑥) + 𝑖)𝑚𝑜𝑑 𝑚

ค่าของ i| =0, 1, . . ., m – 1 เราเริ่มจาก i =0 และเพิ่มจนได้พื้นที่ว่างหนึ่งอัน ดังนั้น ในตอนแรก เมื่อ i =0 ดังนั้น h(x, i) จะเหมือนกับ h´(x)

ตัวอย่าง

สมมติว่าเรามีรายการขนาด 20 (ม. =20) เราต้องการใส่องค์ประกอบบางอย่างในลักษณะการตรวจสอบเชิงเส้น องค์ประกอบคือ {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

ตารางแฮช