DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master separate chaining for hash collision resolution — complete implementation using linked lists, array-backed lists, and balanced BSTs as chain structures, formal average-case analysis, Java HashMap
The Core Idea
In separate chaining, each slot in the hash table holds a separate collection (the "chain") of all key-value pairs that hash to that slot.
| Index 0 | [] |
| Index 1: [(Bob, 25) | (Carol, 35)] ← Two keys hashed to index 1 |
| Index 2 | [(Alice, 30)] |
| Index 3 | [] |
| Index 4 | [(Dave, 28)] |
| Index 5 | [] |
| Index 6: [(Eve, 22) | (Frank, 40)] |
The chain is most commonly a singly linked list, but any dynamic structure works.
Average-Case Analysis
Theorem (SUHA — Simple Uniform Hashing Assumption): If the hash function distributes keys uniformly, then for n keys in m buckets (α = n/m):
- Successful lookup: 1 + α/2 probes on average
- Unsuccessful lookup: 1 + α probes on average
Proof (informal):
For a successful lookup of key k:
- k is in the bucket containing k
- The bucket was built by n-1 other insertions (not k itself)
- Each of the n-1 other keys has probability 1/m of going into k's bucket
- Expected keys before k in the chain: ((n-1)/m) / 2 ≈ α/2
- Plus 1 for finding k itself: 1 + α/2
For α = 1 (n = m): average 1.5 comparisons per lookup — essentially O(1).
Implementation with Python List (Array-Backed Chain)
Python lists have O(1) amortized append and O(1) random access, which can be faster than linked list nodes for small chains due to better cache behavior:
Example
class ArrayChainingHashMap:
def __init__(self, size=16):
self.size = size
self.buckets = [[] for _ in range(size)] # Python list per bucket
self.count = 0
def put(self, key, value):
idx = hash(key) % self.size
for i, (k, v) in enumerate(self.buckets[idx]):
if k == key:
self.buckets[idx][i] = (key, value)
return
self.buckets[idx].append((key, value))
self.count += 1
def get(self, key, default=None):
idx = hash(key) % self.size
for k, v in self.buckets[idx]:
if k == key: return v
return default
def delete(self, key):
idx = hash(key) % self.size
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket.pop(i)
self.count -= 1
return True
return False
Java HashMap's Treeification
Java's HashMap starts with linked list chains. When a single chain grows beyond 8 nodes, it converts that chain to a Red-Black Tree:
Code example
Chain length 1-7: Linked list, O(chain_length) lookup
Chain length ≥ 8: Red-Black tree, O(log(chain_length)) lookup
Why 8? Poisson distribution analysis shows:
P(chain length ≥ 8) ≈ 6×10⁻⁸ with good hash function
Only happens when hash function is poor or adversarial input existsThis gives Java HashMap O(log n) worst case instead of O(n) — important for security.
python example
# Python equivalent: use SortedList or BST for large chains
from sortedcontainers import SortedList
class TreeifiedChaining:
TREE_THRESHOLD = 8
def __init__(self):
self.buckets = {} # Simplified: idx → list or SortedListChaining with a Sorted Chain
For chains that support range queries:
Example
import bisect
class SortedChainingHashMap:
"""
Each bucket maintains a sorted list for binary search within chain.
Useful when chains grow large or range queries within a bucket are needed.
"""
def __init__(self, size=16):
self.size = size
self.chains = [[] for _ in range(size)] # List of (key, value) sorted by key
def put(self, key, value):
idx = hash(key) % self.size
chain = self.chains[idx]
# Binary search for key
keys = [k for k, v in chain]
pos = bisect.bisect_left(keys, key)
if pos < len(chain) and chain[pos][0] == key:
chain[pos] = (key, value) # Update
else:
chain.insert(pos, (key, value)) # Insert sorted
def get(self, key, default=None):
idx = hash(key) % self.size
chain = self.chains[idx]
keys = [k for k, v in chain]
pos = bisect.bisect_left(keys, key)
if pos < len(chain) and chain[pos][0] == key:
return chain[pos][1]
return default
Performance Summary
| Operation | Chaining (α=0.75) | Chaining (α=2) | Chaining (worst) |
|---|---|---|---|
| Lookup | O(1) | O(1) | O(n) |
| Insert | O(1) | O(1) | O(n) |
| Delete | O(1) | O(1) | O(n) |
| Memory | O(n+m) | O(n+m) | O(n+m) |
Practical tip: With α ≤ 0.75 and a good hash function, every operation is effectively O(1) for all but adversarial inputs.
Summary
Separate chaining:
- Each slot stores a dynamic structure (linked list, array, BST)
- O(1) average for all operations when α ≤ 1
- Handles any load factor — just degrades gracefully
- Easy deletion — just remove from the chain
- Java HashMap uses linked lists → Red-Black trees when chains are long
Preferred over open addressing when:
- Deletion is frequent
- Load factor may exceed 0.7
- Worst-case O(n) is unacceptable (use treeified chains)
- Memory is not extremely tight
*Next Lesson: Open Addressing*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Separate Chaining — Complete Implementation and Analysis.
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, chaining, separate chaining — complete implementation and analysis
Related Data Structures & Algorithms Topics
Continue learning this concept
HashingCollision Handling — Chaining vs Open Addressing Complete ComparisonMaster all collision resolution strategies for hash tables — separate chaining with linked lists, open addressing (linear probing, quadratic probing, double hashing), comparison of all methods, load factor effects, and when to use each approach.HashingHash Functions — Design, Properties, and Common ImplementationsA complete guide to hash functions — the mathematical properties of a good hash function, common hashing methods (division, multiplication, universal hashing), hash functions for strings and objects, cryptographic vs non-cryptographic hashes, and PythonHashingHashing — Complete Introduction to Hash Tables and Hash FunctionsA complete introduction to hashing — what a hash table is, how hash functions work, why hash tables achieve O(1) average operations, the load factor, the difference between hash maps and hash sets, and real-world applications of hashing in databases, security, and caching.HashingHashing Problems — 10 Classic Interview Problems with Complete SolutionsSolve 10 classic hashing interview problems — two sum, group anagrams, longest consecutive sequence, subarray sum equals k, top k frequent elements, valid anagram, isomorphic strings, word pattern, 4-sum count, and design a hashmap from scratch.HashingOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingComplete guide to open addressing for hash collision resolution — linear probing with clustering analysis, quadratic probing, double hashing, tombstone deletion, the DELETED sentinel pattern, performance at different load factors, and Python dictAdvanced TopicsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsMaster bit manipulation completely — bitwise operators with truth tables, bit shifting, common tricks for setting/clearing/toggling bits, XOR magic properties, counting set bits (Brian Kernighan), power of two checks, swap without temp variable, and 15 classic interview problems solved with bit manipulation.