| Aspect | Hash Block | Perfect Hash Table |
|---|---|---|
| Memory Usage | ~40 KB (with ~100 street names stored) | ~143 KB (preallocated, including names). |
| Scalability | Efficient for sparse data; scales dynamically. | Preallocates all slots, wasteful for sparse data. |
| Lookup Time | O(1) (array indexing). | O(1) (direct indexing). |
| Insertion Time | O(1) for most cases, O(k) if collisions. | O(1) (no collisions by design). |
| Suitability for Sparse Datasets | Excellent (only allocates necessary slots). |
Hydra9268
Hydra9268
/ hash_block_vs_perfect_hash_table_2.md
Last active
November 18, 2024 07:36
Hydra9268
/ hash_block_vs_perfect_hash_table_1.md
Last active
November 18, 2024 07:33
| Aspect | Hash Block | Perfect Hash Table |
|---|---|---|
| Memory Usage (Slots) | ~39,520 bytes (worst case) | 140,608 bytes (fixed) |
| Memory Efficiency | Scales with usage (lazy init) | Preallocates all slots upfront |
| Lookup Time | O(1) (array-based indexing) | O(1) |
| Scalability | Adapts to actual usage | Fixed size for predefined keys |
| Collisions | Handles with linked lists | None |
Hydra9268
/ perfect-hash-table.md
Last active
November 18, 2024 06:05
Using Two-Letter Keys (e.g., AA, AB, AC) |
Three-Letter Keys (e.g., AAA, AAB, AAC) |
|---|---|
A hash table for two-letter keys could use a hash function like: hash(key) = 26 × index_of(first_letter) + index_of(second_letter) For AA, AB, AC: - AA → 26 × 0 + 0 = 0 - AB → 26 × 0 + 1 = 1 - AC → 26 × 0 + 2 = 2 This maps each two-letter key to a unique slot in a table with size 26 × 26 = 676 spaces. |
A hash table for three-letter keys might extend this idea: `hash(key) = 26² × index_of(first_letter) + 26 × in |