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
Understand 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.
What is Hashing?
Hashing is a technique that maps data of arbitrary size to fixed-size values (hash codes), enabling near-constant-time insertion, deletion, and lookup. A hash table (also called hash map or dictionary) uses a hash function to compute an index into an array of buckets, where the desired value can be found.
Think of it like a library with a magical catalog system: instead of searching through every shelf, you compute a formula from the book title that tells you exactly which shelf to check. Most of the time, you find the book immediately.
The Hash Table Structure
| Key | hash_function(key) → index → bucket[index] → value |
| hash("apple") = 3 | table[3] = "apple: red fruit" |
| hash("banana") = 5 | table[5] = "banana: yellow fruit" |
| hash("cherry") = 1 | table[1] = "cherry: small red fruit" |
| table | [_, "cherry:...", _, "apple:...", _, "banana:...", _] |
Core Operations and Their Complexity
| Operation | Average Case | Worst Case | Notes |
|---|---|---|---|
| Insert | O(1) | O(n) | Worst case: all keys hash to same index |
| Search | O(1) | O(n) | Average assumes good hash function |
| Delete | O(1) | O(n) | Same reasoning as search |
The "O(1) average" depends on two things:
- A good hash function that distributes keys uniformly
- A load factor that stays below a threshold
How a Hash Table Works
Insertion
- Compute
index = hash(key) % table_size - Store the (key, value) pair at
table[index] - If there is already something at that index (collision), handle it (chaining or probing)
Lookup
- Compute
index = hash(key) % table_size - Go to
table[index] - If the key matches, return the value
- If collision handling was used, search through the chain/probe sequence
Deletion
- Find the key (same as lookup)
- Remove it from the bucket/slot
- Handle any structural cleanup (e.g., tombstone markers in open addressing)
Load Factor
The load factor α = n/m, where n = number of stored elements and m = table size.
- α < 0.7 → good performance for open addressing
- α < 1.0 → reasonable for chaining
- α > 1.0 → guaranteed collisions (only possible with chaining)
When α exceeds a threshold, we resize (typically double) the table and rehash all elements. This keeps operations at O(1) amortized.
python example
# Load factor calculation
n = 15 # elements stored
m = 20 # table size
alpha = n / m # 0.75
# Time to resize! Most implementations resize at α = 0.75
# New table: m = 40, rehash all 15 elements
# New α = 15/40 = 0.375 — plenty of roomPython Implementation from Scratch
Example
class HashTable:
def __init__(self, initial_size=8):
self.size = initial_size
self.count = 0
self.table = [[] for _ in range(self.size)] # chaining
def _hash(self, key):
return hash(key) % self.size
def _resize(self):
old_table = self.table
self.size *= 2
self.table = [[] for _ in range(self.size)]
self.count = 0
for bucket in old_table:
for key, value in bucket:
self.put(key, value)
def put(self, key, value):
if self.count / self.size >= 0.75:
self._resize()
index = self._hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value) # update
return
self.table[index].append((key, value)) # insert
self.count += 1
def get(self, key):
index = self._hash(key)
for k, v in self.table[index]:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
index = self._hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index].pop(i)
self.count -= 1
return
raise KeyError(key)
# Usage
ht = HashTable()
ht.put("name", "Alice")
ht.put("age", 30)
print(ht.get("name")) # "Alice"
ht.delete("age")
C++ Implementation
Example
#include <vector>
#include <list>
#include <string>
#include <iostream>
using namespace std;
class HashTable {
int size;
int count;
vector<list<pair<string, int>>> table;
int hashFunc(const string& key) {
int hash = 0;
for (char c : key) hash = hash * 31 + c;
return abs(hash) % size;
}
public:
HashTable(int sz = 16) : size(sz), count(0), table(sz) {}
void put(const string& key, int value) {
int idx = hashFunc(key);
for (auto& [k, v] : table[idx]) {
if (k == key) { v = value; return; }
}
table[idx].push_back({key, value});
count++;
}
int get(const string& key) {
int idx = hashFunc(key);
for (auto& [k, v] : table[idx])
if (k == key) return v;
return -1; // not found
}
void remove(const string& key) {
int idx = hashFunc(key);
table[idx].remove_if([&](const pair<string,int>& p) {
return p.first == key;
});
count--;
}
};
Why Hashing is Everywhere
Hash tables are arguably the most important data structure in practical computing:
- Python dict, JavaScript object/Map, Java HashMap, C++ unordered_map — all hash tables
- Database indexing: Hash indexes for equality queries
- Caching: Memcached, Redis use hashing for key-value storage
- Compilers: Symbol tables mapping variable names to metadata
- Networking: Hash tables for connection tracking, routing tables
- Deduplication: Detect duplicate files/records via hash comparison
- Load balancing: Consistent hashing distributes requests across servers
Hash Table vs Other Data Structures
| Structure | Search | Insert | Delete | Ordered? |
|---|---|---|---|---|
| Hash table | O(1) avg | O(1) avg | O(1) avg | No |
| BST (balanced) | O(log n) | O(log n) | O(log n) | Yes |
| Sorted array | O(log n) | O(n) | O(n) | Yes |
| Linked list | O(n) | O(1) | O(n) | No |
Choose hash tables when you need fast lookup/insert and do not need ordering. Choose BSTs when you need range queries or sorted traversal.
Common Pitfalls
- Bad hash function: If many keys map to the same bucket, performance degrades to O(n)
- Not handling resize: Without dynamic resizing, load factor grows unbounded
- Mutable keys: If a key changes after insertion, its hash changes and lookup fails
- Hash flooding attacks: Adversarial inputs causing worst-case O(n) in web servers (mitigated by randomized hashing)
Key Takeaways
Hashing provides O(1) average-case operations by converting keys into array indices. The magic relies on good hash functions and controlled load factors. Hash tables are the default choice for key-value lookup in virtually every programming language and system. Understanding how they work internally — including collision handling and resizing — is essential for both interviews and systems design.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Hashing Fundamentals.
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, introduction, hashing fundamentals
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 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.ArraysArrays - Fundamental Data StructureLearn array basics, structure, operations, and properties as the foundation of data structures.