DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL 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 Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete 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
Implement and analyze separate chaining for hash collision resolution — linked lists at each bucket, performance analysis, load factor behavior, and practical considerations.
How Separate Chaining Works
In separate chaining, each slot (bucket) in the hash table holds a pointer to a data structure — typically a linked list — that stores all key-value pairs mapping to that index. When a collision occurs, the new element is simply appended (or prepended) to the list at that bucket.
| Index 0: | [7, "seven"] → [14, "fourteen"] → [21, "twenty-one"] → NULL |
| Index 1: | [1, "one"] → [8, "eight"] → NULL |
| Index 2: | [2, "two"] → NULL |
| Index 3: | NULL (empty bucket) |
| Index 4: | [4, "four"] → [11, "eleven"] → NULL |
| Index 5: | [5, "five"] → NULL |
| Index 6: | [6, "six"] → NULL |
Operations
Insert (key, value)
- Compute
index = h(key) - Search the chain at
table[index]for the key - If found, update the value
- If not found, prepend/append to the chain
Search (key)
- Compute
index = h(key) - Traverse the chain at
table[index] - Return value if key found, else "not found"
Delete (key)
- Compute
index = h(key) - Traverse the chain, find the node
- Remove the node from the linked list (standard list deletion)
Complete Python Implementation
Example
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class ChainingHashTable:
def __init__(self, capacity=16, max_load=2.0):
self.capacity = capacity
self.max_load = max_load
self.size = 0
self.table = [None] * capacity
def _hash(self, key):
return hash(key) % self.capacity
def _load_factor(self):
return self.size / self.capacity
def _resize(self):
old_table = self.table
self.capacity *= 2
self.table = [None] * self.capacity
self.size = 0
for head in old_table:
node = head
while node:
self.put(node.key, node.value)
node = node.next
def put(self, key, value):
if self._load_factor() >= self.max_load:
self._resize()
index = self._hash(key)
node = self.table[index]
# Search for existing key
while node:
if node.key == key:
node.value = value # update
return
node = node.next
# Insert at head (O(1))
new_node = Node(key, value)
new_node.next = self.table[index]
self.table[index] = new_node
self.size += 1
def get(self, key):
index = self._hash(key)
node = self.table[index]
while node:
if node.key == key:
return node.value
node = node.next
raise KeyError(f"Key '{key}' not found")
def delete(self, key):
index = self._hash(key)
node = self.table[index]
prev = None
while node:
if node.key == key:
if prev:
prev.next = node.next
else:
self.table[index] = node.next
self.size -= 1
return
prev = node
node = node.next
raise KeyError(f"Key '{key}' not found")
def display(self):
for i in range(self.capacity):
chain = []
node = self.table[i]
while node:
chain.append(f"({node.key}:{node.value})")
node = node.next
if chain:
print(f" [{i}]: {' → '.join(chain)}")
# Usage
ht = ChainingHashTable(capacity=7)
for num in [7, 14, 21, 1, 8, 2, 4, 11, 5, 6]:
ht.put(num, str(num))
ht.display()
print(f"Get 14: {ht.get(14)}")
ht.delete(14)
print(f"After deleting 14:")
ht.display()
C++ Implementation
Example
#include <list>
#include <vector>
#include <iostream>
#include <stdexcept>
using namespace std;
template <typename K, typename V>
class ChainingHashMap {
struct Entry { K key; V value; };
int capacity, count;
vector<list<Entry>> table;
int hashIndex(const K& key) {
return hash<K>{}(key) % capacity;
}
public:
ChainingHashMap(int cap = 16) : capacity(cap), count(0), table(cap) {}
void put(const K& key, const V& value) {
int idx = hashIndex(key);
for (auto& entry : table[idx]) {
if (entry.key == key) {
entry.value = value;
return;
}
}
table[idx].push_back({key, value});
count++;
if ((double)count / capacity > 2.0)
resize();
}
V get(const K& key) {
int idx = hashIndex(key);
for (auto& entry : table[idx])
if (entry.key == key)
return entry.value;
throw runtime_error("Key not found");
}
void remove(const K& key) {
int idx = hashIndex(key);
table[idx].remove_if([&](const Entry& e) { return e.key == key; });
count--;
}
private:
void resize() {
auto oldTable = move(table);
capacity *= 2;
table.assign(capacity, list<Entry>());
count = 0;
for (auto& chain : oldTable)
for (auto& entry : chain)
put(entry.key, entry.value);
}
};
Performance Analysis
Assuming a good hash function distributes n keys uniformly across m buckets:
Average chain length = n/m = α (load factor)
| Operation | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Insert | O(1) | O(1) | O(n) — all keys in one chain |
| Search (success) | O(1) | O(1 + α/2) | O(n) |
| Search (failure) | O(1) | O(1 + α) | O(n) |
| Delete | O(1) | O(1 + α/2) | O(n) |
The O(1 + α) means: O(1) to compute the hash, plus traversing an average chain of length α.
When α = 1.0:
- Successful search: ~1.5 comparisons on average
- Unsuccessful search: ~2 comparisons
When α = 0.5:
- Successful search: ~1.25 comparisons
- Unsuccessful search: ~1.5 comparisons
Advantages of Separate Chaining
- Simple to implement — standard linked list operations
- Load factor can exceed 1.0 — chains just grow longer
- Deletion is straightforward — no tombstones or restructuring needed
- Graceful degradation — performance degrades linearly with load, no sudden cliff
- Dynamic — memory allocated per insertion (no wasted pre-allocated slots)
Disadvantages
- Poor cache performance — pointer chasing across non-contiguous memory
- Extra memory per entry — each node needs a next pointer (8 bytes on 64-bit)
- Memory fragmentation — nodes allocated individually on heap
- Slow for small tables — overhead of linked list outweighs benefit
Optimization: Chaining with Arrays Instead of Lists
Replace linked lists with dynamic arrays (vectors) per bucket for better cache locality:
Example
class ArrayChainingTable:
def __init__(self, capacity=16):
self.capacity = capacity
self.table = [[] for _ in range(capacity)] # list of lists
def put(self, key, value):
idx = hash(key) % self.capacity
bucket = self.table[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
This is what Python's dict actually does (sort of) — it trades linked-list pointer overhead for array-based storage with better spatial locality.
Java's Advanced Chaining (Tree Bins)
Java 8's HashMap converts a chain to a red-black tree when its length reaches 8:
| Chain length < 8 | Linked list (O(n) search within chain) |
| Chain length ≥ 8 | Red-black tree (O(log n) search within chain) |
| Chain length < 6 | Reverts to linked list (hysteresis) |
This ensures O(log n) worst case even with terrible hash distribution — a defense against hash-flooding attacks.
Real-World Applications
- Java HashMap, C++ unordered_map — both use chaining by default
- Database hash joins — build phase creates chained hash table of smaller relation
- Symbol tables in compilers — variable/function names stored with chaining
- Network packet classification — rule tables use chaining for multi-match
Key Takeaways
Separate chaining is the most intuitive collision resolution strategy: each bucket holds a list of collided elements. It is simple, deletion-friendly, and tolerates high load factors. The trade-off is cache performance and memory overhead from pointers. For most general-purpose applications (Java, C++ standard libraries), chaining remains the default choice due to its robustness and simplicity.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Separate Chaining.
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
Related Data Structures & Algorithms Topics
Continue learning this concept
HashingCollision HandlingUnderstand why hash collisions are inevitable and compare the two primary strategies — separate chaining and open addressing — with their trade-offs.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.