In computer systems engineering, Arrays and Hash Maps represent the foundational building blocks of databases, compilers, caching layers, and operating system kernels.
1. Contiguous Arrays & CPU Cache Locality#
An array is a linear data structure storing elements of identical size in contiguous physical memory addresses:
\text{Physical Address}(A[i]) = \text{Base Address} + (i \times \text{Size of Element})
Because calculating this address requires only one multiplication and one addition instruction, any element in an array can be read or modified in $O(1)$ constant time.
Modern CPUs do not fetch single bytes from main RAM; they fetch memory in 64-byte Cache Lines. When you iterate sequentially through an array, reading A[0] automatically loads the adjacent elements into L1/L2 cache, resulting in lightning-fast cache hits.
2. Hash Maps: The Mathematics of $O(1)$ Lookups#
A Hash Map maps keys of arbitrary types to values by passing keys through a hash function:
\text{index} = \text{hash}(key) \pmod{\text{array\_capacity}}
By the Pigeonhole Principle, if the domain of possible keys is larger than the number of available buckets, two distinct keys will eventually produce identical hash indices (k_1 \neq k_2 but \text{hash}(k_1) = \text{hash}(k_2)).
3. Collision Resolution: Separate Chaining vs Open Addressing#
- Separate Chaining: Each array bucket holds a pointer to the head of a linked list or balanced tree. When collisions occur, the new key-value pair is appended to the chain.
- Open Addressing: All elements are stored directly within the primary array. If a bucket is occupied, the algorithm searches for an alternative slot using linear or quadratic probing.