Definition
- Bucket array – a
Nodearray where each slot holds the head of a linked list (chain) of key-value pairs - Hash function – computes
hash(key) & (capacity - 1)to find the bucket index; the spread functionh ^ (h >>> 16)mixes high and low bits for better distribution - Chaining – when two keys hash to the same bucket, they form a linked list; each node stores key, value, hash, and a next pointer
- put() – hash the key, find the bucket, walk the chain; if the key exists (equals), replace the value; otherwise prepend a new node
- get() – hash the key, find the bucket, walk the chain comparing with equals(); return the value or null
- Resize – when
size > capacity * loadFactor, create a new array of double capacity and rehash every entry
At National Bank of India, the filing room has 16 shelves (the bucket array). When a new account folder for SAV2001 arrives, the clerk computes a shelf number from the account ID (hash function) and places the folder on that shelf. If two folders land on the same shelf (collision), they are chained together in a stack. When the filing room gets too full (load factor exceeded), the bank doubles the number of shelves and redistributes all folders (resize and rehash).
Understanding the Concepts
How do you build your own HashMap?
Building a HashMap from scratch involves four components: a Node class to hold key-value pairs, a bucket array, a hash function, and resize logic. The implementation below is a simplified version that demonstrates the core mechanics.
package com.bank.core;
import java.util.Objects;
public class BankHashMap<K, V> {
private static class Node<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
private static final int DEFAULT_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;
@SuppressWarnings("unchecked")
private Node<K, V>[] table = new Node[DEFAULT_CAPACITY];
private int size = 0;
// Spread function: mix high bits into low bits for better distribution
private int hash(Object key) {
if (key == null) return 0;
int h = key.hashCode();
return h ^ (h >>> 16);
}
// Bucket index from hash
private int indexFor(int hash, int capacity) {
return hash & (capacity - 1);
}
public V put(K key, V value) {
int h = hash(key);
int index = indexFor(h, table.length);
// Walk the chain: if key exists, replace value
for (Node<K, V> node = table[index]; node != null; node = node.next) {
if (node.hash == h && Objects.equals(node.key, key)) {
V oldValue = node.value;
node.value = value;
return oldValue;
}
}
// Key not found: prepend new node
table[index] = new Node<>(h, key, value, table[index]);
size++;
if (size > table.length * LOAD_FACTOR) {
resize();
}
return null;
}
public V get(K key) {
int h = hash(key);
int index = indexFor(h, table.length);
for (Node<K, V> node = table[index]; node != null; node = node.next) {
if (node.hash == h && Objects.equals(node.key, key)) {
return node.value;
}
}
return null;
}
public V remove(K key) {
int h = hash(key);
int index = indexFor(h, table.length);
Node<K, V> prev = null;
for (Node<K, V> node = table[index]; node != null; prev = node, node = node.next) {
if (node.hash == h && Objects.equals(node.key, key)) {
if (prev == null) {
table[index] = node.next;
} else {
prev.next = node.next;
}
size--;
return node.value;
}
}
return null;
}
@SuppressWarnings("unchecked")
private void resize() {
int newCapacity = table.length * 2;
Node<K, V>[] newTable = new Node[newCapacity];
for (Node<K, V> head : table) {
for (Node<K, V> node = head; node != null; ) {
Node<K, V> next = node.next;
int newIndex = indexFor(node.hash, newCapacity);
node.next = newTable[newIndex];
newTable[newIndex] = node;
node = next;
}
}
table = newTable;
}
public int size() {
return size;
}
public boolean containsKey(K key) {
return get(key) != null;
}
}
How do you test this implementation?
package com.bank.demo;
import com.bank.core.BankHashMap;
import java.math.BigDecimal;
public class BankHashMapDemo {
public static void main(String[] args) {
BankHashMap<String, BigDecimal> balances = new BankHashMap<>();
// put operations
balances.put("SAV2001", new BigDecimal("500000.00"));
balances.put("CUR3001", new BigDecimal("1200000.00"));
balances.put("FD4001", new BigDecimal("2500000.00"));
// get operations
System.out.println("SAV2001 balance: " + balances.get("SAV2001"));
System.out.println("CUR3001 balance: " + balances.get("CUR3001"));
System.out.println("Unknown account: " + balances.get("ACC-999"));
System.out.println("Size: " + balances.size());
// replace existing key
balances.put("SAV2001", new BigDecimal("550000.00"));
System.out.println("Updated SAV2001: " + balances.get("SAV2001"));
// remove
balances.remove("FD4001");
System.out.println("After remove FD4001, size: " + balances.size());
System.out.println("FD4001: " + balances.get("FD4001"));
}
}
SAV2001 balance: 500000.00
CUR3001 balance: 1200000.00
Unknown account: null
Size: 3
Updated SAV2001: 550000.00
After remove FD4001, size: 2
FD4001: null
How does the hash function work?
The hash function has two steps. First, it calls key.hashCode() to get the raw hash. Second, it applies a spread function that XORs the hash with its own upper 16 bits shifted right. This mixing ensures that differences in the upper bits also influence the lower bits, which is important because the bucket index uses only the lower bits (via hash & (capacity - 1)).
package com.bank.demo;
public class HashFunctionDemo {
public static void main(String[] args) {
String key = "SAV2001";
int h = key.hashCode();
int spread = h ^ (h >>> 16);
int capacity = 16;
int bucket = spread & (capacity - 1);
System.out.println("Key: " + key);
System.out.println("hashCode(): " + h);
System.out.println("After spread: " + spread);
System.out.println("Bucket index (capacity=" + capacity + "): " + bucket);
}
}
Key: SAV2001
hashCode(): -1808287924
After spread: -1808223900
Bucket index (capacity=16): 4
How does resizing work?
Resizing happens when the number of entries exceeds capacity * loadFactor. The default load factor is 0.75, meaning a 16-slot array resizes when it holds 13 entries.
During resize, a new array of double capacity is created. Every existing entry is rehashed into the new array because the bucket index depends on the capacity: hash & (newCapacity - 1) produces different indices than hash & (oldCapacity - 1).
- Initial capacity: 16. Resize threshold: 12.
- After first resize: capacity 32. Threshold: 24.
- After second resize: capacity 64. Threshold: 48.
Resize is O(n) because every entry must be moved. However, it happens infrequently enough that the amortised cost of put remains O(1).
What are common mistakes?
Mistake: Not checking equals() after hash match
// WRONG: comparing only hash codes
for (Node<K, V> node = table[index]; node != null; node = node.next) {
if (node.hash == h) { // hash collision! Different keys can have same hash!
return node.value;
}
}
// CORRECT: check hash AND equals
for (Node<K, V> node = table[index]; node != null; node = node.next) {
if (node.hash == h && Objects.equals(node.key, key)) {
return node.value;
}
}
Mistake: Using modulo instead of bitwise AND
// WRONG: modulo can return negative index
int index = hash % capacity; // negative if hash is negative!
// CORRECT: bitwise AND with (capacity - 1), requires power-of-2 capacity
int index = hash & (capacity - 1); // always non-negative
Mistake: Forgetting to rehash during resize
// WRONG: copying entries to same index in new array
for (int i = 0; i < oldTable.length; i++) {
newTable[i] = oldTable[i]; // WRONG! Index depends on capacity!
}
// CORRECT: recompute index for each entry
for (Node<K, V> head : oldTable) {
for (Node<K, V> node = head; node != null; ) {
Node<K, V> next = node.next;
int newIndex = node.hash & (newCapacity - 1);
node.next = newTable[newIndex];
newTable[newIndex] = node;
node = next;
}
}
What should a senior engineer know?
- Java 8 treeification. OpenJDK's HashMap converts a chain to a red-black tree when the chain length reaches 8 (TREEIFY_THRESHOLD) and the table has at least 64 slots. This changes worst-case get from O(n) to O(log n).
- Power-of-two capacity. The capacity is always a power of 2 so that
hash & (capacity - 1)works as a fast modulo. Java's HashMap enforces this by rounding up the initial capacity. - Null key handling. Java's HashMap stores the null key at index 0 with a hash of 0.
- Thread safety. A custom HashMap is not thread-safe. For concurrent access, use ConcurrentHashMap or synchronise externally.
- Open addressing alternative. Instead of chaining, open addressing (linear probing, quadratic probing) stores entries directly in the array. IdentityHashMap uses this approach. It has better cache locality but worse performance under high load factors.
How does this compare to Java's real HashMap?
| Feature | Our BankHashMap | Java HashMap (JDK 17+) |
|---|---|---|
| Collision handling | Chaining (linked list) | Chaining + tree (at length 8) |
| Spread function | h ^ (h >>> 16) | Same |
| Load factor | 0.75 | 0.75 (configurable) |
| Null key | Not handled | Stored at index 0 |
| Iteration | Not implemented | Via EntrySet, KeySet, Values |
| Fail-fast | No | Yes (modCount check) |
| Thread safety | None | None (use ConcurrentHashMap) |
What are common interview follow-up questions?
- "What is the time complexity of put and get?" : O(1) amortised, O(n) worst case (all keys in one bucket). With treeification (Java 8+), worst case is O(log n).
- "What triggers a resize?" : When size exceeds capacity times load factor (default 0.75).
- "Why is capacity a power of 2?" : So that
hash & (capacity - 1)is equivalent tohash % capacitybut faster. - "How does the spread function help?" : It mixes high bits into low bits to reduce clustering when the table is small.
- "What happens if two keys have the same hash?" : They land in the same bucket and form a chain. get() walks the chain and uses equals() to find the correct key.
Visual Overview
Custom HashMap Structure
========================
Node<K,V>[] table (capacity = 16)
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬───┐
│ [0] │ [1] │ [2] │ [3] │ [4] │ [5] │ ... │[15]│
└──┬──┴─────┴──┬──┴─────┴──┬──┴─────┴─────┴───┘
│ │ │
▼ ▼ ▼
null Node(CUR3001) Node(SAV2001)
│ │
▼ ▼
null Node(FD4001) <- collision, same bucket
│
▼
null
put("SAV2001", 500000):
1. h = hash("SAV2001") -> compute spread
2. index = h & (16 - 1) -> bucket 4
3. Walk chain at table[4]
4. Key not found -> prepend Node
5. size++ -> check if size > 16 * 0.75 -> resize if needed
get("SAV2001"):
1. h = hash("SAV2001") -> same hash
2. index = h & (16 - 1) -> bucket 4
3. Walk chain: node.hash == h && node.key.equals("SAV2001")
4. Match found -> return 500000
Resize (capacity 16 -> 32):
┌──────────────────────────────────────────┐
│ Create new Node[32] │
│ For each entry in old table: │
│ newIndex = entry.hash & (32 - 1) │
│ Move entry to new table at newIndex │
│ table = newTable │
└──────────────────────────────────────────┘
Key Takeaway
Building a HashMap from scratch requires four components: a Node array (the buckets), a hash function that maps keys to bucket indices, chaining with linked lists to handle collisions, and automatic resizing when the load factor is exceeded. The put operation hashes the key, walks the chain at the computed bucket, replaces the value if the key exists, or prepends a new node. The get operation does the same traversal and returns the value or null.
The spread function (h ^ (h >>> 16)) is a critical detail. It mixes the upper 16 bits of the hashCode into the lower 16 bits, ensuring better distribution across buckets even when the table is small. Without this, keys with identical lower bits would cluster in the same bucket.
In the National Bank of India's coding interviews, Pankaj asks candidates to implement a HashMap that stores account ID to balance mappings (SAV2001 to BigDecimal amounts). The exercise tests understanding of hashing, collision resolution, the equals/hashCode contract, and amortised analysis. Candidates who mention treeification (Java 8), power-of-two capacity, and the load factor threshold demonstrate senior-level knowledge.
Remember one sentence: a HashMap is a bucket array where put and get hash the key to find the bucket, walk the chain to find the entry using equals, and resize by doubling and rehashing when the load factor is exceeded.
---