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
A 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 Python
What a Hash Function Must Do
A hash function h: Keys → {0, 1, ..., m-1} converts any key to an integer in range [0, m-1] where m is the hash table size.
A good hash function has these properties:
- Deterministic:
h(k)always returns the same value for the same k - Uniform distribution: Each slot is equally likely for a random key
- Fast to compute: O(1) for integers, O(|key|) for strings
- Avalanche effect: Small change in key causes large change in hash (for cryptographic use)
Method 2 — Multiplication Method
python example
def h_multiplication(key, m, A=0.6180339887): # A = (√5 - 1) / 2 (golden ratio)
return int(m * ((key * A) % 1))The fractional part of key×A is extracted, then scaled to [0, m-1].
Advantage: m does not need to be prime. Any value of m works well.
Knuth's recommendation: A = (√5 - 1) / 2 ≈ 0.6180339887 (the golden ratio conjugate) gives excellent distribution empirically.
Method 3 — Universal Hashing
Universal hashing chooses a hash function randomly from a family, making it hard for an adversary to create worst-case inputs.
Example
import random
def make_universal_hash_function(m, p=10**9+7):
"""
Returns a hash function h(k) = ((a*k + b) mod p) mod m
for random a in [1, p-1] and random b in [0, p-1].
This family is 2-universal: for any two distinct keys k1, k2,
P[h(k1) == h(k2)] ≤ 1/m.
"""
a = random.randint(1, p - 1)
b = random.randint(0, p - 1)
def h(key):
return ((a * key + b) % p) % m
return h
h = make_universal_hash_function(100)
print(h(42), h(43), h(42)) # Different values, last equals first
Hash Functions for Strings
Polynomial Rolling Hash
The standard approach for strings. Treat the string as a polynomial:
Example
h("abc") = a×p² + b×p¹ + c×p⁰ (mod m)
where p is a prime base (commonly 31 or 37)
and m is the hash table size (commonly 10^9 + 7)
python example
def polynomial_hash(s, p=31, m=10**9 + 7):
"""
Polynomial rolling hash.
p=31: good for lowercase letters
p=37: good for alphanumeric
m=10^9+7: large prime prevents collisions
"""
h = 0
p_pow = 1
for char in s:
h = (h + (ord(char) - ord('a') + 1) * p_pow) % m
p_pow = (p_pow * p) % m
return h
print(polynomial_hash("abc")) # Some integer
print(polynomial_hash("bca")) # Different integer
print(polynomial_hash("abc")) # Same as first — deterministicdjb2 Hash (Fast, Popular)
python example
def djb2(s):
h = 5381
for char in s:
h = ((h << 5) + h) + ord(char) # h = h * 33 + c
return h
# Used in: GNU C library, PostgreSQL, many programming languagesFNV Hash (Fowler-Noll-Vo)
python example
def fnv1a(s):
"""FNV-1a hash — excellent avalanche effect, used in Go, Java."""
h = 2166136261 # FNV offset basis (32-bit)
for char in s:
h ^= ord(char)
h = (h * 16777619) % (2**32) # FNV prime
return hRabin-Karp Rolling Hash
For substring search, a rolling hash allows computing hash(s[i+1..i+k]) from hash(s[i..i+k-1]) in O(1):
Example
def rabin_karp_search(text, pattern):
"""
Find all occurrences of pattern in text using rolling hash.
Time: O(n + m) average, O(nm) worst case.
"""
n, m = len(text), len(pattern)
p, mod = 31, 10**9 + 7
p_pow_m = pow(p, m - 1, mod)
pattern_hash = 0
window_hash = 0
for i in range(m):
pattern_hash = (pattern_hash + (ord(pattern[i]) - ord('a') + 1) * pow(p, i, mod)) % mod
window_hash = (window_hash + (ord(text[i]) - ord('a') + 1) * pow(p, i, mod)) % mod
results = []
if window_hash == pattern_hash and text[:m] == pattern:
results.append(0)
for i in range(1, n - m + 1):
# Remove leftmost character, add new rightmost
window_hash = (window_hash - (ord(text[i-1]) - ord('a') + 1)) % mod
window_hash = (window_hash * pow(p, mod-2, mod)) % mod
window_hash = (window_hash + (ord(text[i+m-1]) - ord('a') + 1) * p_pow_m) % mod
if window_hash == pattern_hash and text[i:i+m] == pattern:
results.append(i)
return results
print(rabin_karp_search("abcabcabc", "abc")) # [0, 3, 6]
Cryptographic vs Non-Cryptographic Hashes
| Feature | Non-Cryptographic | Cryptographic |
|---|---|---|
| Speed | Very fast (ns) | Slow (μs-ms) |
| Security | Not collision-resistant | Collision-resistant |
| Reversible | Sometimes | No (one-way) |
| Use case | Hash tables, checksums | Passwords, digital signatures |
| Examples | djb2, FNV, MurmurHash | SHA-256, bcrypt, SHA-3 |
python example
# Non-cryptographic: Python's built-in hash()
print(hash("hello")) # Fast, but PREDICTABLE without randomization
# Cryptographic: hashlib
import hashlib
sha256 = hashlib.sha256("hello".encode()).hexdigest()
print(sha256) # "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"
# One-way: cannot reverse to get "hello" from thisPython's hash() Behavior
python example
# Python uses SipHash-1-3 for str, bytes, datetime (Python 3.4+)
# HASH RANDOMIZATION: hash() is different in each Python session!
print(hash("hello")) # 123456789 (different every run)
# This prevents HashDoS attacks (adversary crafting many collisions)
# Disable with PYTHONHASHSEED=0 (for reproducibility in testing)
# Numbers hash to themselves or their value:
print(hash(0) == hash(0.0) == hash(False)) # True — consistent
print(hash(1) == hash(1.0) == hash(True)) # True
# Custom objects need __hash__ and __eq__:
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __hash__(self):
return hash((self.x, self.y)) # Tuple hash
def __eq__(self, other):
return self.x == other.x and self.y == other.y
p1 = Point(1, 2)
p2 = Point(1, 2)
s = {p1, p2}
print(len(s)) # 1 — p1 and p2 are equal → deduplicatedSummary
| Hash Function | Speed | Distribution | Use Case | ||
|---|---|---|---|---|---|
| Division (key % m) | O(1) | Good with prime m | Simple integers | ||
| Multiplication | O(1) | Excellent | General integers | ||
| Universal | O(1) | Provably good | Security against adversarial input | ||
| Polynomial (strings) | O( | s | ) | Excellent | Strings, substrings |
| djb2 | O( | s | ) | Good | General strings |
| FNV-1a | O( | s | ) | Excellent | Strings in Go, Java |
| SHA-256 | O( | s | ) slow | Cryptographic | Passwords, signatures |
Key insight: A perfect hash function for all cases does not exist. Choose based on key type, required security level, and performance requirements.
*Next Lesson: Collision Handling*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Hash Functions — Design, Properties, and Common Implementations.
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, hash, functions
Related Data Structures & Algorithms Topics
Continue learning this concept
HashingSeparate Chaining — Complete Implementation and AnalysisMaster 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 HashMapHashingCollision 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.HashingHashing — 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.