Skip to content

Instantly share code, notes, and snippets.

@Hydra9268

Hydra9268/hash_block_vs_perfect_hash_table_2.md

Last active November 18, 2024 07:36
Show Gist options
  • Save Hydra9268/dde04a1f9c9e8287e8be3770f33ac0b9 to your computer and use it in GitHub Desktop.
Save Hydra9268/dde04a1f9c9e8287e8be3770f33ac0b9 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
hash_block_vs_perfect_hash_table_2.md
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). Poor (allocates all possible slots).
Collision Handling Handled via linked lists (efficient for few collisions). None, since each key is unique.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment