Hashing

Definition

• Hashing maps data (keys) to fixed-size table positions (indices) via a hash function, enabling near O(1) average-case insert/search/delete

Hash Function

• Takes a key, returns an index within table bounds: $\text{index} = h(\text{key}) \bmod \text{table\_size}$
• Good hash function: uniform distribution (minimizes clustering), fast to compute, deterministic

Collisions & Resolution (the most-tested subtopic)

A collision occurs when two keys hash to the same index. Two main resolution families:

1. Chaining (Open Hashing) — each table slot holds a linked list of all keys hashing there; simple, handles high load factors gracefully
2. Open Addressing (Closed Hashing) — on collision, probe for the next open slot:
   • Linear Probing: check next slot sequentially (i+1, i+2…) — suffers from "primary clustering"
   • Quadratic Probing: check i+1², i+2²… — reduces clustering
   • Double Hashing: use a second hash function to determine probe interval — best distribution

Complexity

• Average case: O(1) for insert/search/delete
• Worst case: O(n) — if all keys collide into one slot/chain (poor hash function or adversarial input)

Load Factor

• $\alpha = n/m$ (number of entries / table size) — higher load factor increases collision probability; tables are typically resized (rehashed) when α exceeds a threshold (commonly 0.7)

Exam Angle / MCQ Trap

A guaranteed question: "Differentiate chaining, linear probing, and double hashing as collision resolution strategies." Know that hashing gives average O(1) but the worst case is always O(n) — don't claim O(1) unconditionally.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: Hashing Process, Worked Example

2017, Paper I, Q5(b) (6 marks) — Hash tables enable fast insertion and searching within the database. Describe the process of hashing with a suitable example.

Model answer: Hashing maps a key to an array index using a hash function $h(\text{key})$, giving average-case O(1) insertion, deletion and search since the location is computed directly instead of searched for.

Process: (1) choose a table of size m; (2) define $h(\text{key})$ mapping any key to $[0, m-1]$, e.g. $h(\text{key}) = \text{key} \bmod m$; (3) insert by placing the record at $\text{table}[h(\text{key})]$; (4) search by computing $h(\text{key})$ and looking directly there; (5) handle collisions (see below) since different keys can map to the same index.

Worked example — table size m = 7, $h(\text{key}) = \text{key} \bmod 7$, inserting 15, 22, 9:

$$\begin{aligned} h(15) &= 15 \bmod 7 = 1 \;\to\; \text{slot } 1 \\ h(22) &= 22 \bmod 7 = 1 \;\to\; \text{COLLISION with 15!} \\ &\quad\text{chaining: append 22 to the list at slot 1} \\ &\quad\text{linear probing: place 22 at slot 2 (next free slot)} \\ h(9) &= 9 \bmod 7 = 2 \;\to\; \text{chaining: slot 2 directly} \\ &\quad\text{(if probing used above) slot 3} \end{aligned}$$

This shows both the O(1) average-time benefit and why a collision-resolution strategy is mandatory for correctness, not just performance.

📝 Exam Practice: Choosing a Data Structure at Scale

2026, Paper I, Q8(c) (8 marks) — A company maintains millions of product IDs and frequently performs searching, insertion, and deletion. The data volume is extremely large, and performance is critical. Which data structure would be most suitable — Binary Search Tree, AVL Tree, Hash Table, or Array? Justify logically using time complexity and memory considerations.

Model answer: Hash Table is most suitable.

• Sorted array: O(log n) search but O(n) insert/delete (shifting) — unacceptable at scale.
• Plain BST: average O(log n), but degrades to O(n) worst case if IDs arrive in near-sorted batches (a real risk for sequentially-issued product IDs).
• AVL Tree: guarantees O(log n) worst case via rotations — solid, but still logarithmic, not constant.
• Hash Table: average-case O(1) search/insert/delete with a good hash function and load-factor management (dynamic resizing); product IDs are unique identifiers and make excellent hash keys.

Exam angle: the question deliberately gives no requirement for sorted/range-based retrieval — if it had, an AVL Tree would be the better answer (hash tables cannot efficiently support "give me all IDs between X and Y"). Always check whether ordering/range queries are needed before defaulting to "hash table = fastest."

📝 Exam Practice: Collision Resolution & Complexity (MCQ set)

2026, Paper I, Q12 (1 mark) — In Hash Tables, what is a collision resolution technique?

• A. Linear Search
• B. Binary Search
• C. Chaining ✓
• D. None of these

2025, Paper I, Q12 (1 mark) — Which one of the following is the fastest way of searching for a given key?

• A. Sorted array
• B. Linked list
• C. Binary search tree
• D. None of these ✓

MCQ Trap: the "obvious" answer to Q12/2025 looks like "Binary search tree" (O(log n)) — but a hash table's average O(1) beats all three listed options, and since "hash table" itself isn't an option, the only correct choice is None of these. Read every option list for what's missing, not just what's present.

---n## Direct-Address Tables — Hashing With a Bounded Key RangenWhen a problem guarantees keys fall in a small, known range (e.g., [1, 100]) regardless of how large n (the number of elements) is, you can use a direct-address table: a boolean/count array sized to the key range, with the identity function as the hash function ($h(\\text{key}) = \\text{key}$). This needs no collision handling at all — each possible key value maps to exactly one, dedicated slot — trading it for O(1) extra space instead of O(n), since the table size depends only on the (constant) key range, not on n.n### Exam AnglenThis is the pattern to reach for whenever a question emphasizes "values are bounded between X and Y" alongside "n is significantly larger than that range" — that phrasing is a direct signal to use a fixed-size lookup/frequency array instead of a general hash table with chaining/probing.n## 📌 More Sample & Repeated FPSC Questionsn### 📝 Exam Practice: Counting Distinct Elements in O(n)n2022, Paper I, Q3(a) (8 marks) — Complete the C++ code below to find the number of distinct elements in an array in O(n) time, where all elements are in the range [1,100] and n ≫ 100.ncpp\nint numDistinctElements(int array[], int n) {\n bool seen[101] = {false}; // direct-address table: identity hash, O(1) extra space (range is a fixed constant)\n int count = 0;\n for (int i = 0; i < n; i++) {\n if (!seen[array[i]]) {\n seen[array[i]] = true;\n count++;\n }\n }\n return count;\n}\nnKey reasoning points: a single O(n) pass marks each value's slot the first time it's seen and counts it exactly once; the seen array's size (101) never grows with n — it's fixed by the stated value range — which is precisely why the question stresses n ≫ 100: it's the tell that a bounded lookup table (not a general hash table, and not sorting-then-scanning at O(n log n)) is the intended O(n)/O(1)-extra-space solution.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-I · Q5(b) · 6 marks

Q. Hash tables enable fast insertion and searching. Describe the process of hashing with a suitable example.

Ans.

• Hashing converts a key into an array index using a hash function, so data can be stored and found directly without scanning.
• Example: table size m = 10, h(k) = k mod 10. Insert 25 → index 5, 37 → index 7, 42 → index 2. Searching for 37 goes straight to index 7.
• Collision: two keys map to the same index (25 and 35 both go to 5).
• Chaining: each slot holds a linked list, so 25 and 35 sit in the list at index 5.
• Open addressing (linear probing): 35 goes to the next free slot, 6.
• Cost: insert, search and delete are O(1) on average, O(n) in the worst case. A low load factor and a good hash function keep it fast.

2022 · Paper-I · Q3(a) · 8 marks

Q. Complete the code to find the number of distinct elements in an array in O(n) time, where all elements are in the range [1, 100] and n ≫ 100.

Ans.

int numDistinctElements(int array[], int n) {
    bool seen[101] = { false };          // one flag per possible value
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!seen[array[i]]) {           // first time this value appears
            seen[array[i]] = true;
            count++;
        }
    }
    return count;
}

• One pass over the array with O(1) work per element gives O(n) time and O(100) = O(1) extra space.
• For {3,1,3,8,2,1,8,2} the result is 4.

2026 · Paper-I · Q8(c) · 8 marks

Q. A company stores millions of product IDs and frequently searches, inserts and deletes them. Which data structure is most suitable: BST, AVL tree, hash table or array? Justify using time complexity and memory.

Ans.

• Choice: hash table (with a good hash function and chaining or open addressing). For millions of IDs, average O(1) operations beat O(log n) (about 20 comparisons for a million keys).
• Memory: a hash table uses somewhat more space than an array, but far less work per operation. Tree nodes also carry pointers.
• Exception: if sorted order or range queries are needed, use an AVL tree.

MCQs

2025 P-I · Q12. Which one of the following is the fastest way of searching for a given key?

• (A) Sorted array
• (B) Linked list
• (C) Binary search tree
• (D) None of these ✅
• Answer: (D) None of these.
• Why: a sorted array and a binary search tree take O(log n), and a linked list takes O(n). The fastest method is a hash table with O(1) average search, and it is not in the list.

2025 P-I · Q19. What is the time complexity of searching for an element in a hash table?

• (A) O(1) ✅
• (B) O(n)
• (C) O(n log n)
• (D) None of these
• Answer: (A) O(1) (average case).
• Why: the hash function turns the key into an index directly, so the search takes constant time. It degrades to O(n) only in the worst case, when many keys collide.

2026 P-I · Q12. In hash tables, what is a collision resolution technique?

• (A) Linear Search
• (B) Binary Search
• (C) Chaining ✅
• (D) None of these
• Answer: (C) Chaining.
• Why: with chaining, all keys that hash to the same slot are stored in a linked list at that slot. Linear and binary search are search methods, not ways to resolve collisions. (Open addressing, such as linear probing, is the other collision method.)