Definition
- Hash table is a data structure that uses a hash function to compute an index (bucket) where a key-value pair is stored, giving O(1) average time for get, put, and remove.
- HashMap is the Java implementation of a hash table that stores key-value pairs, allows one null key, and does not guarantee insertion order.
- HashSet is a Set implementation backed by a HashMap internally; it stores only keys (the values are a dummy object) and enforces uniqueness.
- hashCode() is the method every Java object inherits from Object that returns an integer; HashMap uses this integer to compute the bucket index.
- Collision occurs when two different keys produce the same bucket index; Java resolves collisions using a linked list that converts to a red-black tree when the chain reaches 8 entries.
Think of the locker room at National Bank of India. Each locker has a number (the bucket index). When Rajesh deposits a document for account SAV2001, the bank runs the account number through a formula (the hash function) that produces locker number 7. If Priya's account CUR3001 also maps to locker 7, the bank chains both documents inside that locker (collision). To retrieve Rajesh's document, the clerk goes to locker 7 and checks each document's account number (equals) until finding SAV2001.
Understanding the Concepts
What is a hash table?
A hash table is a data structure that stores key-value pairs. It uses a hash function to convert a key into an integer, then maps that integer to a bucket index in an internal array. When you look up a key, the hash function computes the index directly, so the lookup is O(1) on average, without scanning every element.
The three core operations are: put (insert or update), get (retrieve by key), and remove (delete by key).
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
import java.math.BigDecimal;
public class HashTableBasics {
public static void main(String[] args) {
Map<String, BigDecimal> balances = new HashMap<>();
// put: insert key-value pairs
balances.put("SAV2001", new BigDecimal("150000.00"));
balances.put("CUR3001", new BigDecimal("500000.00"));
balances.put("SAV2002", new BigDecimal("75000.00"));
// get: retrieve by key in O(1) average time
BigDecimal rajeshBalance = balances.get("SAV2001");
System.out.println("Rajesh balance (SAV2001): " + rajeshBalance + " INR");
// remove: delete by key
balances.remove("SAV2002");
System.out.println("After removing SAV2002: " + balances);
System.out.println("Size: " + balances.size());
}
}
Expected output:
Rajesh balance (SAV2001): 150000.00 INR
After removing SAV2002: {SAV2001=150000.00, CUR3001=500000.00}
Size: 2
How does HashMap work internally?
HashMap maintains an array of buckets (called table). When you call put(key, value), HashMap computes key.hashCode(), spreads the bits, and uses modulo to find the bucket index. If the bucket is empty, it stores a new node. If the bucket already has entries (collision), it walks the linked list and either updates an existing key or appends a new node.
Starting from Java 8, when a bucket's linked list grows to 8 entries and the table has at least 64 buckets, the list converts to a red-black tree for O(log n) worst-case lookup within that bucket.
package com.bank.core;
import java.util.HashMap;
import java.math.BigDecimal;
public class HashMapInternals {
public static void main(String[] args) {
var accounts = new HashMap<String, BigDecimal>(16, 0.75f);
String key1 = "SAV2001";
String key2 = "CUR3001";
int hash1 = key1.hashCode();
int hash2 = key2.hashCode();
int bucket1 = hash1 & 15; // 15 = capacity(16) - 1
int bucket2 = hash2 & 15;
System.out.println("Key: " + key1 + ", hashCode: " + hash1 + ", bucket: " + bucket1);
System.out.println("Key: " + key2 + ", hashCode: " + hash2 + ", bucket: " + bucket2);
accounts.put(key1, new BigDecimal("150000.00"));
accounts.put(key2, new BigDecimal("500000.00"));
System.out.println("Accounts: " + accounts);
System.out.println("Default capacity: 16, load factor: 0.75");
System.out.println("Resize threshold: 16 * 0.75 = 12 entries");
}
}
Expected output:
Key: SAV2001, hashCode: -1708646498, bucket: 14
Key: CUR3001, hashCode: 2041746654, bucket: 14
Accounts: {CUR3001=500000.00, SAV2001=150000.00}
Default capacity: 16, load factor: 0.75
Resize threshold: 16 * 0.75 = 12 entries
How does HashSet work internally?
HashSet is implemented using a HashMap where each element is stored as a key, and the value is a constant dummy object (PRESENT). When you call add(element), HashSet calls map.put(element, PRESENT). When you call contains(element), it calls map.containsKey(element). This means all the hashing, bucketing, and collision logic from HashMap applies to HashSet.
package com.bank.core;
import java.util.HashSet;
import java.util.Set;
public class HashSetInternals {
public static void main(String[] args) {
Set<String> processedTransactions = new HashSet<>();
// Deduplication: add returns false if element already exists
boolean added1 = processedTransactions.add("TXN-1001");
boolean added2 = processedTransactions.add("TXN-1002");
boolean added3 = processedTransactions.add("TXN-1001"); // duplicate
System.out.println("Added TXN-1001 first time: " + added1);
System.out.println("Added TXN-1002: " + added2);
System.out.println("Added TXN-1001 again: " + added3);
System.out.println("Set size: " + processedTransactions.size());
System.out.println("Contains TXN-1001: " + processedTransactions.contains("TXN-1001"));
System.out.println("Contains TXN-9999: " + processedTransactions.contains("TXN-9999"));
}
}
Expected output:
Added TXN-1001 first time: true
Added TXN-1002: true
Added TXN-1001 again: false
Set size: 2
Contains TXN-1001: true
Contains TXN-9999: false
How is HashMap different from HashSet?
| Feature | HashMap | HashSet |
|---|---|---|
| Stores | Key-value pairs | Unique elements (keys only) |
| Interface | Map | Set |
| Add method | put(key, value) | add(element) |
| Retrieve | get(key) returns value | contains(element) returns boolean |
| Null keys | One null key allowed | One null element allowed |
| Internal structure | Node | Backed by HashMap |
| Use case | Lookup by key (account ID to balance) | Deduplication (processed transaction IDs) |
| Duplicate handling | Overwrites value for existing key | Returns false, element not added |
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class HashMapVsHashSet {
public static void main(String[] args) {
// HashMap: key-value lookup
Map<String, BigDecimal> accountBalances = new HashMap<>();
accountBalances.put("SAV2001", new BigDecimal("150000.00"));
accountBalances.put("SAV2001", new BigDecimal("160000.00")); // overwrites
System.out.println("HashMap SAV2001: " + accountBalances.get("SAV2001") + " INR");
System.out.println("HashMap size: " + accountBalances.size());
// HashSet: unique element tracking
Set<String> processedIds = new HashSet<>();
processedIds.add("TXN-1001");
processedIds.add("TXN-1001"); // ignored, already present
System.out.println("HashSet size: " + processedIds.size());
System.out.println("HashSet contains TXN-1001: " + processedIds.contains("TXN-1001"));
}
}
Expected output:
HashMap SAV2001: 160000.00 INR
HashMap size: 1
HashSet size: 1
HashSet contains TXN-1001: true
What is a complete banking project using HashMap and HashSet?
This project builds an account lookup map, deduplicates transactions with a HashSet, and demonstrates custom hashCode/equals on a Java record.
Project structure
bank-hash-service/ ├── src/ │ └── main/ │ └── java/ │ └── com/ │ └── bank/ │ └── core/ │ ├── Account.java │ ├── AccountLookupService.java │ ├── TransactionDeduplicator.java │ └── BankHashApp.java └── run.sh
Account.java
package com.bank.core;
import java.math.BigDecimal;
import java.util.Objects;
public record Account(String accountId, String holderName, BigDecimal balance) {
// Records auto-generate hashCode and equals based on all components.
// This is correct behavior for HashMap/HashSet usage.
@Override
public String toString() {
return accountId + " (" + holderName + ") : " + balance + " INR";
}
}
AccountLookupService.java
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
public class AccountLookupService {
private final Map<String, Account> accounts = new HashMap<>();
public void addAccount(Account account) {
accounts.put(account.accountId(), account);
}
public Optional<Account> findById(String accountId) {
return Optional.ofNullable(accounts.get(accountId));
}
public int size() {
return accounts.size();
}
public void printAll() {
accounts.forEach((id, account) -> System.out.println(" " + account));
}
}
TransactionDeduplicator.java
package com.bank.core;
import java.util.HashSet;
import java.util.Set;
public class TransactionDeduplicator {
private final Set<String> processedIds = new HashSet<>();
public boolean processIfNew(String transactionId) {
if (processedIds.add(transactionId)) {
return true; // new transaction, process it
}
return false; // duplicate, skip
}
public int processedCount() {
return processedIds.size();
}
}
BankHashApp.java
package com.bank.core;
import java.math.BigDecimal;
public class BankHashApp {
public static void main(String[] args) {
System.out.println("=== National Bank of India: Hash-Based Services ===");
// Account lookup with HashMap
var lookupService = new AccountLookupService();
lookupService.addAccount(new Account("SAV2001", "Rajesh", new BigDecimal("150000.00")));
lookupService.addAccount(new Account("CUR3001", "Priya", new BigDecimal("500000.00")));
lookupService.addAccount(new Account("SAV2002", "Pankaj", new BigDecimal("75000.00")));
System.out.println("\nAll accounts (" + lookupService.size() + "):");
lookupService.printAll();
System.out.println("\nLookup SAV2001: " + lookupService.findById("SAV2001").orElse(null));
System.out.println("Lookup SAV9999: " + lookupService.findById("SAV9999").orElse(null));
// Transaction deduplication with HashSet
var dedup = new TransactionDeduplicator();
System.out.println("\nTransaction deduplication:");
System.out.println(" TXN-1001 new? " + dedup.processIfNew("TXN-1001"));
System.out.println(" TXN-1002 new? " + dedup.processIfNew("TXN-1002"));
System.out.println(" TXN-1001 new? " + dedup.processIfNew("TXN-1001")); // duplicate
System.out.println(" TXN-1003 new? " + dedup.processIfNew("TXN-1003"));
System.out.println(" Processed unique transactions: " + dedup.processedCount());
// Record equality (auto-generated hashCode and equals)
var a1 = new Account("SAV2001", "Rajesh", new BigDecimal("150000.00"));
var a2 = new Account("SAV2001", "Rajesh", new BigDecimal("150000.00"));
var a3 = new Account("SAV2001", "Rajesh", new BigDecimal("200000.00"));
System.out.println("\nRecord equality:");
System.out.println(" a1.equals(a2) (same data): " + a1.equals(a2));
System.out.println(" a1.hashCode() == a2.hashCode(): " + (a1.hashCode() == a2.hashCode()));
System.out.println(" a1.equals(a3) (different balance): " + a1.equals(a3));
}
}
How to compile and run
javac -d out src/main/java/com/bank/core/*.java
java -cp out com.bank.core.BankHashApp
Expected output:
=== National Bank of India: Hash-Based Services ===
All accounts (3):
SAV2001 (Rajesh) : 150000.00 INR
CUR3001 (Priya) : 500000.00 INR
SAV2002 (Pankaj) : 75000.00 INR
Lookup SAV2001: SAV2001 (Rajesh) : 150000.00 INR
Lookup SAV9999: null
Transaction deduplication:
TXN-1001 new? true
TXN-1002 new? true
TXN-1001 new? false
TXN-1003 new? true
Processed unique transactions: 3
Record equality:
a1.equals(a2) (same data): true
a1.hashCode() == a2.hashCode(): true
a1.equals(a3) (different balance): false
What are common mistakes with HashMap and HashSet?
The most common mistake is overriding equals() without overriding hashCode(). If two objects are equal according to equals() but have different hashCode() values, HashMap will put them in different buckets and treat them as different keys.
Wrong: override equals but not hashCode
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Objects;
public class WrongHashCodeMissing {
static class AccountKey {
String accountId;
AccountKey(String accountId) { this.accountId = accountId; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof AccountKey other)) return false;
return Objects.equals(accountId, other.accountId);
}
// BUG: hashCode not overridden, uses Object.hashCode() (memory address)
}
public static void main(String[] args) {
var map = new HashMap<AccountKey, BigDecimal>();
map.put(new AccountKey("SAV2001"), new BigDecimal("150000.00"));
// Different object, same accountId
BigDecimal result = map.get(new AccountKey("SAV2001"));
System.out.println("Lookup result: " + result);
System.out.println("Expected 150000.00 but got null because hashCode differs");
System.out.println("Two objects with same accountId have different hashCodes:");
System.out.println(" key1.hashCode(): " + new AccountKey("SAV2001").hashCode());
System.out.println(" key2.hashCode(): " + new AccountKey("SAV2001").hashCode());
}
}
Expected output:
Lookup result: null
Expected 150000.00 but got null because hashCode differs
Two objects with same accountId have different hashCodes:
key1.hashCode(): 1234567890
key2.hashCode(): 987654321
Correct: override both hashCode and equals
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Objects;
public class CorrectHashCodeAndEquals {
static class AccountKey {
String accountId;
AccountKey(String accountId) { this.accountId = accountId; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof AccountKey other)) return false;
return Objects.equals(accountId, other.accountId);
}
@Override
public int hashCode() {
return Objects.hash(accountId);
}
}
public static void main(String[] args) {
var map = new HashMap<AccountKey, BigDecimal>();
map.put(new AccountKey("SAV2001"), new BigDecimal("150000.00"));
BigDecimal result = map.get(new AccountKey("SAV2001"));
System.out.println("Lookup result: " + result + " INR");
System.out.println("Works because hashCode is consistent with equals");
// Even better: use a record (auto-generates both)
System.out.println("Tip: Java records auto-generate hashCode and equals");
}
}
Expected output:
Lookup result: 150000.00 INR
Works because hashCode is consistent with equals
Tip: Java records auto-generate hashCode and equals
What about collisions and how does Java resolve them?
A collision happens when two different keys have the same bucket index. Java handles collisions in two ways, depending on the chain length:
- Linked list (default): each bucket holds a linked list of nodes. On collision, the new node is appended.
- Red-black tree (Java 8+): when a bucket's chain reaches 8 entries and the table has 64+ buckets, the chain converts to a balanced tree for O(log n) lookup.
The threshold of 8 is chosen because under a good hash function, the probability of 8 collisions in one bucket is extremely low.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class CollisionDemo {
// Deliberately bad hash: all keys hash to the same bucket
static class BadHashKey {
String value;
BadHashKey(String value) { this.value = value; }
@Override
public int hashCode() {
return 1; // all keys go to bucket 1
}
@Override
public boolean equals(Object o) {
if (!(o instanceof BadHashKey other)) return false;
return value.equals(other.value);
}
@Override
public String toString() { return value; }
}
public static void main(String[] args) {
Map<BadHashKey, String> map = new HashMap<>();
// All entries go to the same bucket
for (int i = 1; i <= 10; i++) {
map.put(new BadHashKey("ACC-" + i), "Account " + i);
}
System.out.println("Map size: " + map.size());
System.out.println("All 10 keys hash to bucket 1 (collision chain)");
System.out.println("At 8 entries, chain converts to red-black tree");
System.out.println("Lookup ACC-5: " + map.get(new BadHashKey("ACC-5")));
System.out.println("Lookup ACC-10: " + map.get(new BadHashKey("ACC-10")));
System.out.println("With good hash: O(1). With bad hash: O(log n) via tree.");
}
}
Expected output:
Map size: 10
All 10 keys hash to bucket 1 (collision chain)
At 8 entries, chain converts to red-black tree
Lookup ACC-5: Account 5
Lookup ACC-10: Account 10
With good hash: O(1). With bad hash: O(log n) via tree.
What about thread safety with HashMap?
HashMap is not thread-safe. If multiple threads read and write to a HashMap without synchronization, you can get corrupted data, infinite loops during resize (in older JVMs), or lost updates. For concurrent access, use ConcurrentHashMap.
package com.bank.core;
import java.math.BigDecimal;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class ThreadSafeHashMapDemo {
public static void main(String[] args) throws InterruptedException {
Map<String, BigDecimal> balances = new ConcurrentHashMap<>();
balances.put("SAV2001", new BigDecimal("100000.00"));
// Atomic compute: thread-safe balance update
Runnable deposit = () -> {
for (int i = 0; i < 1000; i++) {
balances.compute("SAV2001", (key, balance) ->
balance.add(new BigDecimal("100.00")));
}
};
var t1 = Thread.ofVirtual().start(deposit);
var t2 = Thread.ofVirtual().start(deposit);
t1.join();
t2.join();
System.out.println("Final balance (SAV2001): " + balances.get("SAV2001") + " INR");
System.out.println("Expected: 100000 + (2 threads * 1000 * 100) = 300000.00");
System.out.println("ConcurrentHashMap.compute() is atomic per key");
}
}
Expected output:
Final balance (SAV2001): 300000.00 INR
Expected: 100000 + (2 threads * 1000 * 100) = 300000.00
ConcurrentHashMap.compute() is atomic per key
What should a senior or principal engineer know?
At the senior level, you should understand how capacity, load factor, and rehashing affect performance. A poorly sized HashMap wastes memory or triggers frequent resizing.
At the principal level, consider:
- Initial capacity planning: if you know the map will hold 1000 entries, create it with
new HashMap<>(1334)(1000 / 0.75) to avoid resizing. - Key immutability: if a key object is mutated after being put into the map, its hashCode changes but it stays in the old bucket, making it unretrievable.
- Identity vs equality: IdentityHashMap uses
==instead of equals(), useful for tracking object references in serialization. - Weak references: WeakHashMap allows keys to be garbage collected, useful for caches.
- Iteration cost: HashMap iteration is O(capacity + size), not just O(size). A large, mostly empty map is slow to iterate.
package com.bank.core;
import java.math.BigDecimal;
import java.util.HashMap;
public class SeniorHashMapKnowledge {
public static void main(String[] args) {
// Pre-size to avoid resizing
int expectedEntries = 1000;
int initialCapacity = (int) (expectedEntries / 0.75) + 1;
var accounts = new HashMap<String, BigDecimal>(initialCapacity);
System.out.println("Senior/Principal HashMap checklist:");
System.out.println(" 1. Pre-size: new HashMap<>(" + initialCapacity + ") for " + expectedEntries + " entries");
System.out.println(" 2. Never mutate a key after putting it in the map");
System.out.println(" 3. Use ConcurrentHashMap for multi-threaded access");
System.out.println(" 4. Use records or immutable objects as keys");
System.out.println(" 5. WeakHashMap for caches that should not prevent GC");
System.out.println(" 6. Iteration cost is O(capacity + size), not O(size)");
// Demonstrate pre-sizing benefit
long start = System.nanoTime();
var preSized = new HashMap<String, BigDecimal>(1334);
for (int i = 0; i < 1000; i++) preSized.put("ACC-" + i, BigDecimal.valueOf(i * 1000));
long preSizedTime = System.nanoTime() - start;
start = System.nanoTime();
var defaultSized = new HashMap<String, BigDecimal>();
for (int i = 0; i < 1000; i++) defaultSized.put("ACC-" + i, BigDecimal.valueOf(i * 1000));
long defaultTime = System.nanoTime() - start;
System.out.println(" Pre-sized (1334): " + (preSizedTime / 1000) + " us");
System.out.println(" Default (16): " + (defaultTime / 1000) + " us");
System.out.println(" Pre-sizing avoids rehash during bulk inserts");
}
}
Expected output:
Senior/Principal HashMap checklist:
1. Pre-size: new HashMap<>(1334) for 1000 entries
2. Never mutate a key after putting it in the map
3. Use ConcurrentHashMap for multi-threaded access
4. Use records or immutable objects as keys
5. WeakHashMap for caches that should not prevent GC
6. Iteration cost is O(capacity + size), not O(size)
Pre-sized (1334): 850 us
Default (16): 1200 us
Pre-sizing avoids rehash during bulk inserts
What are common interview follow-up questions?
- What happens if you use a mutable object as a HashMap key and then modify it? (The object stays in the old bucket based on the old hashCode. A get() with the modified key computes a different bucket, so the entry is lost.)
- What is the difference between HashMap and LinkedHashMap? (LinkedHashMap maintains insertion order using a doubly linked list through all entries. Iteration follows insertion order.)
- What is the difference between HashMap and TreeMap? (TreeMap stores entries sorted by key using a red-black tree. Lookups are O(log n) instead of O(1), but you get sorted iteration.)
- Why is the default load factor 0.75? (It is a trade-off between space and time. Lower load factor means fewer collisions but more memory. Higher load factor saves memory but increases collisions.)
- Can HashSet contain duplicate objects? (No. If you add an object that equals() an existing element and has the same hashCode(), the add() returns false and the set is unchanged.)
- What is the time complexity of HashMap in the worst case? (O(log n) per operation since Java 8, because long collision chains convert to red-black trees. Before Java 8, worst case was O(n).)
Visual Overview
HashMap Internal Structure (Capacity 16)
==========================================
Bucket Array (Node<K,V>[] table)
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
│null │null │null │null │null │null │null │null │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │ 15 │
│null │null │null │null │null │null │Node │null │
└─────┴─────┴─────┴─────┴─────┴─────┴──┬──┴─────┘
│
▼
┌──────────────────┐
│ SAV2001=150000.00 │
│ next ─────────────┤
└──────────────────┬┘
│
▼
┌──────────────────┐
│ CUR3001=500000.00 │
│ next = null │
└──────────────────┘
put("SAV2001", 150000):
hashCode("SAV2001") = -1708646498
bucket = hash & (16-1) = 14
bucket[14] is empty, insert node
put("CUR3001", 500000):
hashCode("CUR3001") = 2041746654
bucket = hash & (16-1) = 14
bucket[14] has SAV2001, chain as linked list
get("CUR3001"):
compute bucket 14
walk chain: SAV2001.equals(CUR3001)? No
CUR3001.equals(CUR3001)? Yes, return 500000
HashSet Backed by HashMap
==========================
HashSet<String> internally HashMap<String, PRESENT>
┌──────────────┐ ┌──────────────────────┐
│ add("TXN-1") │ ───────────────────────> │ put("TXN-1", PRESENT)│
│ add("TXN-2") │ ───────────────────────> │ put("TXN-2", PRESENT)│
│ add("TXN-1") │ ───────────────────────> │ put("TXN-1", PRESENT)│
│ returns false│ │ key exists, no change│
└──────────────┘ └──────────────────────┘
contains("TXN-1") ──> map.containsKey("TXN-1") ──> true
Key Takeaway
A hash table gives you O(1) average-time lookups by converting a key into a bucket index through a hash function. In Java, HashMap stores key-value pairs and HashSet stores unique elements, with HashSet using a HashMap internally where each element is a key mapped to a dummy value.
When you call put() on a HashMap, it computes the key's hashCode(), spreads the bits, and finds the bucket. If another key already occupies that bucket (a collision), the new entry is chained as a linked list node. Starting in Java 8, when a chain grows to 8 entries, it converts to a red-black tree for O(log n) worst-case performance.
The most critical rule for custom objects is: always override hashCode() and equals() together. If two objects are equal by equals() but have different hashCode() values, HashMap puts them in different buckets and cannot find one using the other as a lookup key. Java records solve this automatically by generating both methods from all components.
In our National Bank of India project, we used HashMap for account lookups by ID and HashSet for deduplicating transaction IDs. The Account record auto-generated correct hashCode and equals, so it worked as a HashMap key without any manual overrides.
At the senior level, pre-size your HashMap if you know the expected entry count, use ConcurrentHashMap for multi-threaded access, and never mutate a key object after putting it in the map. The default capacity of 16 with a load factor of 0.75 resizes at 12 entries, doubling the array and rehashing all entries.
Remember one sentence: HashMap computes a bucket index from hashCode(), chains collisions as a linked list that becomes a tree at 8 entries, and requires hashCode() and equals() to agree for correct lookups.
---