Definition
- HashMap – a data structure that stores key-value pairs and provides O(1) average time for insertion, lookup, and deletion.
- Hash function – computes
hashCode()on the key, spreads the bits, and maps the result to a bucket index in the internal array. - Bucket – a slot in the internal array where entries land after hashing; collisions chain entries together.
- Load factor – the threshold (default 0.75) at which the map doubles capacity and rehashes to keep buckets short.
- Collision handling – entries in the same bucket form a linked list, which converts to a red-black tree after eight entries (Java 8+).
Think of the account register at the National Bank of India. Instead of flipping through every page to find Rajesh's balance, the bank uses his account number SAV2001 as a key. A formula instantly converts that account number into a shelf position, and the balance sits waiting on that shelf. You hand over the account number, the formula points to the exact shelf, and you grab the balance immediately without searching the whole register.
Understanding the Concepts
What is a HashMap?
A HashMap is a data structure that stores data as key-value pairs and lets you retrieve a value by its key in average constant time. Internally it keeps an array of buckets. When you call put(key, value), the map computes key.hashCode(), applies a bit-spreading function, and uses the result to pick a bucket index. The entry is stored in that bucket. When you call get(key), the same hash computation finds the bucket, and the map walks the bucket's chain comparing keys with equals() to find the matching entry.
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class AccountBalanceStore {
public static void main(String[] args) {
Map<String, BigDecimal> balances = new HashMap<>();
balances.put("SAV2001", new BigDecimal("1000000.00"));
balances.put("CUR3001", new BigDecimal("500000.00"));
BigDecimal rajesh = balances.get("SAV2001");
System.out.println("Rajesh balance: " + rajesh);
}
}
Rajesh balance: 1000000.00
How does the hash function work internally?
Java's HashMap does not use hashCode() directly. It applies a secondary hash that XORs the upper 16 bits of the hash code with the lower 16 bits. This spreads the information across all bits and reduces collisions when the bucket array is small. The bucket index is then computed as (n - 1) & hash, where n is the array length and is always a power of two, so the bitwise AND acts as a fast modulo.
package com.bank.core;
public class HashDemo {
static int spread(int h) {
return h ^ (h >>> 16);
}
static int bucketIndex(int hash, int capacity) {
return (capacity - 1) & hash;
}
public static void main(String[] args) {
String key = "SAV2001";
int raw = key.hashCode();
int spread = spread(raw);
int index = bucketIndex(spread, 16);
System.out.println("Raw hash: " + raw);
System.out.println("Spread hash: " + spread);
System.out.println("Bucket index (cap 16): " + index);
}
}
How does collision handling work?
When two keys hash to the same bucket, a collision occurs. Java chains the entries in that bucket as a linked list. Each node holds the key, value, hash, and a pointer to the next node. On lookup the map walks this chain and compares each key using equals(). Since Java 8, once a bucket holds eight or more entries and the table has at least 64 buckets, the linked list converts into a red-black tree, which drops the worst-case lookup from O(n) to O(log n).
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class CollisionDemo {
public static void main(String[] args) {
// These two accounts may land in the same bucket
Map<String, BigDecimal> balances = new HashMap<>(4);
balances.put("SAV2001", new BigDecimal("100000"));
balances.put("SAV2005", new BigDecimal("200000"));
balances.put("CUR3001", new BigDecimal("300000"));
// If SAV2001 and CUR3001 collide, they chain in the same bucket
System.out.println("Lookup SAV2001: " + balances.get("SAV2001"));
System.out.println("Lookup CUR3001: " + balances.get("CUR3001"));
}
}
Lookup SAV2001: 100000
Lookup CUR3001: 300000
How does resizing work?
The map tracks a load factor, which defaults to 0.75. When the number of entries exceeds the load factor times the current capacity, the map doubles the internal array and rehashes every entry into the new, larger array. Doubling keeps the bucket count as a power of two, which is required for the bitwise index computation. Pre-sizing the map avoids unnecessary resizes.
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class PreSizedMap {
public static void main(String[] args) {
int expectedAccounts = 10000;
// Pre-size to avoid resizing: capacity = expected / loadFactor + 1
Map<String, BigDecimal> balances = new HashMap<>(
(int) (expectedAccounts / 0.75) + 1
);
for (int i = 0; i < expectedAccounts; i++) {
balances.put("ACC-" + i, BigDecimal.valueOf(i * 1000L));
}
System.out.println("Stored " + balances.size() + " accounts without resizing.");
}
}
What is the equals and hashCode contract?
If two objects are equal according to equals(), they must return the same hashCode(). Breaking this contract causes the map to store duplicates or fail to find existing keys. If you override equals() on a custom key class, you must also override hashCode() to be consistent.
package com.bank.model;
import java.util.Objects;
public class AccountKey {
private final String branchCode;
private final String accountNumber;
public AccountKey(String branchCode, String accountNumber) {
this.branchCode = branchCode;
this.accountNumber = accountNumber;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof AccountKey)) return false;
AccountKey that = (AccountKey) o;
return branchCode.equals(that.branchCode)
&& accountNumber.equals(that.accountNumber);
}
@Override
public int hashCode() {
return Objects.hash(branchCode, accountNumber);
}
}
What is the BigDecimal equals trap?
BigDecimal's equals() method considers scale, so new BigDecimal("1.0") and new BigDecimal("1.00") are not equal and may hash differently. This means a HashMap keyed on BigDecimal can store what look like duplicate amounts. To avoid this, either normalise the scale with stripTrailingZeros() before insertion, or use a TreeMap with BigDecimal::compareTo as the comparator.
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class BigDecimalTrap {
public static void main(String[] args) {
Map<BigDecimal, String> map = new HashMap<>();
map.put(new BigDecimal("1.0"), "first");
map.put(new BigDecimal("1.00"), "second");
// Two entries because equals considers scale
System.out.println("Size: " + map.size()); // 2, not 1
// Fix: normalise with stripTrailingZeros
Map<BigDecimal, String> fixed = new HashMap<>();
fixed.put(new BigDecimal("1.0").stripTrailingZeros(), "first");
fixed.put(new BigDecimal("1.00").stripTrailingZeros(), "second");
System.out.println("Fixed size: " + fixed.size()); // 1
}
}
Size: 2
Fixed size: 1
What about thread safety?
A plain HashMap is not thread-safe. If two threads call put() concurrently, the internal structure can corrupt, leading to lost entries or infinite loops during resize. In a multi-threaded banking service, use ConcurrentHashMap, which partitions the buckets into segments and allows concurrent reads and writes without locking the entire map.
package com.bank.service;
import java.math.BigDecimal;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
public class ConcurrentBalanceStore {
private final ConcurrentMap<String, BigDecimal> balances =
new ConcurrentHashMap<>();
public void updateBalance(String accountId, BigDecimal newBalance) {
balances.put(accountId, newBalance);
}
public BigDecimal getBalance(String accountId) {
return balances.getOrDefault(accountId, BigDecimal.ZERO);
}
}
What are common mistakes?
The most common mistake is using a mutable object as a key and then modifying it after insertion. Changing the object changes its hash code, and the map can no longer find it in the correct bucket, making the entry unreachable.
// Wrong: mutable key
List<String> key = new ArrayList<>(List.of("SAV", "2001"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "Rajesh");
key.add("EXTRA"); // hash changes
System.out.println(map.get(key)); // null, entry is lost
// Correct: use an immutable key
String safeKey = "SAV-2001";
Map<String, String> safeMap = new HashMap<>();
safeMap.put(safeKey, "Rajesh");
System.out.println(safeMap.get(safeKey)); // Rajesh
How is HashMap different from TreeMap and LinkedHashMap?
| Feature | HashMap | TreeMap | LinkedHashMap |
|---|---|---|---|
| Ordering | None | Sorted by key | Insertion order |
| Lookup time | O(1) average | O(log n) | O(1) average |
| Null keys | One allowed | Not allowed | One allowed |
| Use case | General fast lookup | Range queries | LRU cache, ordered iteration |
package com.bank.core;
import java.util.*;
public class MapComparison {
public static void main(String[] args) {
Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> treeMap = new TreeMap<>();
Map<String, Integer> linkedMap = new LinkedHashMap<>();
for (String key : List.of("CUR", "SAV", "FDR", "LON")) {
hashMap.put(key, 1);
treeMap.put(key, 1);
linkedMap.put(key, 1);
}
System.out.println("HashMap order: " + hashMap.keySet());
System.out.println("TreeMap order: " + treeMap.keySet());
System.out.println("LinkedHashMap order: " + linkedMap.keySet());
}
}
What should a senior engineer know?
A senior engineer knows the internal mechanics: the bit-spreading secondary hash, the power-of-two capacity, the linked-list-to-tree threshold, and the resize trigger. They pre-size maps to avoid unnecessary resizes in hot paths, use immutable keys, and choose ConcurrentHashMap for concurrent access. They also know that Java 8 introduced the compute, merge, and computeIfAbsent methods, which simplify patterns like counting frequencies or building adjacency lists.
Visual Overview
put("SAV2001", 1000000)
┌─────────────────────────────────────┐
│ key.hashCode() --> raw hash │
│ spread(raw) --> spread hash │
│ (cap-1) & hash --> bucket index │
└──────────────┬──────────────────────┘
│
▼
Bucket Array (capacity = 16)
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │...│ 7 │...│12 │...│15 │
└───┴───┴───┴───┴─┬─┴───┴───┴───┴───┘
│
▼
┌──────────┐ ┌──────────┐
│ SAV2001 │--->│ CUR3001 │---> null
│ 1000000 │ │ 500000 │
└──────────┘ └──────────┘
(linked list chain in same bucket)
When chain >= 8 entries + table >= 64 buckets:
Chain converts to a red-black tree (O(log n) worst case)
When entries > loadFactor * capacity:
Table doubles, all entries rehash into new buckets
Key Takeaway
A HashMap is a data structure that stores key-value pairs and gives you average constant time for put, get, and remove. It works by applying a hash function to the key to compute a bucket index in an internal array, so instead of searching through every entry it jumps directly to the right bucket and finds the value in one step. The internal array is always a power of two in size, the hash is spread by XORing the upper and lower 16 bits, and the bucket index is a fast bitwise AND.
In my banking work at the National Bank of India, I use a HashMap as the account directory. The mobile app looks up a customer's balance by account number thousands of times per second, and scanning a list for every request would be far too slow. Updating a balance after a transfer is just putting the same key again, which replaces the value in place, and for unknown accounts I use getOrDefault to return a safe zero instead of risking a null.
On the internals, collisions are unavoidable because many keys can map to the same bucket. Java chains the colliding entries in a linked list, and since Java 8 that list converts to a balanced red-black tree once it grows past eight entries and the table has at least 64 buckets. The map also resizes by doubling capacity when entries exceed 75 percent of capacity, keeping buckets short. Pre-sizing the map to the expected number of entries divided by the load factor avoids unnecessary resizes in hot paths.
The senior-level points I always raise are the equals and hashCode contract, the BigDecimal scale trap, and thread safety. Equal keys must produce the same hash code, mutable keys break lookups after modification, BigDecimal equals considers scale so numerically identical values can look different to the map, and a plain HashMap is not thread-safe so concurrent banking services must use ConcurrentHashMap.
Remember one sentence: a HashMap hashes the key to a bucket index for O(1) average lookup, but correctness depends on the equals-hashCode contract, immutable keys, and choosing ConcurrentHashMap for concurrent access.
---