home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

Static Perfect Hashing (การแฮชสมบูรณ์แบบคงที่) ในโครงสร้างข้อมูล

Perfect Hashing คืออะไร?

Perfect Hashing = Hashing Model ที่ Set ของ n Elements เก็บใน Hash Table ขนาด n ได้ และ Lookup ใน Constant Time

Fredman, Komlós, Szemerédi (1984) → Nickname: FKS Hashing

Static Hashing

Static Hashing = Lookup บน Finalized Dictionary Set (Objects Final, ไม่เปลี่ยนแปลง)

Applications

Limited เพราะ Database/Objects/References ต้องคงที่
Eligible: Databases ที่เปลี่ยนแปลงน้อย (Rehash ทั้ง DB ครั้งคราว)
Examples: Word/Dictionary Sets, Organization Personnel Data, Fixed Reference Data

Implementation (FKS Scheme)

  1. Given: Set of p Entries, Unique Keys (Known Ahead of Time)
  2. First-level Hash Table: Size s = 2(p-1) Buckets
  3. Top-level Hash Function → Separate p Entries → q Buckets (q = 2(p-1))
  4. แต่ละ Bucket ที่มี r Entries: Allocate Second-level Table = r² Slots
  5. Second-level Hash Function: Choose Randomly from Universal Hash Family → Collision-Free
  6. ถ้า Collide → Choose New Random Hash Function จน Collision-Free
  7. Hash r Entries ลง Second-level Table

Space Analysis

Expected Total Size = O(p) (Linear)
Second-level Tables Size = r² แต่ Expected Σ r² = O(p) (เนื่องจาก Universal Hashing)

สรุป

Static Perfect Hashing (FKS) = O(1) Worst-case Lookup, O(n) Space, Static Data Only
Two-Level Scheme: First-level Distribute, Second-level Perfect Hash per Bucket