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
Explore hash function design — division method, multiplication method, universal hashing, polynomial rolling hash, and properties that make a hash function effective.
What Makes a Good Hash Function?
A hash function maps keys from a large universe (all possible strings, integers, etc.) to a small range [0, m-1] where m is the table size. A good hash function should:
- Deterministic: Same key always produces same hash
- Uniform distribution: Keys spread evenly across buckets (minimizes collisions)
- Efficient to compute: O(1) or O(key_length) at most
- Avalanche effect: Small changes in key produce vastly different hashes
- Minimize clustering: Similar keys should not map to adjacent slots
Division Method
The simplest hash function: h(k) = k mod m
python example
def hash_division(key, table_size):
return key % table_sizeChoosing m: The table size matters greatly.
- Bad: m = power of 2 (e.g., 1024) — only the lowest bits of the key matter. Keys with similar low bits cluster.
- Bad: m = even number — odd and even keys separate into distinct halves.
- Good: m = prime not close to a power of 2 — distributes keys more uniformly.
Example
m = 7 (prime):
h(14) = 0, h(21) = 0, h(28) = 0 ← multiples of 7 still cluster!
m = 701 (prime, not near 2^k):
Much better distribution for general-purpose keys
Multiplication Method
h(k) = floor(m × (k × A mod 1)) where A is a constant 0 < A < 1.
Knuth recommends A = (√5 - 1)/2 ≈ 0.6180339887 (the golden ratio conjugate).
python example
import math
def hash_multiplication(key, table_size):
A = 0.6180339887 # golden ratio conjugate
fractional_part = (key * A) % 1 # extract fractional part
return int(table_size * fractional_part)
# Examples with table_size = 16:
# h(1) = floor(16 × 0.618) = 9
# h(2) = floor(16 × 0.236) = 3
# h(3) = floor(16 × 0.854) = 13
# h(4) = floor(16 × 0.472) = 7
# Beautiful spread! No clustering.Advantage: The value of m does not matter — works well even with powers of 2. This is why multiplication method is preferred in practice when table size is a power of 2.
Polynomial Rolling Hash (For Strings)
For string keys, treat each character as a coefficient in a polynomial:
h(s) = (s[0]×p^(n-1) + s[1]×p^(n-2) + ... + s[n-1]×p^0) mod m
python example
def hash_polynomial(key, table_size, p=31):
"""
p = small prime (31 or 37 for lowercase letters, 53 for mixed case)
"""
hash_value = 0
p_power = 1
for char in key:
hash_value = (hash_value + (ord(char) - ord('a') + 1) * p_power) % table_size
p_power = (p_power * p) % table_size
return hash_value
# Example: hash("abc") with p=31, m=1000000007
# = 1×1 + 2×31 + 3×961 = 1 + 62 + 2883 = 2946Rolling property: When computing hashes of all substrings (e.g., Rabin-Karp pattern matching), you can compute the next hash from the previous one in O(1) by subtracting the outgoing character and adding the incoming one.
Java's String hashCode (Real-World Example)
Java uses: h = s[0]×31^(n-1) + s[1]×31^(n-2) + ... + s[n-1]
Example
// Java's actual implementation:
public int hashCode() {
int h = 0;
for (int i = 0; i < value.length; i++) {
h = 31 * h + value[i];
}
return h;
}
Why 31? It is an odd prime, and 31 × i can be optimized as (i << 5) - i by the compiler.
Universal Hashing
No single hash function is safe against adversarial inputs. Universal hashing randomly selects a hash function from a family at runtime:
h_{a,b}(k) = ((a×k + b) mod p) mod m
where:
- p is a prime larger than the key universe
- a is random in [1, p-1]
- b is random in [0, p-1]
Example
import random
class UniversalHash:
def __init__(self, table_size, prime=104729):
self.m = table_size
self.p = prime
self.a = random.randint(1, self.p - 1)
self.b = random.randint(0, self.p - 1)
def hash(self, key):
return ((self.a * key + self.b) % self.p) % self.m
# Property: For any two distinct keys k1, k2:
# Pr[h(k1) = h(k2)] ≤ 1/m
# This guarantees good average behavior regardless of input distribution!
Why it matters: Prevents hash-flooding DoS attacks. Even if an attacker knows the algorithm, they cannot predict which function was chosen.
Tabulation Hashing
Split the key into bytes, look up each byte in a random table, and XOR the results:
Example
import random
class TabulationHash:
def __init__(self, table_size):
self.m = table_size
# 4 tables of 256 random values (for 32-bit keys split into 4 bytes)
self.tables = [[random.getrandbits(64) for _ in range(256)] for _ in range(4)]
def hash(self, key):
h = 0
for i in range(4):
byte = (key >> (8 * i)) & 0xFF
h ^= self.tables[i][byte]
return h % self.m
Fast (4 lookups + 3 XORs), high quality, and theoretically 3-wise independent.
Comparing Hash Functions
| Method | Speed | Distribution Quality | Table Size Restriction |
|---|---|---|---|
| Division | Very fast | Depends on m choice | m should be prime |
| Multiplication | Fast | Very good | None (works with 2^k) |
| Polynomial | O(key length) | Good for strings | None |
| Universal | Fast | Guaranteed uniform (probabilistic) | None |
| Tabulation | Very fast | Excellent | None |
Cryptographic vs Non-Cryptographic Hashes
| Property | Hash Table Hash | Cryptographic Hash (SHA-256) |
|---|---|---|
| Speed | Very fast | Deliberately slow |
| Output size | Small (table index) | Fixed large (256 bits) |
| Reversible? | Not a concern | Must be infeasible |
| Collision resistance | Best effort | Cryptographically guaranteed |
| Use case | Data structures | Security, integrity |
For hash tables, we do NOT need cryptographic hashes — they are too slow. We need fast functions with good distribution.
Practical Guidelines
- Integer keys: Use multiplication method with golden ratio, or
(key * 2654435769) >> (32 - log2(m))for power-of-2 table sizes - String keys: Polynomial hash with p=31 (lowercase) or p=53 (mixed case)
- Composite keys: Combine component hashes:
hash = h1 * 31 + h2or XOR with rotation - Security-sensitive: Use universal or SipHash (Python 3.4+ default for strings)
Real-World Applications
- HashMap/dict implementations: Every standard library needs an efficient hash function
- Bloom filters: Use multiple hash functions for probabilistic set membership
- Consistent hashing: Load balancers distribute requests using hash ring
- Rabin-Karp string matching: Rolling polynomial hash enables O(n) pattern search
- Checksums: CRC32, xxHash for fast data integrity verification
Key Takeaways
The choice of hash function profoundly affects hash table performance. Division method is simple but table-size-sensitive. Multiplication method handles power-of-2 sizes elegantly. Polynomial hashing is the standard for strings. Universal hashing provides worst-case guarantees against adversarial inputs. Always match your hash function to your key type and security requirements.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Hash Functions.
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 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.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.