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

Open Addressing

Master open addressing for hash tables — linear probing, quadratic probing, double hashing, the clustering problem, deletion with tombstones, and complete implementations.

How Open Addressing Works

In open addressing, all elements live directly inside the hash table array. When a collision occurs, we systematically search for the next available slot using a probe sequence. There are no linked lists, no pointers — just the flat array.

The probe sequence for key k is: h(k,0), h(k,1), h(k,2), ... where h(k,i) gives the i-th slot to check. Different probing methods define different sequences.

Linear Probing

The simplest approach: if slot h(k) is occupied, try h(k)+1, then h(k)+2, and so on (wrapping around).

h(k, i) = (h(k) + i) mod m

Table size m=7. Insert keys	7, 14, 21, 3
h(7) = 7 % 7 = 0	slot 0 free → place 7
h(14) = 14 % 7 = 0	slot 0 taken → try 1 → free → place 14
h(21) = 21 % 7 = 0	slot 0 taken → 1 taken → try 2 → free → place 21
h(3) = 3 % 7 = 3	slot 3 free → place 3
Table	[7, 14, 21, 3, _, _, _]

The Clustering Problem

Linear probing suffers from primary clustering: occupied slots form contiguous blocks. New keys hashing near a cluster join and extend it, making the cluster grow faster.

Example

Before: [X, X, X, X, _, _, _, X, X, _] ↑ cluster of 4 Any key hashing to indices 0,1,2,3,4 will join this cluster. That's 5/10 = 50% of keys! The cluster grows quadratically.

Despite clustering, linear probing has excellent cache performance (sequential memory access) and is the fastest method for low load factors (α < 0.5).

Quadratic Probing

Spreads probes more by using quadratic steps: h(k, i) = (h(k) + c₁i + c₂i²) mod m

Common choice: h(k, i) = (h(k) + i²) mod m

Probe 0	slot 3
Probe 1	slot (3 + 1) % 11 = 4
Probe 2	slot (3 + 4) % 11 = 7
Probe 3	slot (3 + 9) % 11 = 1
Probe 4	slot (3 + 16) % 11 = 8

Eliminates primary clustering — different initial hashes produce different probe sequences. However, keys with the same hash still follow the same quadratic sequence (secondary clustering).

Caveat: Quadratic probing does not guarantee visiting all slots. For full coverage, table size must be prime and α < 0.5, OR use (h + i(i+1)/2) mod 2^k with power-of-2 table size.

Double Hashing

Uses a second hash function to determine the probe step size:

h(k, i) = (h₁(k) + i × h₂(k)) mod m

python example

# h1(k) = k % m
# h2(k) = 1 + (k % (m-1))   — ensures h2 is never 0

# Key=14, m=7:
# h1(14) = 0, h2(14) = 1 + (14 % 6) = 3
# Probe sequence: 0, 3, 6, 2, 5, 1, 4 — visits ALL slots!

No clustering at all — each key has its own unique probe sequence. This gives the best distribution but costs an extra hash computation per probe.

Complete Python Implementation

Example

class OpenAddressHashTable: EMPTY = None DELETED = object() # tombstone sentinel def __init__(self, capacity=16, probe='linear'): self.capacity = capacity self.probe_type = probe self.keys = [self.EMPTY] * capacity self.values = [None] * capacity self.size = 0 def _hash1(self, key): return hash(key) % self.capacity def _hash2(self, key): # For double hashing: step size return 1 + (hash(key) % (self.capacity - 1)) def _probe(self, key, i): h = self._hash1(key) if self.probe_type == 'linear': return (h + i) % self.capacity elif self.probe_type == 'quadratic': return (h + i * i) % self.capacity else: # double return (h + i * self._hash2(key)) % self.capacity def put(self, key, value): if self.size >= self.capacity * 0.7: self._resize() first_deleted = -1 for i in range(self.capacity): idx = self._probe(key, i) if self.keys[idx] == self.EMPTY: # Use first deleted slot if found, otherwise this empty slot insert_idx = first_deleted if first_deleted != -1 else idx self.keys[insert_idx] = key self.values[insert_idx] = value self.size += 1 return elif self.keys[idx] is self.DELETED: if first_deleted == -1: first_deleted = idx elif self.keys[idx] == key: self.values[idx] = value # update existing return def get(self, key): for i in range(self.capacity): idx = self._probe(key, i) if self.keys[idx] == self.EMPTY: return None # not found (empty slot = end of probe chain) if self.keys[idx] == key: return self.values[idx] # Skip DELETED slots — they don't end the search return None def delete(self, key): for i in range(self.capacity): idx = self._probe(key, i) if self.keys[idx] == self.EMPTY: return False # not found if self.keys[idx] == key: self.keys[idx] = self.DELETED # tombstone self.values[idx] = None self.size -= 1 return True return False def _resize(self): old_keys = self.keys old_values = self.values self.capacity *= 2 self.keys = [self.EMPTY] * self.capacity self.values = [None] * self.capacity self.size = 0 for i in range(len(old_keys)): if old_keys[i] not in (self.EMPTY, self.DELETED): self.put(old_keys[i], old_values[i]) # Test all three probe types for method in ['linear', 'quadratic', 'double']: ht = OpenAddressHashTable(capacity=7, probe=method) for k in [7, 14, 21, 3, 10]: ht.put(k, k * 10) print(f"{method}: get(14)={ht.get(14)}, get(99)={ht.get(99)}") ht.delete(14) print(f" After delete 14: get(14)={ht.get(14)}, get(21)={ht.get(21)}")

The Tombstone Problem

Deletion in open addressing cannot simply empty a slot — that would break probe chains for keys inserted after the deleted one. Solution: mark deleted slots with a tombstone (DELETED sentinel).

Before delete(14)	[7, 14, 21, 3, _, _, _]
Naive empty slot	[7, _, 21, 3, _, _, _]
Search for 21: h(21)=0	taken(7) → probe 1 → EMPTY → "not found"! WRONG!
With tombstone	[7, DEL, 21, 3, _, _, _]
Search for 21: h(21)=0	taken(7) → probe 1 → DELETED (continue) → found 21! ✓

Tombstone drawback: Over time, many tombstones accumulate and degrade search performance. Periodic rehashing (resize without growing) cleans them up.

Performance Comparison

Method	Avg Probes (Success, α=0.5)	Avg Probes (Failure, α=0.5)	Clustering
Linear	1.5	2.5	Primary + Secondary
Quadratic	1.44	2.19	Secondary only
Double Hashing	1.39	2.0	None

At α = 0.7:

Method	Success	Failure
Linear	2.17	6.06
Quadratic	1.85	3.82
Double	1.72	3.33

C++ Implementation (Linear Probing)

Example

#include <vector> #include <optional> #include <iostream> using namespace std; class LinearProbingMap { enum State { EMPTY, OCCUPIED, DELETED }; struct Slot { int key; int value; State state = EMPTY; }; vector<Slot> table; int capacity, count; public: LinearProbingMap(int cap = 16) : capacity(cap), count(0), table(cap) {} void put(int key, int value) { if (count >= capacity * 0.7) resize(); int idx = key % capacity; while (table[idx].state == OCCUPIED && table[idx].key != key) idx = (idx + 1) % capacity; if (table[idx].state != OCCUPIED) count++; table[idx] = {key, value, OCCUPIED}; } optional<int> get(int key) { int idx = key % capacity; while (table[idx].state != EMPTY) { if (table[idx].state == OCCUPIED && table[idx].key == key) return table[idx].value; idx = (idx + 1) % capacity; } return nullopt; } void remove(int key) { int idx = key % capacity; while (table[idx].state != EMPTY) { if (table[idx].state == OCCUPIED && table[idx].key == key) { table[idx].state = DELETED; count--; return; } idx = (idx + 1) % capacity; } } private: void resize() { auto old = move(table); capacity *= 2; table.assign(capacity, Slot{}); count = 0; for (auto& s : old) if (s.state == OCCUPIED) put(s.key, s.value); } };

Real-World Usage

Python dict: Uses open addressing with a custom probe sequence (perturbed by hash bits)
Rust HashMap: Robin Hood hashing (linear probing variant with displacement)
Google's dense_hash_map: Quadratic probing optimized for cache
Game engines: Linear probing preferred for cache performance with small load factors

Key Takeaways

Open addressing stores everything in a flat array — excellent cache locality, no pointer overhead, but requires careful load factor management (keep α < 0.7). Linear probing is fastest but clusters. Quadratic probing eliminates primary clustering. Double hashing eliminates all clustering but costs an extra hash. Tombstones are necessary for deletion but accumulate — periodic rehashing is the cure. Choose open addressing when memory efficiency and cache performance are priorities.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Open Addressing.

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, open, addressing

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.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.Advanced TopicsBit Manipulation - Advanced TechniquesMaster bit manipulation techniques, bitwise operations, bit masking, and advanced binary algorithms for competitive programming and interviews.

PreviousHashing Interview Problems NextBubble Sort - Simple Sorting Algorithm

DSA Notes

Open Addressing

Master open addressing for hash tables — linear probing, quadratic probing, double hashing, the clustering problem, deletion with tombstones, and complete implementations.

How Open Addressing Works

The probe sequence for key k is: h(k,0), h(k,1), h(k,2), ... where h(k,i) gives the i-th slot to check. Different probing methods define different sequences.

Linear Probing

The simplest approach: if slot h(k) is occupied, try h(k)+1, then h(k)+2, and so on (wrapping around).

h(k, i) = (h(k) + i) mod m

Table size m=7. Insert keys	7, 14, 21, 3
h(7) = 7 % 7 = 0	slot 0 free → place 7
h(14) = 14 % 7 = 0	slot 0 taken → try 1 → free → place 14
h(21) = 21 % 7 = 0	slot 0 taken → 1 taken → try 2 → free → place 21
h(3) = 3 % 7 = 3	slot 3 free → place 3
Table	[7, 14, 21, 3, _, _, _]

The Clustering Problem

Linear probing suffers from primary clustering: occupied slots form contiguous blocks. New keys hashing near a cluster join and extend it, making the cluster grow faster.

Example

Before: [X, X, X, X, _, _, _, X, X, _] ↑ cluster of 4 Any key hashing to indices 0,1,2,3,4 will join this cluster. That's 5/10 = 50% of keys! The cluster grows quadratically.

Despite clustering, linear probing has excellent cache performance (sequential memory access) and is the fastest method for low load factors (α < 0.5).

Quadratic Probing

Spreads probes more by using quadratic steps: h(k, i) = (h(k) + c₁i + c₂i²) mod m

Common choice: h(k, i) = (h(k) + i²) mod m

Probe 0	slot 3
Probe 1	slot (3 + 1) % 11 = 4
Probe 2	slot (3 + 4) % 11 = 7
Probe 3	slot (3 + 9) % 11 = 1
Probe 4	slot (3 + 16) % 11 = 8

Eliminates primary clustering — different initial hashes produce different probe sequences. However, keys with the same hash still follow the same quadratic sequence (secondary clustering).

Caveat: Quadratic probing does not guarantee visiting all slots. For full coverage, table size must be prime and α < 0.5, OR use (h + i(i+1)/2) mod 2^k with power-of-2 table size.

Double Hashing

Uses a second hash function to determine the probe step size:

h(k, i) = (h₁(k) + i × h₂(k)) mod m

python example

# h1(k) = k % m
# h2(k) = 1 + (k % (m-1))   — ensures h2 is never 0

# Key=14, m=7:
# h1(14) = 0, h2(14) = 1 + (14 % 6) = 3
# Probe sequence: 0, 3, 6, 2, 5, 1, 4 — visits ALL slots!

No clustering at all — each key has its own unique probe sequence. This gives the best distribution but costs an extra hash computation per probe.

Complete Python Implementation

Example

The Tombstone Problem

Deletion in open addressing cannot simply empty a slot — that would break probe chains for keys inserted after the deleted one. Solution: mark deleted slots with a tombstone (DELETED sentinel).

Before delete(14)	[7, 14, 21, 3, _, _, _]
Naive empty slot	[7, _, 21, 3, _, _, _]
Search for 21: h(21)=0	taken(7) → probe 1 → EMPTY → "not found"! WRONG!
With tombstone	[7, DEL, 21, 3, _, _, _]
Search for 21: h(21)=0	taken(7) → probe 1 → DELETED (continue) → found 21! ✓

Tombstone drawback: Over time, many tombstones accumulate and degrade search performance. Periodic rehashing (resize without growing) cleans them up.

Performance Comparison

Method	Avg Probes (Success, α=0.5)	Avg Probes (Failure, α=0.5)	Clustering
Linear	1.5	2.5	Primary + Secondary
Quadratic	1.44	2.19	Secondary only
Double Hashing	1.39	2.0	None

At α = 0.7:

Method	Success	Failure
Linear	2.17	6.06
Quadratic	1.85	3.82
Double	1.72	3.33

C++ Implementation (Linear Probing)

Example

Real-World Usage

Python dict: Uses open addressing with a custom probe sequence (perturbed by hash bits)
Rust HashMap: Robin Hood hashing (linear probing variant with displacement)
Google's dense_hash_map: Quadratic probing optimized for cache
Game engines: Linear probing preferred for cache performance with small load factors

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Open Addressing.

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, open, addressing

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousHashing Interview Problems NextBubble Sort - Simple Sorting Algorithm