Given an array of numbers and a target, return the positions of two numbers that add up to the target.

Walk the array once. For each number x, check whether target - x is already in a hash map that stores each earlier number and its index. If yes, return the two indexes. If not, store x and its index and move on. Time is O(n), because each lookup is O(1) on average. Memory is O(n) for the map. Without the map you would compare every pair, which is O(n²).

Group a list of words so that words that are anagrams of each other are together.

Use a hash map from a canonical key to a list of words. The key can be the word with its letters sorted, or a tuple of 26 letter counts. Add each word to the list for its key. The groups are the map's values. With n words of length up to L, sorting each word gives O(n × L log L) time. Counting letters gives O(n × L). Memory is O(n × L) for the stored words.

Return true if any value appears at least twice in an array.

Walk the array and keep a hash set of numbers seen so far. If the current number is already in the set, return true. Otherwise add it. If you finish without a repeat, return false. Time is O(n) on average and memory is O(n). Sorting first and comparing neighbours uses O(n log n) time and O(1) extra memory if you can sort in place.

Given an unsorted array of integers, find the length of the longest run of consecutive numbers, in O(n) time.

Put all numbers in a hash set. For each number x, if x - 1 is not in the set, x starts a run: count upwards while x + 1, x + 2, and so on are in the set, and track the longest. Each number is visited at most twice (once as a candidate start, once inside a run), so time is O(n) on average. Memory is O(n) for the set.

Hash Tables

Look things up by key in about one step. Hash maps, hash sets and frequency counting, plus how collisions and resizing work.

beginner25 minAsked oftenHash mapHash setHashingFrequency countingCollisions

Last reviewed 24 Oct 2026 · by TheLearningLoop Team

Read first: Data Structures & Algorithms: The Big Picture (blog post)

Progress is saved on this device. Create a free account to keep it everywhere.

On this page ▾

On this page

Key takeaways

A hash table turns a key into a bucket number, so lookup, insert and delete take O(1) on average.
Two keys can land in the same bucket. That is a collision, and the table handles it with chains or probing.
The worst case is O(n), and a hash table keeps no useful order. Use a tree when you need order.

When to use a hash table

Use a hash table (a hash map or a hash set) when you need:

Lookup by key in about one step: "the user with this ID", "the price of this product".
To count things: how many times each word, error or visitor appears (frequency counting).
To answer "have I seen this before?": removing duplicates, spotting a repeat, checking membership.
To group items by a key, such as orders by customer.
A cache or memo: remember an answer so you never compute it twice.
To make a slow nested loop into one pass: "for each item, is its partner already stored?"

Use something else when:

You need keys in sorted order, or range queries such as "all scores from 1,000 to 2,000": use a balanced tree.
You need a guaranteed worst case on untrusted input: a balanced tree gives O(log n) always.
Keys are small whole numbers in a known range: a plain array indexed by the key is simpler and faster.
You need items in insertion order: use an ordered map (Java LinkedHashMap, and Python's dict already keeps insertion order).

Do not build a hash table by hand. Every language has one (see the real-world section). Writing one is for learning and interviews.

How a hash table works

A hash table stores key and value pairs and finds a pair by its key without searching through the others.

A hash function turns a key into a number, and that number (modulo the number of buckets) says which bucket holds the key. The same key always gives the same bucket.

The steps for put("cat", 5):

Run the hash function on "cat" to get a number.
Take that number modulo the number of buckets to get a bucket index.
Go straight to that bucket and store the pair there.

Looking up "cat" repeats steps 1 and 2 and reads the bucket. No scan through other keys is needed, which is why it is O(1) on average.

Two things can go wrong, and tables handle both:

Collisions. Two different keys can land in the same bucket. The two main fixes are chaining (each bucket holds a small list, as in the demo below) and open addressing (if the bucket is taken, probe for the next free one).
Crowding. The load factor is items divided by buckets. When it passes a limit, the table allocates more buckets, usually double, and puts every key back using the new size. This is called rehashing.

A hash set is a hash table that stores only keys, with no values. It answers "is this in the set?"

Try it

Start with the animals. The demo uses a very simple hash: it adds up the character codes of the key. Real tables mix the bits far better, but the idea is the same.

Hash table

Step 1 of 1 · Press Space to play, arrow keys to step

Start from:

0cat
1bird
2dog
3empty

Start: a table with 4 buckets holding 3 keys. Use Put, Get or Delete above.

items:: 3
buckets:: 4
load factor:: 0.75
key checks:: 0

load factor = items / buckets. key checks = keys compared in this operation. The hash here just adds up character codes, so anagrams collide on purpose.

Speed

Things to try:

Put cat, then Put dog. Each lands in its own bucket, and Get cat takes one key check.
Pick Colliding words and Put cat. act and cat have the same letters, so the same hash, so they share a bucket. Get cat now needs 2 key checks.
Keep putting keys such as a, b, c and watch the load factor. When it passes 0.75 the buckets double and every key is re-placed.

Hash table operations: put, get and delete

Put. Hash the key, pick the bucket, and add the pair. If the key is already there, replace its value instead. If the load factor is now too high, grow and rehash.

Get. Hash the key, pick the bucket, and compare the key with each item in the bucket until one matches. With short chains that is one or two comparisons.

Delete. Find the pair the same way and remove it. In open addressing, tables mark the slot as deleted instead of emptying it, so later probes do not stop too early.

Frequency counting. Use the item as the key and a number as the value. For each item, add one to its count. One pass over n items costs O(n).

Interview fact. A hash table gives O(1) on average, but O(n) in the worst case, when every key collides. It also keeps no useful order, so "smallest key" or "all keys between a and b" is not something it does well.

Hash table time complexity

Operation	Average	Worst case
Put (insert or update)	O(1)	O(n)
Get (lookup)	O(1)	O(n)
Delete	O(1)	O(n)
Resize and rehash	O(n), rare	O(n)
Walk every key	O(n)	O(n)
Memory	O(n)	O(n)

The worst case happens when many keys end up in the same bucket, for example with a poor hash function. Good hash functions, and resizing to keep the load factor low, make it very unlikely.

Hash tables vs other data structures

The right choice depends on what you do most. n is the number of items and k is the number of results returned.

What you need	Hash map	Balanced tree	Unsorted array	Sorted array
Find by key	O(1) average	O(log n)	O(n)	O(log n)
Insert	O(1) average	O(log n)	O(1) at the end	O(n)
Delete by key	O(1) average	O(log n)	O(n)	O(n)
Walk keys in sorted order	O(n log n), sort first	O(n)	O(n log n), sort first	O(n)
Range query ("between a and b")	O(n)	O(log n + k)	O(n)	O(log n + k)
Nearest key	O(n)	O(log n)	O(n)	O(log n)
Guaranteed worst case	No, O(n)	Yes, O(log n)	n/a	Yes for lookup

The bold cells show where each one wins. A hash table is the fastest for exact-key work and the weakest for anything that depends on order.

How to explain hash tables in an interview

Say how it works in one breath: "hash the key to a bucket index, go straight there."
Give both costs: "O(1) on average, O(n) worst case if everything collides."
Name how collisions are handled: "chaining or open addressing", and what the load factor is.
Say it has no order, and name the tree as the alternative when you need order.
For counting or "seen before" problems, say you will trade O(n) memory for O(n) time.

Where you meet hash tables in real systems

Hash tables are one of the most used structures in software. Here are three drawn out, the first with code you can run, then more examples.

Example 1: Counting words and events

Search tools, log analysers and word clouds all start by counting: how many times does each word, error code or page appear? A hash map makes that one pass over the data, because each update is a single lookup. Open the example below to see the picture and the code.

Code: count how many times each word appearsTime O(n)Memory O(k)

Each word is looked up in the map. A new word starts at 1, a known word has its count raised. After one pass the map holds every distinct word and its count.

def count_words(text):
    """Count how many times each word appears.

    A hash map (a Python dict) maps each word to its count. Looking up or
    updating one word takes O(1) on average, however many words are stored.

    Time:   O(n) for n words in the text, one O(1) update per word.
    Memory: O(k) for k distinct words (not n), because repeats share one entry.
    """
    counts = {}                                   # word -> how many times seen
    for word in text.lower().split():
        counts[word] = counts.get(word, 0) + 1    # 0 if the word is new, then add one
    return counts

Each version counted the sentence the cat and the dog and the bird and gave the 3, and 2, and bird, cat and dog 1 each. All five were compiled and run, and none of them uses a package. The harness sorts the output because a hash map does not promise any order.

Example 2: Caches

A cache keeps the answer to an expensive request so the next identical request is instant. The request (a URL, a user ID, a query) is the key and the saved answer is the value. In-memory stores such as Redis keep their keys in hash tables, so a cached read is one lookup.

The key is hashed, the bucket is read, and the saved answer comes back. If the key is missing, the system does the slow work once and stores the result.

Example 3: Database joins

When a database joins two tables, one common method is a hash join. It builds a hash table from the smaller table, keyed by the join column, then reads the bigger table one row at a time and looks each row up in the hash table. That turns a loop inside a loop into two simple passes.

Build a hash table from the small table, then probe it once per row of the big table. Each probe is O(1) on average, so the join costs about the size of both tables added together.

More real-world scenarios

4. Removing duplicates and counting unique visitors

A set answers "have I seen this before?" in one step. Systems use sets to drop duplicate records, ignore a message delivered twice, or count how many distinct users visited a page.

5. Variables in compilers and interpreters

A program refers to variables by name. An interpreter or compiler keeps a symbol table, a hash table from each name to its value or type, so it can look a name up the moment it meets it.

6. Objects in dynamic languages

In Python, objects keep their attributes in a dictionary, and a JavaScript object behaves like a map from property names to values. Reading user.name is a hash lookup on the string "name".

7. DNS caches

A device or resolver remembers recent DNS answers, keyed by the domain name, so it does not ask the network again for a name it looked up a moment ago.

8. Memoisation in dynamic programming

When a recursive function calls itself with the same inputs many times, you can store each result in a hash map keyed by its inputs. The second time the same call comes in, you read the answer instead of recomputing it.

9. The "have I seen the other half?" trick

Problems such as "find two numbers that add to a target" become one pass: for each number, check whether the number you need is already in the map. This is the most common hash map interview pattern.

10. Git and content-addressed storage

Git names every stored object by a hash of its contents, and finds it again by that name. Systems that deduplicate files do the same: if two files have the same hash, they are the same file and can be stored once.

Language standard libraries

Every mainstream language has a built-in hash map and hash set.

Language	Structure or class	What it is under the hood	Notes
Java	`HashMap`, `HashSet`	Array of buckets with chains	`LinkedHashMap` keeps insertion order. `TreeMap` keeps sorted order.
C++	`std::unordered_map`, `std::unordered_set`	Buckets with chains	`std::map` and `std::set` are ordered trees, not hash tables.
C#	`Dictionary<K, V>`, `HashSet<T>`	Hash table	`SortedDictionary` keeps sorted order.
Rust	`HashMap`, `HashSet`	Open-addressing table (hashbrown) with a hash function built to resist attacks	`BTreeMap` keeps sorted order.
Python	`dict`, `set`	Open-addressing hash table	`dict` keeps insertion order. Keys must be hashable, so lists cannot be keys.
Go	`map[K]V`	Built-in hash map	Use `map[K]struct{}` as a set. Iteration order is not specified.
JavaScript	`Map`, `Set`, plain objects	Hash tables	`Map` keeps insertion order and accepts any key type.
Kotlin	`HashMap`, `mutableMapOf()`, `HashSet`	Same as Java	`mutableMapOf()` returns a `LinkedHashMap`.

The pattern: all of them give you a key-value map and a set backed by a hash table, and all of them ask for a hashable key. Where order matters, there is a separate tree-based or ordered variant.

The takeaway

Whenever a system needs fast lookup by key, counting, or "have I seen this?", look for a hash table. When it needs sorted order or range queries, it usually uses a balanced tree instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Given an array of numbers and a target, return the positions of two numbers that add up to the target.
easy
2.
Group a list of words so that words that are anagrams of each other are together.
medium
3.
Return true if any value appears at least twice in an array.
easy
4.
Given an unsorted array of integers, find the length of the longest run of consecutive numbers, in O(n) time.
medium

← Previous

Arrays and Strings

Two Pointers and Sliding Window