LearnAbout

Hashing

On this page
Quick reference
Insert / lookup / delete (average case)O(1)
Insert / lookup / delete (worst case)O(n)
The Idea

Remember from Arrays & Strings Fundamentals that array indexing is O(1). The address comes directly from the index: base + index × size. This is only arithmetic, with no search. Hashing uses this same trick for keys that are not already small, simple integers. A hash function takes any key, for example a word, a tuple, or a full object. It changes the key into a number. The computer uses that number as a plain array index. When you look up "apple" in a hash table, the computer changes "apple" into a number. That number tells you exactly which slot in a backing array to check. No scan is necessary.

Imagine a library that puts books on shelves by a formula from the title, not in alphabetical order. For any title, you compute the formula and go directly to the shelf. You do not browse. This is the whole idea. You trade some memory (the backing array must have room for the possible outputs of the formula) for almost immediate lookup.

Hashing changes "have I seen this value before?" from an O(n) scan into an approximately O(1) lookup. This is the most common improvement in this phase. It is also the reason that many problems from earlier topics return here with a better time complexity.
Build It
Structures
structure HashMap:
    buckets      // a plain array (Arrays & Strings Fundamentals), one slot for each possible hash value
    size         // the number of key/value pairs that are stored now

function hash(key):
    return someFormula(key) % buckets.length   // changes any key into a valid array index
collisions — when two keys land in the same bucket
// Two different keys can hash to the same bucket index. This is a collision.
// One common fix is chaining: each bucket holds a small list instead of one slot.
function insert(map, key, value):
    bucketIndex = hash(key)
    if map.buckets[bucketIndex] is empty:
        map.buckets[bucketIndex] = new list
    map.buckets[bucketIndex].add((key, value))   // Add to the chain. Do not overwrite it.
A good hash function spreads the keys evenly across the buckets. This keeps each chain short, usually one entry. A bad hash function, or an adversarial input, can put many keys in the same bucket. Then the lookup for that bucket becomes a walk through a list.
frequency count — hash map
function countFrequencies(items):
    counts = new HashMap
    for item in items:
        counts[item] = counts.get(item, default=0) + 1
    return counts
membership check — hash set
function hasDuplicate(items):
    seen = new HashSet
    for item in items:
        if item in seen:          // O(1) average: a hashed lookup, not a scan
            return true
        seen.add(item)
    return false
Know It

The "average" word is more important here than almost anywhere else. Remember the difference between the average case and the worst case from Big-O Notation. The speed of a hash table depends on a hash function that spreads the keys well. When this is true (the normal case), lookups are almost immediate.

OperationTimeSpaceWhy
Insert / lookup / delete (average case)O(1)O(1) per operation (O(n) total for n entries)A good hash function spreads the keys evenly. So each bucket holds close to zero or one entries. To check a bucket is almost constant work.
Insert / lookup / delete (worst case)O(n)O(1) per operationIf every key goes to the same bucket (a bad hash function, or an adversarial input made to collide), that bucket's chain grows to length n. A search of the chain is a full scan. This is rare in practice, but real.
Break It

Using a mutable value as a key

the contents of a key change after you insert it

The computer computes the hash of a key from its contents at insert time. If the key is a mutable object and its contents change later, a new hash would be different. But the table does not compute the hash again. So the entry is now in the wrong bucket for the current key. Future lookups for it fail with no error. A key must be a value that does not change after you store it.

Assuming iteration order matches insertion order

code loops over the entries of a hash map and expects a specific order

Some hash map implementations keep the insertion order, or offer a variant that does. Other implementations give no such guarantee and can return the entries in an order that looks random. Code that depends on order without a check of the specific language guarantee works by accident in one language and fails in another.

Reaching for hashing when order actually matters

the problem needs sorted order, not only fast membership

Hashing gives a fast answer to "is this here" or "what is paired with this". It does not give order. A hash set or map does not keep the keys sorted. A loop over one does not give useful order information. Problems that need "the smallest", "in sorted order", or "the next largest" need a different tool, even if fast lookup is also part of the problem.

Collisions silently degrading performance

many keys hash to the same bucket or to nearby buckets

Code that assumes every hash map operation is O(1) can be O(n) per operation on data that collides a lot. An attacker who knows your hash function can sometimes make exactly this input on purpose. "Average case O(1)" is a property of typical data, not a guarantee for all data.

Use It
Two Sum
This is the real tool behind the O(n) approach from Big-O Notation. A hash map stores "value seen → index". It changes "has the complement of this number already appeared?" into one O(1) lookup instead of a nested scan.
Easy
Contains Duplicate
A hash set gives O(1) average membership checks. Put each element in as you go. When an element is already present, you are done in one pass.
Easy
Valid Anagram
Use a hash map of character → count. Build it from one string and reduce it with the other string. You can also use a fixed-size array if you know the strings are only lowercase letters, as in the frequency tables in Sliding Window. Any wrong or remaining count means the strings are not anagrams.
Easy
Group Anagrams
Two anagrams always give the same value when you sort (or count) their characters. Use that canonical form as a hash map key. Put each original string under it.
Medium
Top K Frequent Elements
A hash map does the count pass in O(n). To read the top k without a full sort, group the counted values by their frequency (an array indexed by count, from 0 up to n). Then walk that array from the high-frequency end.
Medium
Longest Consecutive Sequence
Put each number into a hash set for O(1) membership checks. Start a count of a streak only from numbers that are the start of one (there is no num - 1 in the set). This skips a re-walk of the same streak from the middle many times. It keeps the full scan O(n).
Medium
Ransom Note
Use a hash map (or a fixed-size array if the text is only lowercase letters) to count the letters of the magazine. Then subtract each letter that the ransom note needs. If any count becomes negative, the note is not possible.
Easy
Isomorphic Strings
Use two hash maps. One map goes from characters in the first string to the second string. One map goes back. A character can map to (and be mapped from) exactly one partner. Check this in one pass.
Easy
Word Pattern
Use the same two-way mapping idea as Isomorphic Strings. Here the map is between pattern letters and whole words, not single characters.
Easy
Subarray Sum Equals K
This is exactly the Prefix Sums approach, now with the missing piece named. The running-sum lookup that you tracked is a hash map from a running-sum value to the number of times it has occurred. This makes each check O(1) instead of a new scan.
Medium