Back to String & String Pool
Q7Question 7 of 13

How do HashMap and HashSet work internally in Java

Answer: A hash table is a data structure that maps keys to values using a hash function for O(1) average-time lookups, and in Java, HashMap and HashSet are the standard implementations for key-value pairs and unique element storage respectively.

Key Concepts
  • A hash table maps keys to values using a hash function that converts the key into a bucket index for O(1) average-time lookups.
  • HashMap stores key-value pairs and allows one null key, while HashSet stores unique elements and is backed by a HashMap internally.
  • The hashCode() method returns an integer used to compute the bucket index, and equals() is used to resolve collisions within the same bucket.
  • When two keys hash to the same bucket, Java uses a linked list (and converts to a red-black tree at 8 entries) to handle the collision.
  • The default initial capacity is 16 buckets with a load factor of 0.75, meaning the map resizes when 12 slots are filled.
  • Always override both hashCode() and equals() together, or HashMap and HashSet will behave incorrectly for custom objects.
  • For thread safety, use ConcurrentHashMap instead of synchronizing a regular HashMap.

Definition

A hash table is a data structure that maps keys to values using a hash function for O(1) average-time lookups, and in Java, HashMap and HashSet are the standard implementations for key-value pairs and unique element storage respectively.
  • 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).

JAVA
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());
    }
}
TEXT
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.

JAVA
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");
    }
}
TEXT
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.

JAVA
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"));
    }
}
TEXT
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?

FeatureHashMapHashSet
StoresKey-value pairsUnique elements (keys only)
InterfaceMapSet
Add methodput(key, value)add(element)
Retrieveget(key) returns valuecontains(element) returns boolean
Null keysOne null key allowedOne null element allowed
Internal structureNode arrayBacked by HashMap
Use caseLookup by key (account ID to balance)Deduplication (processed transaction IDs)
Duplicate handlingOverwrites value for existing keyReturns false, element not added
JAVA
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"));
    }
}
TEXT
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

DIAGRAM
bank-hash-service/
├── src/
│   └── main/
│       └── java/
│           └── com/
│               └── bank/
│                   └── core/
│                       ├── Account.java
│                       ├── AccountLookupService.java
│                       ├── TransactionDeduplicator.java
│                       └── BankHashApp.java
└── run.sh

Account.java

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

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

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

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

BASH
javac -d out src/main/java/com/bank/core/*.java
java -cp out com.bank.core.BankHashApp
TEXT
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

JAVA
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());
    }
}
TEXT
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

JAVA
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");
    }
}
TEXT
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:

  1. Linked list (default): each bucket holds a linked list of nodes. On collision, the new node is appended.
  2. 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.

JAVA
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.");
    }
}
TEXT
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.

JAVA
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");
    }
}
TEXT
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.
JAVA
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");
    }
}
TEXT
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

DIAGRAM
 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
DIAGRAM
 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.

---

Share
Use ← → arrow keys to navigate