Data Structures

When to use

• Choosing the right data structure before writing a collection or lookup mechanism
• Implementing custom hash tables, trees, or heaps with specific performance requirements
• Selecting between approximate data structures (Bloom filter, HyperLogLog, Count-Min Sketch)
• Optimizing range queries or prefix operations on arrays
• Implementing dynamic connectivity or equivalence class tracking
• Moving from in-memory to disk-based storage structures

Core principles

1. Access pattern first — select for how the structure is queried, not what is most familiar
2. Load factor controls hash table performance — keep below 0.75 for open addressing
3. B-trees exist because disks exist — in-memory trees should not use disk-page logic
4. Segment tree when updates + queries interleave; Fenwick tree for prefix-only — do not overengineer
5. Union-Find is underused — path compression + union by rank gives near-O(1) for connectivity