HashMap Explained: How a Hash Map Works, With Code in Python, JavaScript and Java

A hash map is the data structure behind Python's dict, JavaScript's Map and Java's HashMap. It is the single most useful structure in coding interviews because it turns many O(n) searches into O(1) lookups.

What a hash map is

Imagine a wall of numbered lockers. To store a notebook for "Asha", you run her name through a rule that always gives the same locker number and put the notebook there. To find it later you run the same rule and walk straight to the locker, without checking the others. The rule is the hash function, the lockers are buckets, and the notebook is the value.

How it works, step by step

1. Hash the key. The hash function turns the key into an integer, and the same key always gives the same integer.
2. Pick a bucket. The map takes hash % array_size to get an index in its internal array.
3. Store or find the pair in that bucket.
4. Handle collisions. Different keys can map to the same bucket, so a bucket may hold several pairs.
5. Resize when crowded. When the map is too full it allocates a bigger array and re-inserts every pair.

A tiny hash map you can read in one go

This Python version uses chaining: each bucket is a list of pairs. It resizes when the load factor passes 0.75.

class TinyHashMap:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]   # each bucket holds (key, value) pairs
        self.count = 0

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                  # key already there: update it
                bucket[i] = (key, value)
                return
        bucket.append((key, value))       # collision? chaining just appends
        self.count += 1
        if self.count / len(self.buckets) > 0.75:
            self._resize()

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(len(self.buckets) * 2)]
        self.count = 0
        for k, v in old:
            self.put(k, v)

scores = TinyHashMap()
for name, mark in [("Asha", 91), ("Ravi", 84), ("Meera", 77), ("Asha", 95)]:
    scores.put(name, mark)
print(scores.get("Asha"), scores.get("Ravi"), scores.get("Zoya", "missing"), scores.count)

Output: 95 84 missing 3. The second Asha replaced the first, so the map holds three keys, not four.

Collisions and how maps resolve them

The load factor is the number of pairs divided by the number of buckets. Java's HashMap starts with 16 buckets, resizes at a load factor of 0.75, and since Java 8 turns long buckets into balanced trees, which lowers the worst case from O(n) to O(log n).

Time complexity

The worst case happens when most keys collide into one bucket. A good hash function and resizing make it rare. Hash maps use extra memory to buy speed.

Using the built-in versions

Python dict

Keys must be hashable. Immutable values such as strings, numbers and tuples work; lists do not.

prices = {"pen": 10, "book": 120}
prices[("a", 1)] = 5          # a tuple is hashable, so it can be a key
try:
    prices[["a", 1]] = 5      # a list is mutable and unhashable
except TypeError as error:
    print("TypeError:", error)

Output: TypeError: unhashable type: 'list'. Since Python 3.7 a dict also remembers insertion order.

JavaScript Map

A Map accepts any value as a key and keeps insertion order. A plain object turns every key into a string, so prefer Map when keys are not strings.

const text = "banana";
const counts = new Map();
for (const letter of text) {
  counts.set(letter, (counts.get(letter) || 0) + 1);
}
console.log(counts, counts.get("a"));

Output: Map(3) { 'b' => 1, 'a' => 3, 'n' => 2 } 3

Java HashMap

Custom key classes must override both equals() and hashCode(). HashMap allows one null key and does not guarantee order; use LinkedHashMap for insertion order and ConcurrentHashMap across threads.

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> marks = new HashMap<>();
        marks.put("Asha", 91);
        marks.put("Ravi", 84);
        marks.put("Asha", 95);                       // same key: value is replaced
        System.out.println(marks.get("Asha"));       // 95
        System.out.println(marks.containsKey("Zoya")); // false
        System.out.println(marks.getOrDefault("Zoya", 0)); // 0
        for (Map.Entry<String, Integer> entry : marks.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

Hash map patterns that appear in interviews

Two Sum: store what you have seen

def two_sum(numbers, target):
    seen = {}                                  # value -> index
    for i, n in enumerate(numbers):
        if target - n in seen:                 # O(1) lookup
            return [seen[target - n], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))

Output: [0, 1]. One pass, O(n), instead of checking every pair.

Group anagrams: use a canonical key

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        groups["".join(sorted(word))].append(word)   # sorted letters are the key
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

• Counting frequencies of letters or words.
• Detecting duplicates with a set, which is a hash map without values.
• Prefix sums with a map, as in subarray sum equals k.
• LRU cache: a hash map plus a doubly linked list.

Common mistakes

• Using a mutable object as a key and then changing it, so it can no longer be found.
• Writing a Java key class with equals() but no hashCode().
• Assuming iteration order in a Java HashMap or an old Python version.
• Sharing a plain HashMap between threads without protection.
• Checking if key in list inside a loop when a set or map would make it O(1).

Practice problems, in order

1. Two Sum
2. Valid Anagram
3. Group Anagrams
4. Top K Frequent Elements
5. Subarray Sum Equals K
6. LRU Cache

Read the Masai guide to the HashMap data structure with examples for more worked cases.

Frequently asked questions

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Leap AI Residency CohortMasai

8 weeks→

Advanced Certification in AI & MLVishlesan i-Hub, IIT Patna

8 months→

AI & ML Certification ProgramE&ICT Academy, IIT Roorkee

6 months→