คำจำกัดความ
การแฮชที่สมบูรณ์แบบแบบไดนามิกถูกกำหนดให้เป็นวิธีการเขียนโปรแกรมสำหรับแก้ไขการชนกันในโครงสร้างข้อมูลตารางแฮช
ใบสมัคร
ในขณะที่ใช้หน่วยความจำมากกว่าคู่กันของตารางแฮช วิธีนี้เหมาะอย่างยิ่งสำหรับสถานการณ์ที่ต้องดำเนินการสืบค้น การแทรก และการลบอย่างรวดเร็วบนชุดองค์ประกอบขนาดใหญ่
การนำไปใช้
ดีทซ์เฟลบิงเงอร์ et al. อธิบายอัลกอริธึมพจนานุกรมแบบไดนามิกที่เมื่อชุดของรายการ m ถูกผนวกเข้ากับพจนานุกรมแบบค่อยเป็นค่อยไป การสืบค้นข้อมูลสมาชิกจะใช้เวลาคงที่เสมอ ดังนั้น O(1) กรณีที่เลวร้ายที่สุด พื้นที่เก็บข้อมูลทั้งหมดที่ต้องการคือ O(m) (เชิงเส้น) และ O(1) คาดว่าเวลาการแทรกและการลบค่าตัดจำหน่ายที่คาดหวัง (เวลาคงที่ค่าตัดจำหน่าย) ในกรณีไดนามิก เมื่อคีย์ถูกแทรกลงในตารางแฮช ถ้ารายการในตารางย่อยถูกครอบครอง การชนกันจะเกิดขึ้นและ ตารางย่อยถูกสร้างขึ้นใหม่ตามจำนวนรายการทั้งหมดใหม่และฟังก์ชันแฮชที่เลือกแบบสุ่ม เนื่องจากปัจจัยด้านภาระของตารางระดับที่สองยังคงต่ำ การสร้างใหม่จึงไม่บ่อย และต้นทุนการแทรกที่คาดหมายที่คาดว่าจะตัดจำหน่ายและต้นทุนการลบที่คาดหมายคาดว่าจะเป็น O(1)
นอกจากนี้ ขนาดสูงสุดของตารางระดับบนสุดหรือตารางย่อยใดๆ ไม่มีความรู้ล่วงหน้าในกรณีแบบไดนามิก เทคนิคหนึ่งในการรักษาพื้นที่ O(m) ที่คาดไว้ของตารางคือการกระตุ้นให้มีการสร้างใหม่ทั้งหมดเมื่อพบการแทรกและการลบในจำนวนที่เพียงพอ ตราบใดที่จำนวนการแทรกหรือการลบทั้งหมดเกินจำนวนองค์ประกอบในขณะที่สร้างครั้งสุดท้าย ต้นทุนที่คาดว่าจะตัดจำหน่ายของการแทรกและการลบยังคงเป็น O(1) โดยการพิจารณาการแฮชใหม่ทั้งหมด
