Definition
Dynamic Perfect Hashing = Programming Method สำหรับ Resolve Collisions ใน Hash Table Data Structure
Application
Memory-Intensive กว่า Hash Table ทั่วไป แต่เหมาะสำหรับ: Fast Queries, Insertions, Deletions บน Large Element Sets
Implementation (Dietzfelbinger et al.)
Dynamic Dictionary Algorithm:
- Membership Queries: O(1) Worst-case Time เสมอ
- Total Storage: O(m) Linear (m = Items)
- Expected Amortized Insert/Delete: O(1)
Mechanism
- Top-level Hash Table: Buckets
- แต่ละ Bucket = Second-level Hash Table
- Insert Key: Hash → Bucket → Insert ใน Sub-table
- Collision ใน Sub-table → Rebuild Sub-table (New Size + Random Hash Function)
- Low Load Factor ของ Second-level → Rebuild ไม่บ่อย → Amortized O(1)
Dynamic Sizing
Ultimate Size ของ Top-level/Sub-tables ไม่รู้ล่วงหน้า
Technique: Full Rebuild เมื่อ Insertions/Deletions เกิน Threshold (เช่น > Elements ตอน Last Build)
Amortized Expected Cost Insert/Delete ยังคง O(1) รวม Full Rehashing
สรุป
Dynamic Perfect Hashing = O(1) Worst-case Query + O(1) Amortized Update
