Hash Map Hash-Flooding Attack — 2ms to 30s Latency

Every time you log into a website, your password isn't compared by scanning a list of millions of users one by one — that would take seconds. Instead, it's looked up in a hash table and found in a fraction of a millisecond. Hash tables power database indexes, caches, compilers, and the dictionaries in nearly every programming language you've ever used. They're one of the most practically impactful data structures in existence, yet most developers use them without truly understanding what's happening underneath.

How Hashing Actually Works — The Magic Formula Demystified

At its core, hashing is the process of converting any input — a string, an object, a number — into a fixed integer called a hash code. That hash code is then reduced (usually via the modulo operator) to fit within the array that backs your hash table. The slot in the array where your data lands is called a bucket.

Here's the critical insight: a good hash function is deterministic and uniform. Deterministic means the same input always produces the same output — 'alice@email.com' must always hash to bucket 42, never bucket 17 on Tuesdays. Uniform means the outputs are spread across all available buckets as evenly as possible, so you don't end up with 900 items crammed into bucket 3 while buckets 4 through 100 sit empty.

In Java, every object inherits a hashCode() method from Object. Strings compute their hash by multiplying each character's Unicode value through a polynomial, which gives decent distribution. The HashMap class takes that hash code and uses bit-manipulation tricks to map it to a bucket index. You never see this machinery, but it runs on every single put() and get() call you make.

Visual Diagram: How a Hash Function Maps Keys to Buckets

The diagram below illustrates the process a hash table follows when you insert a key-value pair. The key is first passed through a hash function, which produces an integer (the hash code). That integer is then reduced via modulo to fit within the bucket array. The result is the index where the entry is stored. If two keys produce the same index, a collision occurs — how the table handles that is covered in the next section.

Collision Handling — What Happens When Two Keys Land in the Same Bucket

No matter how brilliant your hash function is, collisions are mathematically inevitable. With enough keys and a finite number of buckets, two different keys will eventually map to the same bucket. 'John' and 'Mary' might both hash to bucket 7. Your hash table must have a strategy for this.

The two dominant approaches are Separate Chaining and Open Addressing. Separate chaining means each bucket holds a linked list (or in Java 8+, a balanced tree once the list grows past 8 nodes). When a collision occurs, the new entry is simply appended to the list at that bucket. Lookup then requires iterating that short list to find the right key. In practice, with a good load factor, these chains stay length 1 or 2.

Open addressing takes a different approach: when a collision occurs, the algorithm probes for the next available bucket using a defined sequence (linear probing, quadratic probing, or double hashing). Everything stays in the same array — no external lists. This is more cache-friendly but degrades faster when the table fills up.

Java's HashMap uses separate chaining. The key takeaway: collisions don't break a hash table — they just slow it down if they pile up too much. The load factor (entries divided by bucket count) is your early warning system.

Visual Diagram: Chaining vs Open Addressing Collision Resolution

The two main strategies for handling collisions differ in how they store multiple keys that land in the same bucket. Separate chaining stores a linked list (or tree) at each bucket, so all colliding entries are kept in the same bucket. Open addressing stores all entries within the array itself — when a collision occurs, it probes forward to find the next empty slot. The diagram below contrasts these two approaches for three keys that all originally map to bucket index 2.

HashMap vs HashTable in Java — The Practical Difference That Matters

Java has two classes that often confuse people: HashMap and HashTable (the older one). They feel interchangeable but they're not, and picking the wrong one can cause subtle bugs in multi-threaded code or hurt performance in single-threaded code.

HashTable is synchronized — every method acquires a lock before executing. This makes it thread-safe but painfully slow in single-threaded applications because you're paying synchronization overhead for nothing. It was the original Java 1.0 implementation, and the API has quirks: it doesn't allow null keys or null values, throwing a NullPointerException instead.

HashMap is unsynchronized, allows one null key and multiple null values, and is significantly faster in single-threaded contexts. It's the right default choice for the vast majority of code. When you do need thread safety, don't reach for HashTable — use ConcurrentHashMap instead. ConcurrentHashMap locks only individual bucket segments rather than the entire table, giving you thread safety without the bottleneck.

LinkedHashMap is worth knowing too: it wraps HashMap with a doubly-linked list that maintains insertion order, making it perfect for LRU caches. TreeMap orders by key but sacrifices O(1) for O(log n) — use it when sorted iteration matters more than raw speed.

Why HashMap is O(1) — And When It Quietly Becomes O(n)

The O(1) average-case performance of a hash map is one of the most cited facts in computer science — and one of the most misunderstood. It's not O(1) because the computer is magic. It's O(1) because the hash function computes the exact memory address of the bucket directly, skipping all comparison. No matter how many items are in the table, we always do the same three steps: hash the key, find the bucket, return the value.

But 'average case' is doing a lot of heavy lifting in that sentence. The worst case is O(n), and it happens when all keys collide into the same bucket, turning your hash table into a linked list. This can occur accidentally with a poor hash function or maliciously in a hash-flooding denial-of-service attack (where an attacker deliberately sends inputs that collide).

Java 8 introduced an important defence: when a bucket's chain exceeds 8 entries, it converts from a linked list to a red-black tree. This caps the worst case at O(log n) per bucket instead of O(n), making hash-flooding far less damaging. This is why your HashMap's performance stays predictable under adversarial conditions — the JDK engineers thought about this so you don't have to.

The practical lesson: keep your load factor below 0.75, ensure your key objects have well-distributed hashCode() implementations, and always override equals() alongside hashCode() — they're a contract in Java, not optional companions.

C++ std::unordered_map Implementation — Same Theory, Different Syntax

While Java's HashMap is the most common example for hash maps in the JVM world, C++ developers use std::unordered_map. The core concepts are identical: a hash function maps keys to buckets, collisions are resolved via separate chaining, and a load factor triggers rehashing. But the C++ standard library gives you more control over the hash function, the bucket count, and even the hash policy.

In C++, std::unordered_map is a hash-table-based associative container. It uses a default hash function from the <functional> header, but you can specialize std::hash for your custom types or provide a custom hash functor. The container also exposes direct bucket-level APIs: bucket_count(), bucket_size(), and bucket(key) let you inspect how items are distributed.

The same pitfalls apply: a poor hash function turns O(1) into O(n). C++ doesn't automatically treeify long chains — if you have many collisions, every lookup scans the entire bucket's linked list. However, you can control the max_load_factor and potentially trigger an early rehash to mitigate the issue.

Resizing and Load Factor — When HashMap Rewrites Itself

Hash tables cannot grow indefinitely within a fixed array. When the number of entries exceeds the load factor threshold (default 0.75 in Java), the HashMap resizes: it doubles the bucket array and rehashes every existing entry into the new table. This operation is O(n) and can cause a latency spike if it happens during a critical request.

The load factor is a trade-off. A lower load factor (e.g., 0.5) means fewer collisions and faster lookups but wastes memory. A higher load factor (e.g., 1.0) saves memory but increases collision probability and slows lookups. Java settled on 0.75 as the empiricial sweet spot — a balance that keeps chains short while not wasting too much space.

You can control resizing by setting the initial capacity in the constructor: new HashMap<>(expectedSize). If you know you'll store 10,000 entries, set the initial capacity to 13,334 (10,000 / 0.75) to avoid resizing entirely. This is a common optimisation in high-throughput services where predictability matters.

Advantages and Disadvantages: Hash Table vs BST vs Array

When choosing a data structure for a key-value lookup or collection, it's important to understand the trade-offs between hash tables, balanced binary search trees, and simple arrays. The table below breaks down the key differences across several dimensions.

In practice: use a hash table when you need fast single-key lookups and don't need ordering. Use a BST when you need ordered traversal or range queries. Use a sorted array when your data is static and you want minimal memory overhead.

Practice Problems to Master Hash Tables

The best way to internalize hash table usage is to solve problems that require O(1) lookups. Below are a curated set of problems, ranging from easy to hard, that test different aspects of hash map knowledge — from simple frequency counting to two-pointer plus hash strategies.

1. Two Sum (Easy)
2. Given an array of integers, return indices of the two numbers that add up to a target.
3. [LeetCode](https://leetcode.com/problems/two-sum/) — Classic hash map usage: store each element's value and its index, check for complement.
4. Valid Anagram (Easy)
5. Given two strings, determine if they are anagrams.
6. [LeetCode](https://leetcode.com/problems/valid-anagram/) — Use a hash map to count frequencies or a fixed-size array for lowercase letters.
7. Longest Consecutive Sequence (Medium)
8. Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
9. [LeetCode](https://leetcode.com/problems/longest-consecutive-sequence/) — Use a hash set to allow O(1) lookups while building sequences.
10. Group Anagrams (Medium)
11. Given an array of strings, group anagrams together.
12. [LeetCode](https://leetcode.com/problems/group-anagrams/) — Use a hash map with sorted character string as key.
13. Subarray Sum Equals K (Medium)
14. Given an array of integers, find the total number of continuous subarrays whose sum equals k.
15. [LeetCode](https://leetcode.com/problems/subarray-sum-equals-k/) — Use a hash map to store cumulative sum frequencies.
16. Top K Frequent Elements (Medium)
17. Given an array of integers, return the k most frequent elements.
18. [LeetCode](https://leetcode.com/problems/top-k-frequent-elements/) — Use a hash map for frequency counting then a bucket sort or heap.
19. Encode and Decode TinyURL (Medium)
20. Design a URL shortening service.
21. [LeetCode](https://leetcode.com/problems/encode-and-decode-tinyurl/) — Use a hash map to store long-to-short and short-to-long mappings.
22. LRU Cache (Medium/Hard)
23. Design a data structure that follows the LRU (Least Recently Used) cache policy.
24. [LeetCode](https://leetcode.com/problems/lru-cache/) — Combines a hash map with a doubly-linked list for O(1) operations.

Frequently Asked Questions