Arrays, Hash Maps & Hash Collision Resolution

Data structures are the foundational building blocks of computation. Every database index, web framework cache, and distributed hash table relies on the fundamental memory layouts of Arrays and Hash Maps.

In this guide, we evaluate contiguous memory allocation mathematics, analyze dynamic array geometric resizing, dissect hash table collision resolution strategies (Separate Chaining vs. Open Addressing with Robin Hood hashing), and evaluate Big-O asymptotic bounds.

Contiguous Memory Arrays & O(1) Indexing Mathematics#

An array is a collection of elements stored in contiguous, sequentially aligned memory addresses. Because memory is contiguous, accessing any element by its integer index i takes deterministic O(1) Constant Time:

Memory: [ Index 0 ] [ Index 1 ] [ Index 2 ] [ Index 3 ] [ Index 4 ]
Addr:    0x1000      0x1008      0x1010      0x1018      0x1020

The Memory Addressing Formula#

The CPU calculates the physical memory address of element A[i] using hardware arithmetic in a single clock cycle:

Physical Address(A[i]) = Base_Address + (i × Element_Size_in_Bytes)

Numerical Example:

• Array base address: Base = 0x1000 (4096 in decimal).
• Data type: 64-bit integer (Element_Size = 8 bytes).
• Address of index i = 5:

Physical Address(A[5]) = 4096 + (5 × 8) = 4096 + 40 = 4136 (hexadecimal: 0x1028).

Because the formula involves only one multiplication and one addition, the CPU calculates the memory location in O(1) time without traversing intermediate elements!

Dynamic Arrays & Geometric Resizing#

Static arrays (like in C) have a fixed capacity determined at allocation. Dynamic arrays (Python's list, C++ std::vector, Java's ArrayList) expand dynamically as elements are appended:

1. When the array is full (size == capacity), the system allocates a new, larger memory block.
2. It copies all N existing elements to the new block.
3. It frees the old memory block and points the array to the new memory address.

Why Geometric Growth Matters:

If capacity increased linearly (+1 element on each resize), appending N elements would take 1 + 2 + 3 + ... + N = O(N^2) time.

By expanding geometrically (multiplying capacity by a factor of 1.5× or 2.0×), resizing occurs infrequently.

Amortized Analysis Proof:

• Appending N elements requires N standard writes: O(N) cost.
• Resizing costs: 1 + 2 + 4 + 8 + ... + N/2 + N < 2·N operations.
• Total operations for N appends = N + 2·N = 3·N.
• Average amortized cost per append: 3·N / N = 3 = O(1) Amortized Time!

Hash Maps: From Keys to Array Buckets#

A Hash Map achieves average-case O(1) search, insert, and delete performance by mapping arbitrary keys (strings, objects) to array indices using a Hash Function:

Key ("user_123") ----[ Hash Function ]----> 64-bit Hash Integer ----[ Modulo Capacity ]----> Bucket Index

Bucket_Index = Hash(Key) mod Array_Capacity

A robust cryptographic or non-cryptographic hash function (like MurmurHash3, CityHash, or SipHash) satisfies two properties:

1. Uniformity: Distributes keys evenly across all array buckets.
2. Determinism: The same key must always yield the exact same bucket index.

Hash Collision Resolution Strategies#

By the Pigeonhole Principle, if you hash more keys than available buckets (or due to birthday paradox probability), two distinct keys will eventually produce identical bucket indices:

Key_1 != Key_2   but   Hash(Key_1) mod Capacity == Hash(Key_2) mod Capacity

1. Separate Chaining (Linked Lists / Red-Black Trees)#

Each bucket in the array stores a pointer to a linked list of key-value pairs:

• When a collision occurs, the new entry is appended to the linked list at that bucket index.
• Lookup: Calculate bucket index, then traverse the linked list comparing keys using equality (==).
• Java 8 Optimization: When a bucket's linked list exceeds 8 elements, Java converts the linked list into a balanced Red-Black Tree, improving worst-case search from O(N) to O(log N)!

Bucket 0:  [ Key: "alice", Val: 42 ] ---> [ Key: "charlie", Val: 19 ]
Bucket 1:  [ Empty ]
Bucket 2:  [ Key: "bob", Val: 99 ]

2. Open Addressing (Linear Probing & Robin Hood Hashing)#

All key-value pairs are stored directly in the primary array table without linked lists:

• When a collision occurs at index i, the algorithm searches alternative indices using a probing sequence:

- Linear Probing: index = (base + step) mod Capacity

- Quadratic Probing: index = (base + step^2) mod Capacity

- Double Hashing: index = (base + step × Hash_2(Key)) mod Capacity

Robin Hood Hashing (Python's Modern Compact Dict):

When inserting a key, the algorithm tracks the "Probe Sequence Length" (PSL - how far a key has moved from its ideal bucket). If an incoming key has a longer PSL than the occupant of a bucket, it "steals from the rich and gives to the poor"—evicting the current occupant and continuing the probe with the evicted key! This minimizes variance in lookup times.

Asymptotic Complexity Summary#

+-------------------+------------+------------+------------+
| Operation         | Best Case  | Average    | Worst Case |
+-------------------+------------+------------+------------+
| Array Read by Idx | O(1)       | O(1)       | O(1)       |
| Array Append      | O(1)       | O(1) amort.| O(N) resize|
| Array Insert (mid)| O(1)       | O(N)       | O(N)       |
| Hash Map Lookup   | O(1)       | O(1)       | O(N) coll. |
| Hash Map Insert   | O(1)       | O(1)       | O(N) coll. |
| Hash Map Delete   | O(1)       | O(1)       | O(N) coll. |
+-------------------+------------+------------+------------+

Checkpoint Questions & Practice Exercises#

Question 1: An array of 32-bit floating-point numbers starts at memory address 0x2000. Calculate the physical byte address of the element at index i = 12.

• Answer:

- Base Address = 0x2000 (8192 in decimal).

- A 32-bit float consumes 4 bytes.

- Address = 8192 + (12 × 4) = 8192 + 48 = 8240 (hexadecimal: 0x2030).

Question 2: What is the Load Factor (α) of a hash table, and why do production hash tables rehash when the load factor exceeds 0.70 to 0.75?

• Answer: The Load Factor is defined as α = Number_of_Items / Total_Buckets. As α exceeds 0.75, the probability of hash collisions increases exponentially. In open addressing, clusters form, degrading search from O(1) towards O(N). Reallocating a table with double the capacity reduces α, restoring O(1) performance.