การจัดการน้ำล้นในโครงสร้างข้อมูล

โอเวอร์โฟลว์เกิดขึ้นในเวลาที่บัคเก็ตหลักสำหรับคู่ใหม่ (คีย์, องค์ประกอบ) เต็ม

เราอาจจัดการกับน้ำล้นโดย

ค้นหาตารางแฮชอย่างเป็นระบบสำหรับถังที่ยังไม่เต็ม

ขจัดส่วนเกินโดยอนุญาตให้แต่ละที่เก็บข้อมูลเก็บรายการของคู่ทั้งหมดที่เป็นที่เก็บข้อมูลหลัก

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

การตรวจสอบเชิงเส้นจะดำเนินการเพื่อแก้ไขการชนกันโดยการวางข้อมูลลงในช่องที่เปิดถัดไปในตาราง

ประสิทธิภาพของการตรวจวัดเชิงเส้น

การค้นหาแบบเส้นตรง (H(x)+i2)%b; H(x) หมายถึงฟังก์ชันแฮชของ x

การตรวจสอบกำลังสองใช้ฟังก์ชันกำลังสองของ i เป็นการเพิ่มขึ้น

ตรวจสอบถัง H(x), (H(x)+i2)%b, (H(x)-i2)%b สำหรับ 1<=i<=(b-1)/2

b ถูกระบุเป็นจำนวนเฉพาะของรูปแบบ 4j+3, j เป็นจำนวนเต็ม

Random Probing ดำเนินการร่วมกับตัวเลขสุ่ม

H(x):= (H’(x) + S[i]) % b
S[i] is a table along with size b-1
S[i] is indicated as a random permutation of integers [1, b-1].