🧩 Algorithmic Deep Dives: Hashmap Internals & Tic-Tac-Toe Combinatorics

Targeted for: Juspay Elimination Round, Technical Interviews & Advanced Problem Solving
Key Focus: Hashmap architecture from scratch, Hash collision resolution (Chaining vs Open Addressing, Java 8 Treeification, Robin Hood), Ordered (std::map) vs Unordered (std::unordered_map) deep comparison, and Complete Mathematical & Algorithmic Analysis of Tic-Tac-Toe Winning Paths after each move.

📑 Quick Navigation

Hashmap Architecture & Core Implementation
Collision Resolution Strategies (Chaining vs Open Addressing)
Ordered Map (std::map) vs Unordered Map (std::unordered_map)
Tic-Tac-Toe Game Tree: Number of Winning Paths After Each Move
C++ Bitmask Solver: Dynamic Path Counter & Minimax Engine

1. Hashmap Architecture & Core Implementation

What is a Hashmap?

A Hashmap is an associative container that stores key-value pairs, providing average-case $O(1)$ time complexity for insertions, deletions, and lookups.

Key ("user_102") ──► [ Hash Function: MurmurHash3 / std::hash ]
                              │
                              ▼ 64-bit Integer (e.g., 0x8a3f59c1)
                     [ Bucket Index Calculation ]
                              │ Index = hash & (Capacity - 1)
                              ▼
                     Bucket Array [ Index = 5 ] ──► [ Key: "user_102", Val: 450 ]

Core Components of a Hashmap

Underlying Array (Buckets): A contiguous array of pointers or entries initialized to a power-of-two capacity (e.g., 16).
Hash Function: Maps an arbitrary key type (string, struct) into a uniformly distributed integer.
- Desired properties: Deterministic, uniform distribution across buckets, fast computation, and avalanche effect (changing 1 bit in the key changes ~50% of the hash bits).
Power-of-Two Index Optimization: Instead of expensive modulo division (hash % capacity), modern runtimes require capacity = 2^k: $$\text{Bucket Index} = \text{hash} \ & \ (\text{capacity} - 1)$$
- Hardware efficiency: Bitwise AND executes in 1 CPU clock cycle, whereas integer division (div/idiv) takes 15–40 clock cycles!
Load Factor ($\alpha$) & Rehashing: $$\alpha = \frac{\text{Number of Stored Elements } (N)}{\text{Number of Buckets } (M)}$$
- Default threshold is typically $\alpha = 0.75$.
- When $N > \alpha \times M$, the hashmap triggers Rehashing:
  1. Allocates a new bucket array of double capacity ($2M$).
  2. Re-computes the bucket index for every existing entry.
  3. Inserts entries into the new array and frees old buckets.
  4. Amortized cost per insertion remains $O(1)$.

C++ Implementation from Scratch (Separate Chaining)

#include <iostream>
#include <vector>
#include <string>
#include <functional>

template <typename K, typename V>
class CustomHashMap {
private:
    struct Node {
        K key;
        V value;
        Node* next;
        Node(K k, V v) : key(k), value(v), next(nullptr) {}
    };

    std::vector<Node*> buckets;
    size_t capacity;
    size_t num_elements;
    const float LOAD_FACTOR_THRESHOLD = 0.75f;

    size_t getBucketIndex(const K& key) const {
        return std::hash<K>{}(key) & (capacity - 1);
    }

    void rehash() {
        size_t old_capacity = capacity;
        capacity *= 2;
        std::vector<Node*> new_buckets(capacity, nullptr);

        for (size_t i = 0; i < old_capacity; ++i) {
            Node* curr = buckets[i];
            while (curr != nullptr) {
                Node* next_node = curr->next;
                size_t new_idx = std::hash<K>{}(curr->key) & (capacity - 1);
                
                // Insert at head of new bucket
                curr->next = new_buckets[new_idx];
                new_buckets[new_idx] = curr;
                
                curr = next_node;
            }
        }
        buckets = std::move(new_buckets);
    }

public:
    CustomHashMap(size_t initial_cap = 16) : capacity(initial_cap), num_elements(0) {
        buckets.resize(capacity, nullptr);
    }

    ~CustomHashMap() {
        for (size_t i = 0; i < capacity; ++i) {
            Node* curr = buckets[i];
            while (curr) {
                Node* temp = curr;
                curr = curr->next;
                delete temp;
            }
        }
    }

    void insert(const K& key, const V& value) {
        if ((float)(num_elements + 1) / capacity > LOAD_FACTOR_THRESHOLD) {
            rehash();
        }

        size_t idx = getBucketIndex(key);
        Node* curr = buckets[idx];

        // Check if key already exists -> Update value
        while (curr != nullptr) {
            if (curr->key == key) {
                curr->value = value;
                return;
            }
            curr = curr->next;
        }

        // Key doesn't exist -> prepend new node at bucket head
        Node* new_node = new Node(key, value);
        new_node->next = buckets[idx];
        buckets[idx] = new_node;
        num_elements++;
    }

    bool get(const K& key, V& out_val) const {
        size_t idx = getBucketIndex(key);
        Node* curr = buckets[idx];
        while (curr != nullptr) {
            if (curr->key == key) {
                out_val = curr->value;
                return true;
            }
            curr = curr->next;
        }
        return false;
    }

    bool remove(const K& key) {
        size_t idx = getBucketIndex(key);
        Node* curr = buckets[idx];
        Node* prev = nullptr;

        while (curr != nullptr) {
            if (curr->key == key) {
                if (prev == nullptr) {
                    buckets[idx] = curr->next;
                } else {
                    prev->next = curr->next;
                }
                delete curr;
                num_elements--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false;
    }
};

2. Collision Resolution Strategies (Chaining vs Open Addressing)

When two distinct keys produce identical bucket indexes ($hash(K_1) \pmod M = hash(K_2) \pmod M$), a hash collision occurs.

┌─────────────────────────────────────────────────────────────────────────────┐
│                    COLLISION RESOLUTION TAXONOMY                            │
└─────────────────────────────────────────────────────────────────────────────┘

            ┌───────────────────────────┴───────────────────────────┐
            ▼                                                       ▼
  [ SEPARATE CHAINING ]                                    [ OPEN ADDRESSING ]
  Buckets hold external data structures.                   All elements reside directly
  - Linked List                                            inside the bucket array.
  - Java 8 Red-Black Tree                                  - Linear Probing
                                                           - Quadratic Probing
                                                           - Double Hashing
                                                           - Robin Hood Hashing

Strategy 1: Separate Chaining & The Java 8 "Treeification" Optimization

Each bucket points to a singly linked list of collided nodes.
Worst-Case Vulnerability (Hash DoS Attack): An attacker submits thousands of keys crafted to collide into the exact same bucket, degrading lookup performance from $O(1)$ to $O(N)$ and causing 100% CPU denial of service!
Java 8 Solution (Treeification):
- If a bucket's linked list length exceeds TREEIFY_THRESHOLD = 8 AND total table capacity $\ge 64$:
- The JVM automatically transforms the linked list into a Red-Black Balanced Binary Search Tree.
- Worst-case lookup time drops from $O(N)$ to guaranteed $O(\log k)$!
- If deletions reduce node count in that bucket to UNTREEIFY_THRESHOLD = 6, it converts back to a linked list to conserve memory.

Strategy 2: Open Addressing Variants

In Open Addressing, no external pointers are used. If bucket $H$ is occupied, the algorithm probes subsequent slots according to a mathematical sequence until finding an empty slot:

1. Linear Probing:

$$h(k, i) = (h'(k) + i) \pmod M$$

Probes: $H, H+1, H+2, H+3, \dots$
Advantage: Superb CPU Cache Locality (contiguous sequential RAM accesses).
Disadvantage: Primary Clustering (adjacent occupied slots merge into long contiguous clusters; any key hashing near the cluster expands it further).

2. Quadratic Probing:

$$h(k, i) = (h'(k) + c_1 i + c_2 i^2) \pmod M$$

Probes: $H, H+1, H+4, H+9, \dots$
Advantage: Eliminates primary clustering.
Disadvantage: Suffers from Secondary Clustering (keys with identical initial hashes follow the identical probe sequence).

3. Double Hashing:

$$h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod M$$

Uses two independent hash functions $h_1$ and $h_2$.
Condition: $h_2(k)$ must be coprime to table size $M$ (e.g., $M$ is prime).
Completely eliminates both primary and secondary clustering.

4. Robin Hood Hashing:

Tracks the Probe Sequence Length (PSL): how far an element is displaced from its ideal hash bucket.
During insertion, if the incoming element has a higher PSL than the element currently occupying the slot, it evicts the resident element and steals its slot ("steals from the rich, gives to the poor").
Result: Drastically compresses variance in probe lengths, ensuring extremely fast lookups and predictable bounds.

The Deletion Dilemma: Why Open Addressing Needs "Tombstones"

If you insert $A$ at index 2, $B$ collides and probes to index 3. If you delete $A$ and set index 2 to EMPTY: When searching for $B$, the search probes index 2, sees EMPTY, assumes $B$ does not exist, and terminates prematurely!

Fix: Deleted slots must be marked with a special sentinel marker: TOMBSTONE (or DELETED).
Lookups continue past tombstones; insertions can overwrite tombstones.

3. Ordered Map (`std::map`) vs Unordered Map (`std::unordered_map`)

A definitive comparison between the two standard C++ associative containers:

Dimension	`std::map` (Ordered Map)	`std::unordered_map` (Unordered Map)
Underlying Data Structure	Self-Balancing BST (Red-Black Tree)	Hash Table with buckets & collision chains
Key Ordering	Strictly Sorted based on `operator<` (or custom comparator)	Arbitrary / Non-deterministic order
Search Time (Average)	$O(\log N)$	$O(1)$
Search Time (Worst Case)	Guaranteed $O(\log N)$ (strict tree balance)	$O(N)$ (if all keys collide into 1 bucket)
Insert / Delete Time	$O(\log N)$	Average $O(1)$, Worst $O(N)$ (during rehash)
Memory Overhead	High per element: 3 pointers (left, right, parent) + 1 color bit per node (typically 32–40 bytes overhead per node).	Variable: Bucket array pointers + node pointers + empty bucket slack ($\approx 25-50%$ empty).
Cache Locality	Poor: Tree nodes are allocated individually on heap $\to$ pointer chasing causes frequent CPU L1/L2 cache misses.	Moderate to High: Hash table bucket lookups are localized; open-addressing variants have near-optimal cache lines.
Range Queries	Native & Fast: `lower_bound()`, `upper_bound()`, in-order iteration in $O(K + \log N)$.	Unsupported: Requires scanning all $N$ elements and sorting ($O(N \log N)$).
Key Type Requirement	Requires `operator<` (Strict Weak Ordering).	Requires `std::hash<Key>` function and `operator==`.
Iterator Invalidation	Never invalidates existing iterators on insert/delete (except the specific deleted node).	Rehash invalidates all iterators when capacity expands!

4. Tic-Tac-Toe Game Tree: Number of Winning Paths After Each Move

Interview Question: "In a standard $3 \times 3$ Tic-Tac-Toe game, how many total valid game paths exist? How many winning paths exist for player X and player O after each move?"

This is a classic combinatorial and state-space tree traversal problem asked to test recursion, game theory, symmetry, and backtracking.

Fundamental Game Rules & Combinatorics

Board: $3 \times 3$ grid = 9 squares.
Players: Player $X$ moves first (Odd moves: 1, 3, 5, 7, 9); Player $O$ moves second (Even moves: 2, 4, 6, 8).
Winning Condition: A player places 3 pieces in a row (3 rows, 3 columns, 2 diagonals = 8 winning lines).
Game Termination: The game terminates immediately as soon as either player achieves 3-in-a-row, or when all 9 cells are filled without a winner (Draw).

UPPER BOUND (Naive Permutations):
Total sequences of 9 moves = 9! = 362,880 play-outs.
However, games stop early upon winning, making the actual valid game tree smaller!

The Exact Game Tree Numbers (Rigorous Mathematical Proof)

Through complete state-space tree expansion:

Total Valid Reachable Board States: 5,478 states (or 765 unique states when accounting for 8-fold dihedral rotational/reflectional symmetry $D_4$).
Total Valid Completed Game Paths (Terminal Leaves in Game Tree): 255,168 valid games.

Outcome Breakdown of all 255,168 Play-Outs:

$$\text{Player } X \text{ Wins}: \mathbf{131,184\text{ paths}} \quad (51.4%)$$ $$\text{Player } O \text{ Wins}: \mathbf{77,904\text{ paths}} \quad (30.5%)$$ $$\text{Draw (Tie)}: \mathbf{46,080\text{ paths}} \quad (18.1%)$$ $$\mathbf{Total = 131,184 + 77,904 + 46,080 = 255,168}$$

Winning Paths Breakdown: Move-by-Move

A player needs at least 3 marks on the board to form a winning line:

Minimum moves for $X$ to win = Move 5 ($X$ has played 3 times, $O$ has played 2 times).
Minimum moves for $O$ to win = Move 6 ($X$ has played 3 times, $O$ has played 3 times).

┌────────────────────────────────────────────────────────────────────────────────────────┐
│               EXACT DISTRIBUTION OF TERMINAL GAME PATHS BY MOVE DEPTH                  │
└────────────────────────────────────────────────────────────────────────────────────────┘

 Move Depth    Turn     X Wins Paths     O Wins Paths     Draw Paths     Total Paths Ended
 ─────────────────────────────────────────────────────────────────────────────────────────
 Move 1–4      -        0                0                0              0
 Move 5        X        1,440            0                0              1,440
 Move 6        O        0                5,328            0              5,328
 Move 7        X        47,952           0                0              47,952
 Move 8        O        0                72,576           0              72,576
 Move 9        X        81,792           0                46,080         127,872
 ─────────────────────────────────────────────────────────────────────────────────────────
 TOTAL                  131,184          77,904           46,080         255,168

Analytical Mathematical Derivation for Move 5 (X's First Possible Win)

Let us prove why exactly 1,440 paths terminate at Move 5:

There are 8 possible winning lines (3 horizontal, 3 vertical, 2 diagonal).
For any chosen winning line:
- Player $X$ places 3 tokens in those 3 specific squares. The order in which $X$ placed them is $3! = 6$ permutations.
Player $O$ has made 2 moves in the remaining $9 - 3 = 6$ empty squares.
- The number of ordered ways $O$ could place their 2 pieces is $P(6, 2) = 6 \times 5 = 30$ ways.
Total winning sequences for $X$ on Move 5: $$\text{Winning Paths (Move 5)} = 8 \text{ lines} \times 3! \times (6 \times 5) = 8 \times 6 \times 30 = \mathbf{1,440\text{ paths}}$$ (Notice that at Move 5, none of O's 2 pieces could have formed a win, so all 1,440 paths are strictly valid!)

5. C++ Bitmask Solver: Dynamic Path Counter & Minimax Engine

Here is the exact, blazing-fast C++ program to compute winning paths from any board state using 18-bit bitmasks:

#include <iostream>
#include <vector>
#include <array>

// 8 Winning Line Bitmasks for a 3x3 Grid
// 0 1 2
// 3 4 5
// 6 7 8
const std::array<int, 8> WIN_PATTERNS = {
    0b000000111, // Row 0 (cells 0, 1, 2)
    0b000111000, // Row 1 (cells 3, 4, 5)
    0b111000000, // Row 2 (cells 6, 7, 8)
    0b001001001, // Col 0 (cells 0, 3, 6)
    0b010010010, // Col 1 (cells 1, 4, 7)
    0b100100100, // Col 2 (cells 2, 5, 8)
    0b100010001, // Diag 1 (cells 0, 4, 8)
    0b001010100  // Diag 2 (cells 2, 4, 6)
};

// Check if a bitmask contains 3 in a row
inline bool hasWon(int mask) {
    for (int pattern : WIN_PATTERNS) {
        if ((mask & pattern) == pattern) return true;
    }
    return false;
}

struct GameStats {
    long long x_wins = 0;
    long long o_wins = 0;
    long long draws = 0;
    std::array<long long, 10> wins_by_depth_x = {0};
    std::array<long long, 10> wins_by_depth_o = {0};
};

GameStats stats;

// Recursive Game Tree Traversal
void traverseGameTree(int maskX, int maskO, int depth, bool isXTurn) {
    // 1. Check if previous move won
    if (!isXTurn) {
        // Last move was by X
        if (hasWon(maskX)) {
            stats.x_wins++;
            stats.wins_by_depth_x[depth]++;
            return;
        }
    } else {
        // Last move was by O
        if (hasWon(maskO)) {
            stats.o_wins++;
            stats.wins_by_depth_o[depth]++;
            return;
        }
    }

    // 2. Check if board is full -> Draw
    if (depth == 9) {
        stats.draws++;
        return;
    }

    // 3. Try all remaining empty cells
    int occupied = maskX | maskO;
    for (int cell = 0; cell < 9; ++cell) {
        if (!(occupied & (1 << cell))) {
            if (isXTurn) {
                traverseGameTree(maskX | (1 << cell), maskO, depth + 1, false);
            } else {
                traverseGameTree(maskX, maskO | (1 << cell), depth + 1, true);
            }
        }
    }
}

int main() {
    std::cout << "Traversing Tic-Tac-Toe Game Tree..." << std::endl;
    traverseGameTree(0, 0, 0, true);

    long long total_games = stats.x_wins + stats.o_wins + stats.draws;
    std::cout << "\n================ RESULTS ================" << std::endl;
    std::cout << "Total Valid Terminal Games: " << total_games << std::endl;
    std::cout << "X Wins: " << stats.x_wins << " (" << (stats.x_wins * 100.0 / total_games) << "%)" << std::endl;
    std::cout << "O Wins: " << stats.o_wins << " (" << (stats.o_wins * 100.0 / total_games) << "%)" << std::endl;
    std::cout << "Draws:  " << stats.draws  << " (" << (stats.draws * 100.0 / total_games) << "%)\n" << std::endl;

    std::cout << "--- X Wins by Move Depth ---" << std::endl;
    for (int d = 1; d <= 9; ++d) {
        if (stats.wins_by_depth_x[d] > 0)
            std::cout << "Depth " << d << ": " << stats.wins_by_depth_x[d] << " paths\n";
    }

    std::cout << "\n--- O Wins by Move Depth ---" << std::endl;
    for (int d = 1; d <= 9; ++d) {
        if (stats.wins_by_depth_o[d] > 0)
            std::cout << "Depth " << d << ": " << stats.wins_by_depth_o[d] << " paths\n";
    }

    return 0;
}

Minimax & Game Theoretic Analysis: What if Both Players Play Optimally?

While there are 131,184 winning paths for X under random play:

Under Game Theoretic Optimal Play (Minimax with Alpha-Beta Pruning):
- Tic-Tac-Toe is a solved game.
- With two rational players, every single game results in a DRAW.
- The value of the root node is $0$.
- First move advantage: If $X$ plays Center or Corner, $X$ can never lose, but $O$ can force a draw by playing optimal responses.

01-hashmap-internals-and-tic-tac-toe-combinatorics.md