Arrays & Hashing

Every AI system — from recommendation engines to search indexes — is built on two primitives: arrays and hash maps. Master these and you master the foundation.

---

How Arrays Work

An array stores elements in contiguous memory — each slot is one step from the next.

Key characteristics:

• O(1) access — jump directly to any index
• O(n) insert/delete — shifting elements is expensive
• Cache-friendly — sequential memory = fast CPU reads
• Fixed size (in most languages) — must know capacity upfront

---

How Hash Maps Work

A hash map converts a key into an index using a hash function, then stores the value in that bucket.

The process:

1. Input: "apple" (key)
2. Hash: hash("apple") % size → bucket 0
3. Store: bucket 0 = {apple: 3}
4. Lookup: O(1) average — go straight to the bucket

Key characteristics:

• O(1) average lookup, insert, delete
• O(n) worst case — when all keys collide into one bucket
• Unordered — no guaranteed iteration order
• Keys must be hashable — immutable types work best

---

Pattern 1: Two Sum

Given an array and a target, find two numbers that add up to the target.

Brute force: Check every pair → O(n²) Hash map approach: For each number, check if target - num exists → O(n)

Step by step with nums = [2, 7, 11, 15], target = 9:

| Step | Current | Need (9 - current) | In Map? | Action | |------|---------|---------------------|---------|--------| | 1 | 2 | 7 | No | Store {2: 0} | | 2 | 7 | 2 | Yes! | Return [0, 1] |

---

Pattern 2: Frequency Counting

Count how often each element appears.

def frequency_count(nums):
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    return freq

# [1, 2, 2, 3, 3, 3] → {1: 1, 2: 2, 3: 3}

Used in:

• Top K Frequent Elements — count then sort by frequency
• Valid Anagram — compare character frequencies
• Group Anagrams — group words with same sorted characters

---

Pattern 3: Grouping by Key

Group anagrams: ["eat","tea","tan","ate","nat","bat"]

Strategy: Sort each word → use sorted version as hash key.

| Original | Sorted (Key) | Group | |----------|-------------|-------| | "eat" | "aet" | ["eat", "tea", "ate"] | | "tan" | "ant" | ["tan", "nat"] | | "bat" | "abt" | ["bat"] |

---

The AI Connection: Feature Stores

In production ML systems, feature stores use hash maps at their core:

• User ID → feature vector — instant lookup for real-time recommendations
• Product ID → embeddings — similarity search in recommendation engines
• Cache layer — avoid recomputing expensive features

---

Complexity Cheat Sheet

| Operation | Array | Hash Map | |-----------|-------|----------| | Access by index | O(1) | — | | Search by value | O(n) | O(1) avg | | Insert at end | O(1)* | O(1) avg | | Insert at start | O(n) | O(1) avg | | Delete | O(n) | O(1) avg | | Space | O(n) | O(n) |

*amortised for dynamic arrays