DSA Notes

Hub Algorithm vs Data Structure - Key Differences Real-World Applications of DSA Time and Space Complexity Overview What is DSA? Data Structures and Algorithms Why Learn Data Structures and Algorithms Asymptotic Analysis - Understanding Algorithm Growth Best, Average, and Worst Case Analysis Big O Notation - Upper Bound Analysis Big Omega Notation - Lower Bound Analysis Big Theta Notation - Tight Bound Analysis Space Complexity - Memory Analysis Time Complexity Examples and Analysis Array Interview Problems and Solutions Array Operations - Insert, Delete, Search Array Rotation Techniques Array Searching Techniques Arrays - Fundamental Data Structure Dynamic Arrays - Flexible Sizing Multidimensional Arrays - 2D and Beyond Sliding Window Technique for Arrays Anagram Problems - Character Rearrangement Palindrome Problems and Solutions Pattern Searching in Strings String Interview Problems Collection String Matching Algorithms - Pattern Searching String Operations - Concatenation, Substring, Manipulation String Data Structure - Fundamentals Circular Linked List - Ring Structure Doubly Linked List - Bidirectional Traversal Linked List Interview Problems Linked List - Data Structure Fundamentals Linked List Operations - Insert, Delete, Reverse Reverse Linked List - Iterative and Recursive Singly Linked List - Implementation and Operations Balanced Parentheses - Stack Application Infix, Prefix, Postfix Expressions - Stack Application Stack Implementation Techniques Stack Interview Problems and Solutions Stack Data Structure - LIFO Principle Stack using Arrays - Static Implementation Stack using Linked Lists - Dynamic Implementation Circular Queue - Efficient Space Usage Deque (Double Ended Queue)Priority Queue - Custom Ordering Queue Applications - Real-World Use Cases Queue Implementation - Array and Linked List Queue Interview Problems and Solutions Queue Data Structure - FIFO Principle AVL Tree - Self-Balancing Binary Search Tree Binary Search Tree (BST)Binary Tree - Structure and Operations Fenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BST Segment Tree - Range Query Data Structure Tree Interview Problems Collection Tree Data Structure Fundamentals Tree Traversals - Inorder, Preorder, Postorder, Level Order Heap Data Structure Heap Operations Heap Interview Problems Max-Heap Min-Heap Implementation and Use Cases Priority Queue using Heap Bellman-Ford Algorithm Breadth-First Search (BFS) Algorithm Depth-First Search (DFS) Algorithm Dijkstra\Floyd-Warshall Algorithm Graph Interview Problems Graph Data Structure Fundamentals Graph Representation Methods Kruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete Comparison Topological Sorting Union-Find (Disjoint Set Union)Separate Chaining Collision Handling Hash Functions Hashing Fundamentals Hashing Interview Problems Open Addressing Bubble Sort - Simple Sorting Algorithm Counting Sort - Non-Comparison Sorting Heap Sort - Heap Based Sorting Insertion Sort - Build Sorted Array Merge Sort - Divide and Conquer Quick Sort - Partition Based Sorting Radix Sort - Digit Based Sorting Selection Sort - Selection Based Sorting Sorting Algorithms Comparison - Choosing the Right Algorithm Sorting Algorithms - Fundamentals and Concepts Binary Search - Efficient Searching Interpolation Search - Intelligent Searching Linear Search - Sequential Search Algorithm Search Algorithms Comparison Searching Algorithm Interview Problems Ternary Search Algorithm Backtracking with Recursion Recursion Fundamentals - Base Case and Recurrence Recursion Problems and Solutions Recursion Tree - Visualizing Function Calls Recursion vs Iteration - Comparing Approaches Tail Recursion - Optimization Technique Dynamic Programming Interview Problems Dynamic Programming Fundamentals Fibonacci with Dynamic Programming 0/1 Knapsack Problem Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain Multiplication Memoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection Problem Fractional Knapsack Greedy Interview Problems Greedy Algorithm Fundamentals Huffman Coding — Data Structures & Algorithms Job Sequencing with Deadlines Backtracking Fundamentals Backtracking Practice Problems N-Queens Problem Rat in a Maze Subset Generation Sudoku Solver Codeforces Guide for Competitive Programmers Common Competitive Programming Techniques Contest Strategies for Competitive Programming Competitive Programming Introduction Fast Input/Output for Competitive Programming LeetCode Guide for Interview Preparation Bit Manipulation - Advanced Techniques Bloom Filter - Probabilistic Data Structure Computational Geometry - Algorithms and Techniques Disjoint Set Union (DSU) - Union Find Randomized Algorithms - Probabilistic Computing Skip List - Probabilistic Balanced Structure Suffix Array - String Indexing Trie - Prefix Tree for Efficient Searching Autocomplete System Using Trie Library Management System Using DSA Route Finder Using Graphs Mini Search Engine Project Social Network Analysis Using Graphs Essential Coding Patterns for Interviews DSA Cheatsheet: Quick Reference Essential DSA Interview Questions FAANG DSA Sheet: Company-Specific Patterns and Problems Problem Solving Strategies for Coding Interviews Complexity Cheatsheet Important Algorithms Summary Best Practice Platforms for DSA Recommended Books for DSA

Collision Handling

Understand why hash collisions are inevitable and compare the two primary strategies — separate chaining and open addressing — with their trade-offs.

Why Collisions Are Inevitable

A collision occurs when two different keys hash to the same index: h(k₁) = h(k₂) where k₁ ≠ k₂. Collisions are mathematically unavoidable due to the Pigeonhole Principle: if you have more possible keys than table slots (which is almost always true), at least two keys must share a slot.

Consider: even a table of size 1,000,000 hashing English words (170,000+ words) will have collisions. With random keys and a table of size m, the probability of at least one collision after inserting n keys is approximately 1 - e^(-n²/(2m)) — this is the Birthday Problem. With 23 keys in a table of size 365, there is already a 50% collision probability!

The Birthday Paradox in Hashing

Table size	1,000,000
100 keys	~0.5% chance of any collision
1,000 keys	~39% chance of collision
2,000 keys	~86% chance of collision

This is why every hash table implementation MUST handle collisions — they are not edge cases but routine occurrences.

Two Main Strategies

Strategy 1: Separate Chaining (Closed Addressing)

Each bucket holds a collection (typically a linked list) of all key-value pairs that hash to that index.

[0]	(14,"x") → (21,"y") → NULL
[1]	(8,"z") → NULL
[2]	NULL
[3]	(10,"w") → (17,"v") → (24,"u") → NULL
[4]	NULL
[5]	(5,"a") → NULL
[6]	(13,"b") → NULL

Multiple keys coexist peacefully at the same index. Insertion is always O(1) (prepend to list). Search/delete traverse the chain.

Strategy 2: Open Addressing (Closed Hashing)

All elements live directly in the table array. When a collision occurs, we probe for the next available slot using a systematic sequence.

[0]	14
[1]	21 (probed 1 step from index 0)
[2]	28 (probed 2 steps from index 0)
[3]	empty
[4]	empty
[5]	empty
[6]	empty

No extra data structures needed — everything fits in the original array.

Detailed Comparison

Aspect	Separate Chaining	Open Addressing
Storage	Array of linked lists	Single flat array
Load factor α	Can exceed 1.0	Must stay < 1.0 (typically < 0.7)
Cache performance	Poor (pointer chasing)	Excellent (contiguous memory)
Deletion	Simple (remove from list)	Complex (tombstones needed)
Worst-case search	O(n) (all in one chain)	O(n) (long probe sequence)
Memory overhead	Pointers per node	None (but needs empty slots)
Implementation	Simpler	More subtle
Resize trigger	α > 1.0 or chain too long	α > 0.7

When to Use Which?

Choose Separate Chaining When:

Load factor may exceed 0.7
Deletions are frequent (no tombstone complexity)
Keys are large (storing in array wastes space)
Implementation simplicity is valued
Unknown or variable number of elements

Choose Open Addressing When:

Memory is at a premium (no pointer overhead)
Cache performance matters (gaming, embedded systems)
Load factor is well-controlled (< 0.7)
Deletions are rare
Fixed/known upper bound on elements

Expected Performance

Separate Chaining

Average chain length = α (load factor). For a successful search, expected comparisons ≈ 1 + α/2. For an unsuccessful search, expected comparisons ≈ α.

α = 0.5	avg 1.25 comparisons (successful), 0.5 (unsuccessful)
α = 1.0	avg 1.5 comparisons (successful), 1.0 (unsuccessful)
α = 2.0	avg 2.0 comparisons (successful), 2.0 (unsuccessful)

Open Addressing (Linear Probing)

For a successful search: ≈ (1/2)(1 + 1/(1-α)) probes. For an unsuccessful search: ≈ (1/2)(1 + 1/(1-α)²) probes.

α = 0.5	avg 1.5 probes (successful), 2.5 (unsuccessful)
α = 0.7	avg 2.17 probes (successful), 6.06 (unsuccessful)
α = 0.9	avg 5.5 probes (successful), 50.5 (unsuccessful) ← degrades fast!

This shows why open addressing requires α < 0.7 — performance cliff beyond that.

Illustrative Python Code

Example

# Separate Chaining class ChainingHashTable: def __init__(self, size=16): self.size = size self.table = [[] for _ in range(size)] def put(self, key, value): idx = hash(key) % self.size for i, (k, v) in enumerate(self.table[idx]): if k == key: self.table[idx][i] = (key, value) return self.table[idx].append((key, value)) def get(self, key): idx = hash(key) % self.size for k, v in self.table[idx]: if k == key: return v return None # Open Addressing (Linear Probing) class ProbingHashTable: def __init__(self, size=16): self.size = size self.keys = [None] * size self.values = [None] * size def put(self, key, value): idx = hash(key) % self.size while self.keys[idx] is not None: if self.keys[idx] == key: self.values[idx] = value return idx = (idx + 1) % self.size self.keys[idx] = key self.values[idx] = value def get(self, key): idx = hash(key) % self.size while self.keys[idx] is not None: if self.keys[idx] == key: return self.values[idx] idx = (idx + 1) % self.size return None

Real-World Implementations

Language	Default HashMap	Strategy
Java (HashMap)	Chaining (linked list → red-black tree at 8)	Chaining
Python (dict)	Open addressing (custom probing)	Open addressing
C++ (unordered_map)	Chaining (linked list per bucket)	Chaining
Go (map)	Chaining (array of 8 per bucket)	Chaining variant
Rust (HashMap)	Robin Hood hashing (open addressing variant)	Open addressing

Interesting: Python chose open addressing for better cache locality, while most others chose chaining for simplicity.

Advanced: Hybrid Approaches

Modern implementations often combine ideas:

Java 8+ TreeBins: Chaining, but when a chain grows beyond 8 entries, it converts to a balanced tree (O(log n) worst case instead of O(n))
Cuckoo Hashing: Open addressing with two hash functions — guarantees O(1) worst-case lookup
Hopscotch Hashing: Open addressing with a neighborhood constraint — good cache performance + O(1) expected
Robin Hood Hashing: Open addressing where elements "steal" from richer neighbors — reduces variance in probe lengths

Key Takeaways

Collisions are not bugs — they are an inherent mathematical certainty. The art of hash table design is in handling them efficiently. Chaining is simpler and tolerates high load; open addressing is more memory-efficient and cache-friendly but demands careful load management. Understanding both strategies and their trade-offs is fundamental to systems design and to answering interview questions about hash map internals.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Collision Handling.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, hashing, collision, handling

Related Data Structures & Algorithms Topics

Continue learning this concept

HashingSeparate ChainingImplement and analyze separate chaining for hash collision resolution — linked lists at each bucket, performance analysis, load factor behavior, and practical considerations.HashingHash FunctionsExplore hash function design — division method, multiplication method, universal hashing, polynomial rolling hash, and properties that make a hash function effective.HashingHashing FundamentalsUnderstand hash tables from the ground up — key-value mapping, hash functions, O(1) average-case lookup, load factor, and why hashing is ubiquitous in computing.HashingHashing Interview ProblemsMaster four essential hashing interview problems — Two Sum, Group Anagrams, Longest Consecutive Sequence, and Subarray with Given Sum using hash maps for O(n) solutions.HashingOpen AddressingMaster open addressing for hash tables — linear probing, quadratic probing, double hashing, the clustering problem, deletion with tombstones, and complete implementations.Advanced TopicsBit Manipulation - Advanced TechniquesMaster bit manipulation techniques, bitwise operations, bit masking, and advanced binary algorithms for competitive programming and interviews.

PreviousSeparate Chaining NextHash Functions