Hashing and hash table interview questions, with answers

The questions, with answers

1. 1.How does a hash table achieve O(1) lookup, and when does it not?

   A hash function turns the key into an integer, that integer modulo the table size picks a bucket, and the key is stored or found in that bucket directly — no scanning, no comparisons against other keys along the way. That is O(1) on average, given two conditions: the hash function spreads keys evenly across buckets, and the table is not too full. Break either and lookups degrade: a bad hash that sends many keys to one bucket, or a table so full that every bucket is crowded, turns a lookup into a walk through a list, O(n) in the worst case. Say "average case" when you quote O(1); the worst case is the follow-up you are being set up for.

2. 2.What is a collision, and how do chaining and open addressing handle it?

   A collision is two different keys hashing to the same bucket, which is unavoidable once you have more possible keys than buckets. Separate chaining keeps a small list (or, in Java 8+, a tree once a bucket grows past eight entries) at each bucket and appends colliding keys to it. Open addressing keeps one key per slot and, on collision, probes for another slot: the next one (linear probing), a quadratic sequence, or a second hash function's stride (double hashing). Chaining is simpler, tolerates high load and makes deletion easy; open addressing is more cache-friendly and uses less memory, but needs tombstones for deletion and falls apart as the table fills. Java's HashMap chains; Python's dict and CPython's set use open addressing.

3. 3.What is the load factor, and why does the table resize?

   Load factor is the number of stored entries divided by the number of buckets — how full the table is. With chaining, the average chain length equals the load factor, so a load factor of 0.75 means most lookups touch one or two entries. With open addressing, the expected probe length grows sharply as the load factor approaches 1, and insertion fails outright when every slot is taken. So tables resize: when the load factor crosses a threshold (0.75 in Java's HashMap, about 2/3 in CPython), the bucket array is doubled and every entry is rehashed into the new array. That resize is O(n), but it happens so rarely that the cost amortises to O(1) per insertion — the same argument as a dynamic array's growth.

4. 4.What makes a hash function good, and what happens with a bad one?

   A good hash function is fast, deterministic (equal keys always hash equally), and spreads keys uniformly so that small differences in the key produce very different hashes. A bad one clusters: hashing strings by their first letter sends every name starting with S to one bucket, and the table degrades to a linked list. The extreme case is the one interviewers describe: a hash function that returns a constant, which is legal — it satisfies the contract — but makes every operation O(n). Real libraries also defend against adversarial inputs: Java treeifies long chains, and Python and Ruby randomise string hashing per process so an attacker cannot craft keys that all collide and slow a web server down.

5. 5.Why must you override hashCode when you override equals in Java?

   Because HashMap and HashSet find a key by its hashCode first and only then call equals on the candidates in that bucket. If two objects are equal by your equals but Object's default hashCode gives them different values, they land in different buckets, and the map never compares them — you put a key in and cannot get it out with an equal key. The contract: equal objects must have equal hash codes; unequal objects may share one (that is just a collision). The mirror-image bug is a hashCode that depends on a mutable field: change the field after inserting, and the entry is now filed under the old hash where nobody will look. Keys should be immutable, or at least their hashed fields should be.

   @Override public boolean equals(Object o) {
       if (this == o) return true;
       if (!(o instanceof Point)) return false;
       Point p = (Point) o;
       return x == p.x && y == p.y;
   }
   @Override public int hashCode() { return Objects.hash(x, y); }   // same fields as equals

6. 6.When should you use a HashMap versus a TreeMap or a sorted array?

   Use a hash map when you need fast exact-key lookup, insertion and deletion and you do not care about order: O(1) average for all three. Use a tree map (a balanced BST such as a red-black tree) when you need the keys in sorted order, range queries — everything between two keys — or the nearest key above or below a value; it costs O(log n) per operation but keeps order for free. A sorted array gives O(log n) lookup with the best memory locality but O(n) insertion, so it suits data built once and queried many times. The interview version of this question is usually "why not always use a hash map", and the answer is: when the question involves order, ranges or the smallest element, hashing has nothing to offer.

7. 7.How do you find the first repeated element, or a pair with a given sum, in one pass?

   Both are the same trick: a hash set of what you have already seen turns "have I met this before" into an O(1) check. For the first repeated element, scan left to right, and the first value already in the set is the answer — O(n) time, O(n) space, instead of the O(n²) double loop. For two-sum, scan the array and, for each value v, check whether target - v is in the set before adding v; the check comes first so an element cannot pair with itself. To return indices rather than values, store value to index in a map. Counting frequencies (anagram checks, the majority element, the first unique character) is the map version of the same idea.

   boolean hasPairWithSum(int[] a, int target) {
       Set<Integer> seen = new HashSet<>();
       for (int v : a) {
           if (seen.contains(target - v)) return true;   // check before adding
           seen.add(v);
       }
       return false;
   }

8. 8.How does a HashMap iterate, and why is its order not the insertion order?

   Iteration walks the bucket array from index 0 upward and each chain in order, so the sequence depends on the keys' hash codes and the current table size — not on when you inserted them — and it changes after a resize. That is why code that relies on HashMap order breaks unpredictably. If you need insertion order, use LinkedHashMap, which threads a doubly linked list through the entries at a small memory cost (and can be configured for access order, which is how an LRU cache is built in a few lines). If you need sorted order, use TreeMap. Python's dict has preserved insertion order since 3.7, which is the exception that makes people expect it everywhere.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 4 on hashing and 60 across DSA.