¶ Hash Tables
¶ Competitive programming
¶ Introduction to Hash Tables in Competitive Programming
If you spend long enough in competitive programming, you eventually notice something: the problems rarely reward brute force, and they almost never forgive inefficiency. The deeper you go, the more you start to value data structures not as abstract academic objects, but as living tools that determine whether your solution stands or falls. Amid all these tools—segment trees, heaps, balanced BSTs, tries—there is one structure that is deceptively simple, yet unbelievably powerful, and once mastered, it changes the way you solve problems forever.
That structure is the hash table.
The term might remind you of the early days learning programming—perhaps using a dictionary or map in Python, an unordered_map in C++, or a HashMap in Java. For many programmers, hash tables feel so familiar that they seem almost trivial. But competitive programming has a funny way of revealing the truth: what feels simple on the surface often hides profound depth underneath. Hashing is one of those domains that looks like kindergarten until you’re deep into it—and suddenly you’re dealing with collisions, custom hash functions, string hashing, randomized hashes, rolling hashes, perfect hashing, and clever tricks that feel almost magical when they work.
This course, made of one hundred detailed articles, aims to take you far beyond the surface-level idea of “store key-value pairs quickly.” It invites you into the real world of hashing—where hash tables become problem-solving weapons, where proper hashing saves you from TLE or WA, and where understanding collisions, distributions, and randomized behavior unlocks solutions that would otherwise feel impossible.
Before we begin this journey, let’s take a deep breath and explore why hash tables matter so profoundly in competitive programming, and what makes them so fascinating when viewed from the inside.
¶ Why Hash Tables Matter More Than You Think
If you’ve ever solved a problem where you needed instant lookups, fast inserts, or quick membership checks, chances are a hash table has already quietly saved you. But in competitive programming—where time is scarce and input sizes explode—hash tables aren't just conveniences; they are survival tools.
Whenever you're handling:
- frequency maps
- visited states in BFS/DFS
- memoization for DP
- storing sets of strings or large integers
- caching results
- handling large alphabets
- compressing states
- deduplicating values
- quick existence checks
- coordinate compression
- multisets via hashing
- pattern detection or substring queries
…hash tables play a starring role.
They are often the difference between O(n log n) and O(n), between passing and timing out, between an elegant 15-line solution and a complex workaround.
But the simple built-in hash tables that languages provide aren’t always enough. In real contests, especially those involving large constraints or tricky adversarial input, you often need deeper insights into how hash tables work internally. You need to understand:
- collision behavior
- the importance of good hash functions
- how to avoid worst-case slowdowns
- when to use randomization
- how to prevent hacking on platforms like Codeforces
- how to safely hash composite objects
- how to hash grids, pairs, or custom structs
- how to store states of large combinatorial problems
- how to design hash tables for problems involving strings or rolling patterns
Once you understand these details, the hash table stops being a black box and becomes a powerful extension of your algorithmic intuition.
¶ The Art and Science of Hashing
Hash tables are not just data structures—they are a form of algorithmic art. You take something large, complex, and often unwieldy, and transform it into a neat little index managed by a hash function. A good hash function feels almost like a compression superpower: it distills huge objects into tiny integers that can be compared or stored efficiently. But this transformation is risky. If two different objects produce the same hash, you have a collision. And collisions can be harmless—or disastrous.
Part of mastering hash tables is learning how to reduce the risk of harmful collisions, how to design resilient hash functions, and how to let randomness work in your favor without turning your solution into a lottery ticket.
You’ll explore:
- polynomial rolling hash functions
- double hashing
- splitmix64 and other robust hash generators
- universal hashing
- custom hashers for pairs and structs
- multiplicative hashing tricks
- XOR-based hashing
- randomized probing
- collision-resistant hashing for strings
Each of these concepts opens the door to solving more advanced problems—and doing so with confidence instead of fear of hidden pitfalls.
¶ Hash Tables as a Competitive Edge
Many high-rated contestants will tell you that hashing becomes one of their competitive edges. It's not uncommon to see solutions where a brute-force approach gets magically upgraded into something efficient simply by storing intermediate values in a hash table. Some problems even become trivial once you realize you can hash the necessary states.
Hash tables help with:
- two-sum and k-sum–style tricks
- matching problems
- storing reachable states in DP
- substring comparisons in constant time
- finding repeated patterns
- checking isomorphisms between trees or graphs
- detecting cycles in sequences
- multi-source constraints
- fast frequency or parity checks
- hashing subsets or paths
They provide the flexibility of a set or map, but at far greater speed and often with more freedom to design your own structure.
Hash tables also open doors to techniques like:
- string hashing (fundamental for problems involving substrings)
- 2D hashing (useful for pattern matching in matrices)
- hashing tree shapes (identifying subtrees by their hashed structure)
- hashing cycles or permutations
- hashing vectors, paths, or general sequences
These techniques show up often in problems involving pattern matching, graph isomorphism, string algorithms, and state compression. Without hashing, many of these problems feel untouchable. With it, they suddenly fall into place.
¶ The Dark Side: Collisions and Adversarial Inputs
Once you’ve coded long enough, you encounter cases where your hash table behaves strangely. Maybe your unordered_map solution starts TLE-ing for no obvious reason. Maybe your string hashing solution produces false positives. Maybe your carefully hashed states collide and send your DP into chaos.
This isn’t bad luck. It’s part of the territory.
Understanding collisions is essential for mastering hash tables. In contests, especially on platforms where input can be adversarially crafted, hash tables can be hacked if you aren't careful.
A poorly designed hash function can degrade from O(1) to O(n) per operation under bad input. That’s catastrophic.
Languages like C++ even carry warnings about unordered_map being hackable unless you use custom hashers. Python’s dict uses randomized seeds internally to mitigate this risk, but even that isn’t always enough.
So in this course, you’ll learn:
- why collisions occur even with “good” hashing
- how to design hash functions that avoid predictable patterns
- how to combine multiple hashes
- how to use randomness safely and effectively
- how to resolve collisions gracefully
- how to avoid hash-flooding attacks in contests
- how to handle hashing in problems with extreme constraints
Once you know how to guard against adversarial behavior, you’ll trust your hash tables wholeheartedly.
¶ Hash Tables in String Problems
One of the most influential applications of hashing in competitive programming is string hashing. Strings are everywhere—DNA sequences, logs, user inputs, commands, test cases, pattern matching. Many problems require comparing substrings quickly, checking equality across large strings, or computing repeated patterns.
A naive comparison costs O(n).
A rolling hash comparison costs O(1).
That’s the kind of improvement that wins contests.
By exploring string hashing deeply, you learn about:
- base and modulus choices
- preventing collisions with double hashing
- modular arithmetic tricks
- precomputing prefix hashes
- comparing substrings in constant time
- detecting palindromes with hashing
- Z-function vs. rolling hash comparisons
- substring search with Rabin–Karp
- using randomization effectively
You’ll also revisit some classic themes:
- polynomial hashing
- large moduli vs. unsigned 64-bit
- how to avoid overflow traps
- choosing between deterministic and probabilistic approaches
String hashing alone is a universe worth exploring, and it forms a significant segment of this course.
¶ Hashing Beyond Strings: Graphs, Trees, and States
As you grow more comfortable with hashing, you start applying it to more abstract objects:
- hashing tree structures to identify isomorphic subtrees
- hashing graphs to compare shapes or patterns
- hashing DP states in high-dimensional problems
- hashing subarrays or multidimensional data
- hashing configurations in puzzles
- hashing positions in games or simulations
These techniques allow you to convert large or complicated objects into manageable integers that fit nicely inside maps or sets.
One particularly beautiful application is tree hashing, where entire tree shapes are encoded as hashes. This technique appears often in problems involving subtree equivalence, canonical forms, or clustering. Another deep application is state hashing, where you store visited configurations of a system—like board states, permutations, or bitmask-based systems—inside a hash table.
Once you become fluent in these techniques, you will see hashing as a universal language that compresses complexity into something manageable.
¶ The Importance of Good Implementation
Hash tables are forgiving only when used thoughtfully. A naive implementation can lead to mysterious bugs, inefficiencies, or collisions that ruin your solution at the worst moment.
This course won’t simply show you how to use built-in hash tables—it will teach you:
- how to implement a hash table from scratch
- how chaining works internally
- how open addressing works
- why probing strategies matter
- how to resize and rehash efficiently
- how to detect and prevent clustering
- how to properly seed randomness
- how to tune factors for competitive environments
Once you’ve built your own hash table—even a simple one—you begin to appreciate its inner workings. And that understanding makes you a far stronger problem solver.
¶ A Realistic Emotional Journey
Learning hashing deeply isn’t a straight line. You’ll have highs and lows—just like solving hard contest problems.
¶ First Stage: Confidence
You feel you already “know” hash tables because you’ve used unordered_map or dict many times.
¶ Second Stage: Realization
You discover that collisions aren’t myths. They can strike any time. Suddenly, built-in containers feel less magical.
¶ Third Stage: Curiosity
You begin experimenting with custom hashing, random seeds, and collision-resistant designs.
¶ Fourth Stage: Insight
You understand how hashing compresses complexity and why good designs are essential in contests.
¶ Fifth Stage: Mastery
At this stage, you reach reflexive competence. You no longer think “should I use a hash table here?”—you simply know.
This course is structured to guide you through these stages gracefully, in a way that feels empowering rather than overwhelming.
¶ Why Hash Tables Deserve 100 Articles
You may wonder why such a simple-seeming structure deserves an entire hundred-article course. The answer becomes clearer the deeper you go.
Hash tables are not one feature—they are an entire family of techniques, ideas, patterns, and algorithmic innovations:
- dictionary hashing
- rolling hashing
- perfect hashing
- universal hashing
- hash-based DP
- hash-based graph tricks
- hash-based substring search
- randomized algorithms
- hash collisions and mitigations
- efficient map/set tricks in contests
- hashing on constraints up to 10^6 or 10^7
- hashing multidimensional and composite objects
- implementing hash sets and maps manually
Each of these is a domain of its own. Together, they form a complete universe.
A hundred articles is not an exaggeration—it is an opportunity to explore hashing from every angle, with clarity, depth, and practical relevance.
¶ Before You Begin
Hash tables are simple enough that even a beginner can use them on day one, yet deep enough that experts still refine their understanding years later. That duality is what makes hashing so enchanting.
Before you begin this journey, remind yourself:
- You don’t have to memorize everything.
- You don’t need mathematical perfection to use hashing well.
- You will grow steadily as you experiment with real problems.
- Every collision, bug, or unexpected behavior will help you learn.
Most importantly, you’ll discover that hashing is not about fighting randomness—it’s about reshaping randomness into something powerful and controlled.
By the end of this course, you will see hash tables not as language features, but as personalized tools you can bend to your will. You will understand them deeply enough to trust them, modify them, and use them in the most demanding contest environments.
Whether you're solving string problems, graph problems, DP problems, or puzzle problems, hashing will soon become one of your favorite lenses for looking at challenges.
Let’s begin this journey with curiosity, creativity, and patience.
Welcome to the world of Hash Tables.
¶ Hash Tables
¶ Beginner Level
1. Introduction to Hash Tables in Competitive Programming
2. What is a Hash Table? Basic Concepts
3. Why Use Hash Tables?
4. Hash Functions: Introduction and Importance
5. Basic Operations in Hash Tables: Insert, Search, and Delete
6. Collision Handling in Hash Tables
7. Hashing with Chaining: Introduction and Implementation
8. Hashing with Open Addressing: Overview
9. Types of Hash Functions: Division Method
10. Understanding the Load Factor in Hash Tables
11. Basic Hash Table Applications in Competitive Programming
12. Simple Hash Functions: Modulo-Based Hashing
13. Basic Problem Solving with Hash Tables
14. Handling Collisions Using Linear Probing
15. Quadratic Probing for Collision Resolution
16. Double Hashing for Better Collision Handling
17. Hash Tables and Their Applications in Counting Frequencies
18. Hash Tables for Fast Lookups
19. Dynamic Resizing of Hash Tables
20. Implementing a Hash Table in C++ or Python
¶ Intermediate Level
21. Advanced Hash Functions: Universal Hashing
22. Rehashing: When and How to Resize a Hash Table
23. Perfect Hashing: Introduction and Methods
24. Using Hash Tables for Efficient Anagram Detection
25. Multi-Table Hashing: Hash Tables of Hash Tables
26. Handling Large Data Sets with Hash Tables
27. Using Hash Tables for Fast Set Operations
28. Hash Tables for Counting Substrings in a String
29. Using Hash Tables for Pair Sum Problems
30. Combining Hash Tables with Other Data Structures
31. Counting Distinct Elements Using Hash Tables
32. Finding Duplicates in an Array Using Hash Tables
33. Hashing Techniques for Searching in Multiple Arrays
34. Hash Tables in Graph Algorithms
35. Hashing for Range Queries and Interval Problems
36. Bucket Sort and Hash Tables: A Hybrid Approach
37. Implementing Hash Tables with Linked Lists for Chaining
38. Dealing with Large Integer Keys in Hash Tables
39. Efficient Search and Update in Dynamic Arrays Using Hash Tables
40. Hash Table Applications in Frequency Counting Problems
¶ Advanced Level
41. Consistent Hashing in Distributed Systems
42. Cryptographic Hash Functions: Introduction and Applications
43. Bloom Filters: A Space-Efficient Approximate Hashing Technique
44. Cuckoo Hashing: A Better Collision Resolution Scheme
45. Hash Tables in Data Mining Algorithms
46. Hash Tables in String Matching Algorithms
47. Counting Distinct Elements with Hash Tables
48. Hash Tables in Dynamic Connectivity Problems
49. Persistent Hash Tables and Their Applications
50. Sparse Hashing Techniques for Large Datasets
51. Advanced Collision Resolution Techniques
52. Perfect Hashing for Static Sets
53. Hash Tables in Machine Learning: Feature Hashing
54. Double Hashing vs Cuckoo Hashing: Comparison
55. Minimizing Collisions Using Multiple Hash Functions
56. Efficient Hashing for Range Queries
57. Hash Tables in Computational Geometry
58. Utilizing Hash Tables for Efficient Matrix Operations
59. Optimizing Hash Table Performance with Custom Hash Functions
60. Counting Inversions Using Hash Tables
61. Hash Tables for Path Finding in Graphs
62. Hash Tables in Geospatial Data Handling
63. Solving Sudoku with Hash Tables
64. Space Complexity of Hash Tables and Memory Management
65. Load Balancing in Hash Tables for Parallel Computing
66. Efficient Hash Table Implementations in Competitive Programming Languages
67. Space and Time Tradeoffs in Hash Tables
68. Using Hash Tables in Image Processing Algorithms
69. Bloom Filter Applications in Memory-Constrained Environments
70. Hashing and Sorting Techniques Combined
71. Advanced Hash Table Techniques for Solving Large-Scale Problems
72. Probabilistic Hashing: Theoretical Foundations and Applications
73. Rehashing Strategies for Optimal Performance
74. SimHash: A Technique for Similarity Estimation Using Hash Tables
75. Using Hash Tables in Network Flow Algorithms
76. Advanced Hashing for Large Scale Databases
77. Hash Tables in Online Algorithms and Data Streams
78. Efficient String Hashing and Rolling Hash
79. Modular Hashing in Cryptography
80. Custom Hash Functions for Special Data Types
81. Implementing Hash Tables for Sparse Matrices
82. Optimal Load Factor Selection in Hash Tables
83. Comparing Hash Table Implementations in Different Programming Languages
84. Applications of Hash Tables in Trie Structures
85. Implementing and Optimizing Hash Tables for Real-Time Systems
86. Handling String Keys in Hash Tables Efficiently
87. Dynamic Hash Tables with Limited Memory
88. Interval Hashing for Range Search Problems
89. Space-Efficient Hashing Techniques
90. Multi-Dimensional Hashing
91. Hash Tables in Text Compression Algorithms
92. Analysis of Hash Table Time Complexity
93. String Hashing in Competitive Programming
94. Hybrid Hashing: Combining Hash Tables with Other Data Structures
95. Probabilistic Hashing and Its Applications
96. Hash Tables for Graph Traversal and Search Algorithms
97. Efficient Implementation of Hash Tables in Contests
98. Disjoint Set Data Structures with Hash Tables
99. Applications of Hash Tables in Real-World Software Systems
100. Final Thoughts on Optimizing Hash Tables for Competitive Programming