direct-array-access

Direct array access is memory access via base-pointer-plus-offset addressing with no indirection, hashing, or collision resolution. Given a contiguous array and a valid index, the hardware computes the address in a single instruction: address = base + index * element_size. This is the fastest possible random-access lookup.

When you write freq[3], the CPU computes address_of_freq + 3 * sizeof(int) and fetches the value. No hash function computation, no bucket traversal, no collision chains to follow. For character frequency problems with a small known domain, this makes arrays strictly faster than hash maps despite both being theoretically O(1).

1. The array is allocated as a contiguous block of memory
2. The compiler knows the base address and element size
3. At runtime, freq[i] compiles to a single MOV instruction with scaled index addressing
4. The memory access is predictable — adjacent elements are in adjacent memory locations (spatial locality)
5. No branching, no function calls, no hash computation

• True hardware-level O(1) — single CPU instruction
• No hashing, no collisions, no amortization, no worst-case degradation
• Perfect spatial locality — sequential access is cache-friendly
• Indices must be valid (0 to size-1) — no bounds checking by default in C++
• Works only for contiguous, densely populated index ranges

• Built from: Character-to-Index Mapping — direct access requires valid indices via conversion
• Builds into: Frequency Array — direct access is the fundamental advantage of arrays
• Builds into: Memory Efficiency of Array — minimal overhead per slot enables cache efficiency
• Contrasts with: Hash Collision Overhead — hash maps trade direct access for flexibility
• Related: Known Range Assumption — direct access requires known, bounded ranges

• Out-of-bounds access leads to undefined behavior (silent memory corruption)
• C++ does not bounds-check array accesses — use std::array or at() for safety
• For negative indices (from incorrect ch - 'a' on uppercase), the behavior is undefined
• Cache misses can still occur for very large arrays (but for freq[26], the entire array fits in a single cache line)
• Direct access assumes contiguous allocation — vectors also provide this, but with heap allocation overhead