In this article
How a hash map works
What is a hash map and how does it work?
A hash map is a data structure that stores key-value pairs and finds the value for a key by turning the key into an integer, its hash code, and using that integer to choose a bucket, the slot that holds the entries. A lookup hashes the key to pick a bucket, then compares keys with equals. Java's HashMap is a "hash table based implementation" of the Map interface (Oracle, Java Standard Edition (SE) 8 documentation, June 2026).
Text description of the diagram
- A lookup hashes the key to pick a bucket, then compares keys with equals.
- Equal keys must produce the same hash code, or lookups fail.
Why it is asked: it shows whether you can explain the mechanism and not only use the type. Read the full explanation: coding interview guide.
Why is a hash map lookup O(1) on average but O(n) in the worst case?
Oracle says get and put take constant time "assuming the hash function disperses the elements properly among the buckets" (Oracle, June 2026). Python's documentation gives the same condition: dict times are average-case and assume collisions are uncommon, and when every key hashes to the same value each operation takes O(n) (Python documentation, accessed October 2026). The constant also assumes hashing a key costs constant time.
Why it is asked: the strong answer states the condition, not just "O of one". Read the full explanation: Python documentation, time complexity.
What is the difference between a hash map and a hash set, and why not search a list?
A hash set stores keys only, with no values, and uses the same hashing idea. In Python, x in s for a set is O(1) on average, while x in l for a list is O(n) because it scans the elements (Python documentation, accessed October 2026). So turning a list into a set before many membership tests is a common speed-up.
Why it is asked: it checks that you pick the structure by the operation you repeat. Read the full explanation: Python interview questions and answers.
Collisions
What is a collision, and how is it handled?
A collision is two different keys landing in the same bucket. It is legal: Oracle does not require unequal objects to have distinct hash codes (Oracle, Object documentation, June 2026). Chaining keeps several entries in one bucket; open addressing probes other slots instead. Conceptually the bucket is the hash code modulo the capacity, so hash codes 1, 17 and 33 all land in bucket 1 of 16.1
Why it is asked: collisions are the reason the average-case caveat exists. Read the full explanation: Oracle, HashMap.
How does Java 8 handle many collisions in one bucket?
Once a bucket grows past a threshold, it switches from a linked list of entries to a balanced tree, which improves worst-case performance from O(n) to O(log n) (OpenJDK proposal 180, updated June 2017). Nodes in the tree are ordered by hash code first, so keys that share a bucket but have different hash codes benefit either way. When keys share the exact same hash code, the tree can only order them if they are Comparable: Oracle notes that "when keys are Comparable, this class may use comparison order among keys to help break ties" (Oracle, June 2026).
For 10,000 distinct, comparable keys that land in one bucket, that is on the order of log₂ 10,000 ≈ 13 levels rather than up to 10,000 comparisons.1 A secondary reading of the OpenJDK source gives the thresholds as 8 nodes to treeify (only when the table has at least 64 buckets, otherwise it resizes) and 6 when a resize splits the bin (secondary walkthrough, October 2026).
Why it is asked: it separates textbook answers from knowledge of a real implementation. Read the full explanation: OpenJDK proposal 180.
What happens if every key has the same hashCode?
Every entry lands in one bucket, so the table behaves like a single list or tree and the speed advantage disappears. Oracle puts it plainly: using many keys with the same hashCode() is a sure way to slow down any hash table (Oracle, June 2026). The fix is a hashCode that mixes every field used by equals, so keys spread across buckets.
Why it is asked: it tests whether you know the hash function carries the performance. Read the full explanation: Oracle, HashMap.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Resizing and load factor
What is load factor, and when does a HashMap resize?
The load factor is a measure of how full the table may get before its capacity increases. The defaults are a capacity of 16 and a load factor of 0.75, and the table is rehashed to about twice the buckets once the entry count exceeds capacity times load factor (Oracle, June 2026). So the threshold is 12, the 13th entry resizes to 32, and the next threshold is 24.1 It counts entries, not occupied buckets.
Why it is asked: "resizes at 75% full" is a common half-right answer. Read the full explanation: Oracle, HashMap.
How do you pre-size a HashMap to avoid rehashing?
Choose an initial capacity above the expected entries divided by the load factor. Oracle states that if the initial capacity exceeds the maximum number of entries divided by the load factor, no rehash ever occurs (Oracle, June 2026). For 1,000 entries that is 1,000 / 0.75 = 1,333.33, so request at least 1,334.1
Why it is asked: it shows you connect the load-factor rule to a practical choice. Read the full explanation: Oracle, HashMap.
If resizing costs O(n), why is insertion still O(1)?
Amortized cost is the average cost per operation over a long run of operations. A single insert may be O(n) when the storage is resized, but the table roughly doubles each time, so the expensive resizes are rare and their cost is spread over many cheap inserts. Python's time-complexity page makes the same point about its dict: an individual operation may occasionally be O(n) when the storage is resized, but the cost is spread over many operations (Python documentation, accessed October 2026).
Why it is asked: it separates worst-case thinking from amortized thinking. Read the full explanation: Python documentation, time complexity.
Keys: equals and hashCode
What is the equals and hashCode contract?
If two objects are equal according to equals, calling hashCode on each must produce the same integer. The reverse is not required: unequal objects may share a hash code, which is a collision. Oracle adds that the integer need not stay the same from one run of an application to the next (Oracle, Object documentation, June 2026). Equal keys must produce the same hash code, or lookups fail.
Why it is asked: it is the most common Java hash question. Read the full explanation: Oracle, Object documentation.
What breaks if you override equals but not hashCode?
Two keys that your equals treats as equal can get different hash codes, so they land in different buckets and get with an equal key misses the stored entry. Oracle notes it is generally necessary to override hashCode whenever equals is overridden (Oracle, Object documentation, June 2026). Override both, using the same fields in each.
Why it is asked: it tests whether you have met this bug. Read the full explanation: Oracle, Object documentation.
Can a mutable object be a safe key?
It is risky; the Java Map documentation says "great care must be exercised if mutable objects are used as map keys" (Oracle, Map documentation, June 2026). If a field used by hashCode changes after the entry is stored, the key now hashes to a different bucket, and lookups search the wrong place, so the entry becomes unreachable even though it is still in the map. Prefer immutable keys such as strings or small value objects, or never change the fields that feed hashCode while the object is a key.
Why it is asked: it probes whether you connect hashing to object lifecycle. Read the full explanation: coding interview guide.
Can a HashMap hold null, and why does get return null?
Java's HashMap permits null values and one null key. Because of that, a null return from get does not necessarily mean the key is absent; the key may be mapped to null (Oracle, June 2026). Use containsKey to tell the two cases apart.
Why it is asked: it catches a quiet source of bugs in lookups. Read the full explanation: Oracle, HashMap.
Ordering and threads
Does a HashMap keep insertion order?
No. Oracle states the class offers no promise about the order of the map and that the order may change over time (Oracle, June 2026). If a problem needs insertion-ordered or sorted output, use LinkedHashMap or TreeMap (both covered below), or sort the keys before you print them.
Why it is asked: relying on iteration order is a classic mistake. Read the full explanation: Oracle, HashMap.
Is HashMap thread-safe?
No. Oracle's documentation says the implementation is not synchronized: if several threads use the map at the same time and at least one of them changes its structure, the map must be synchronized externally, for example by wrapping it with Collections.synchronizedMap. Its iterators are fail-fast on a best-effort basis, meaning they try to throw an exception when the map changes under them but do not promise to (Oracle, June 2026). The usual concurrent replacement is ConcurrentHashMap, covered below.
Why it is asked: it leads to the HashMap versus ConcurrentHashMap follow-up that senior rounds ask. Read the full explanation: Oracle, HashMap.
How is HashMap different from Hashtable?
Hashtable is the older class: it is synchronized, and neither its keys nor its values can be null, whereas HashMap is unsynchronized and permits one null key and null values. Oracle recommends ConcurrentHashMap in place of Hashtable when a highly concurrent map is wanted, and HashMap when thread safety is not needed (Oracle, Hashtable documentation, June 2026).
Why it is asked: it is a classic warm-up that checks you know the legacy class. Read the full explanation: Oracle, Hashtable.
How is HashMap different from ConcurrentHashMap?
ConcurrentHashMap is a hash table built for use by many threads: Oracle says retrievals generally do not block and that it supports high expected concurrency for updates. Like Hashtable and unlike HashMap, it does not allow null as a key or value (Oracle, ConcurrentHashMap documentation, June 2026). Choose it when several threads share one map, instead of locking a whole HashMap.
Why it is asked: it is the standard concurrency follow-up to the thread-safety question. Read the full explanation: Oracle, ConcurrentHashMap.
When would you use LinkedHashMap or TreeMap instead of HashMap?
Use LinkedHashMap when you need iteration in a predictable order, normally the order keys were inserted, because it threads a linked list through its entries (Oracle, LinkedHashMap documentation, June 2026). Use TreeMap when you need keys sorted by natural order or a comparator; it is a red-black tree with a documented O(log n) cost for get, put and containsKey (Oracle, TreeMap documentation, June 2026).
Why it is asked: it checks that you pick the map by the ordering you need. Read the full explanation: Oracle, TreeMap.
Coding problems with a hash map
How do you solve Two Sum with a hash map?
Walk the array once. For each number, check whether target minus that number is already in the map; if so, return the stored index and the current one, otherwise store the number with its index. With n numbers that is n average-case O(1) lookups (Python documentation, accessed October 2026). For 1,000 numbers, brute force checks 499,500 pairs against at most 1,000 lookups.1
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen: # average O(1) lookup
return [seen[target - x], i]
seen[x] = iOn [2, 7, 11, 15] with target 9 the script returned indices [0, 1].1
Why it is asked: it is the standard first example of trading memory for time. Read the full explanation: coding interview guide.
How does a hash map solve subarray sum equals k?
Keep a running prefix sum and a map from each prefix sum to how often it has appeared. Start the map with prefix sum 0 seen once, so subarrays that begin at index 0 are counted. At each position, the number of earlier prefixes equal to the current sum minus k is the number of subarrays ending here that total k. One pass with average O(1) map operations gives O(n) time, and the method works with negative numbers, where a sliding window fails. The detail is in the page on subarray sum equals k.
Why it is asked: it tests whether you can turn a nested loop into a stored lookup. Read the full explanation: subarray sum equals k.
How do you find the longest substring without repeating characters?
Store the last index at which each character was seen, and keep a window start. When the current character was seen at or after the window start, move the start just past that earlier index. The window length is the end minus the start plus one, and the best length seen is the answer. Each character is processed once, so the time is linear.
Why it is asked: it combines a map with the sliding-window idea. Read the full explanation: longest substring without repeating characters.
How do you count frequencies, and what does defaultdict add?
Loop over the items and add one to the count stored under each item. With a plain Python dict you must handle the missing-key case first, for example with get(key, 0). A defaultdict supplies a default value for a missing key, so the loop is one line shorter and cannot raise a missing-key error. See what a defaultdict is.
Why it is asked: it checks fluent use of the language's own map type. Read the full explanation: what a defaultdict is.
Follow-up questions
What are common hashmap interview questions?
The twenty-two above cover what recurs: how lookup works, collisions, load factor and resizing, the equals and hashCode contract, ordering and threads, and the problems that use a map as a lookup table, such as Two Sum. The wider routine for these rounds is in the coding interview guide.
Are hash map questions different in Python?
The ideas are the same: average-case O(1) with an O(n) worst case, and hash-based sets alongside dicts. The vocabulary changes, with dict instead of HashMap, and the equals and hashCode pair becomes __eq__ and __hash__: a class that defines __eq__ without __hash__ has its __hash__ set to None and cannot be a dict key (Python data model documentation, accessed October 2026). Python dicts also keep insertion order, a language rule since version 3.7, unlike Java's HashMap. More language detail is in Python interview questions and answers.
How do I practise hash map problems?
Solve a problem with brute force first, say its cost aloud, then ask what you could store to avoid the repeated work. Try subarray sum equals k and longest substring without repeating characters, and compare it with a sort-based problem such as merge intervals to see when sorting wins instead.
When should I not use a hash map?
When you need keys in sorted order, when a small array indexed by a number is enough, or when keys have poor hash spread, since the constant-time claim depends on it. Say the trade-off in the interview rather than defaulting to a map.
- A hash map finds a key by hashing it to a bucket, then comparing keys with
equals. O(1)lookup is an average-case result that depends on the hash function spreading keys.- Java resizes when entries exceed capacity times load factor: the 13th entry at the defaults.
- Equal objects must have equal hash codes; override
equalsandhashCodetogether. - A Java
HashMaphas no ordering promise and is not synchronized.
Sources
- HashMap (Java Platform SE 8), Oracle — Oracle, 3 Jun 2026
- Object.hashCode and equals contract (Java Platform SE 8), Oracle — Oracle, 3 Jun 2026
- Time complexity of operations on built-in types, Python documentation — Python Software Foundation, 26 Oct 2026
- JEP 180: Handle Frequent HashMap Collisions with Balanced Trees — OpenJDK, 14 Jun 2017
- HashMap internal working in Java (secondary walkthrough) — ankurm.com, 20 Oct 2026
- Map (Java Platform SE 8), Oracle — Oracle, 3 Jun 2026
- Hashtable (Java Platform SE 8), Oracle — Oracle, 3 Jun 2026
- ConcurrentHashMap (Java Platform SE 8), Oracle — Oracle, 3 Jun 2026
- LinkedHashMap (Java Platform SE 8), Oracle — Oracle, 3 Jun 2026
- TreeMap (Java Platform SE 8), Oracle — Oracle, 3 Jun 2026
- Data model: object.__hash__, Python documentation — Python Software Foundation, 26 Oct 2026
