Java HashMap and LinkedHashMap: Key-Value Stores, Hashing, and Buckets

What Is a HashMap in Java?

A HashMap is a collection that stores data in key-value pairs.

The general structure is:

Key → Value

For example:

101 → "Rahul"102 → "Priya"103 → "Amit"

The key is used to locate the corresponding value.

You can create a HashMap using:

import java.util.HashMap;
HashMap<Integer, String> students = new HashMap<>();

Here:

• Integer is the key type.

• String is the value type.

• Each key maps to one value.

Basic HashMap Example

import java.util.HashMap;
public class Main {
    public static void main(String[] args) {
        HashMap<Integer, String> students = new HashMap<>();
        students.put(101, "Rahul");
        students.put(102, "Priya");
        students.put(103, "Amit");
        System.out.println(students);
    }
}

A possible output is:

{
    101=Rahul, 102=Priya, 103=Amit
}

However, you should not depend on this order with HashMap.

What Is a Key-Value Pair?

A map stores information in pairs.

Consider:

HashMap<String, Integer> marks = new HashMap<>();
marks.put("Math", 85);
marks.put("Java", 92);
marks.put("English", 78);

The data looks conceptually like:

Math → 85Java → 92English → 78

The left side is the key and the right side is the value.

You retrieve a value by providing its key:

System.out.println(marks.get("Java"));

Output:

92

HashMap Does Not Use Indexes

An ArrayList uses positions:

list.get(0);
list.get(1);
list.get(2);

A HashMap uses keys:

map.get("Java");

This makes a map useful when you naturally identify information using a key.

For example:

HashMap<Integer, String> employees = new HashMap<>();
employees.put(1001, "Amit");
employees.put(1002, "Riya");
employees.put(1003, "John");

You can directly search for employee 1002:

System.out.println(employees.get(1002));

Output:

Riya

Creating a HashMap

The most common syntax is:

HashMap<KeyType, ValueType> map = new HashMap<>();

Example:

HashMap<String, String> countries = new HashMap<>();

Another common approach is to program against the Map interface:

Map<String, Integer> scores = new HashMap<>();

This is often preferable because the variable depends on the interface rather than a specific implementation.

import java.util.HashMap;
import java.util.Map;
Map<String, Integer> scores = new HashMap<>();

Adding Elements with put()

Use put() to add or update a key-value pair.

Map<String, Integer> scores = new HashMap<>();
scores.put("Java", 90);
scores.put("Python", 85);
scores.put("SQL", 88);

The map now contains:

Java → 90Python → 85SQL → 88

Updating an Existing Key

A key can appear only once in a Map.

If you call put() with an existing key, its value is replaced.

Map<String, Integer> scores = new HashMap<>();
scores.put("Java", 90);
scores.put("Java", 95);
System.out.println(scores);

Output:

{
    Java=95
}

The second put() updates the existing value.

It does not create another Java key.

Can HashMap Have Duplicate Keys?

No.

A HashMap cannot contain two equal keys.

For example:

Map<Integer, String> users = new HashMap<>();
users.put(1, "Amit");
users.put(1, "Rahul");

The result contains only:

1 → Rahul

The second value replaces the first one.

Can HashMap Have Duplicate Values?

Yes.

Values do not need to be unique.

Map<String, String> employees = new HashMap<>();
employees.put("E101", "Amit");
employees.put("E102", "Amit");
employees.put("E103", "Priya");

This is completely valid.

Two different keys can point to the same value.

E101 → AmitE102 → AmitE103 → Priya

Retrieving Values with get()

Use get() to retrieve a value using its key.

Map<Integer, String> users = new HashMap<>();
users.put(101, "Amit");
users.put(102, "Priya");
String name = users.get(102);
System.out.println(name);

Output:

Priya

What Happens When a Key Does Not Exist?

If the key is not present, get() normally returns null.

Map<Integer, String> users = new HashMap<>();
users.put(101, "Amit");
System.out.println(users.get(999));

Output:

null

Therefore, be careful when immediately unboxing the result into a primitive.

For example:

int value = map.get(999);

can cause a NullPointerException if the map returns null.

Checking Keys with containsKey()

Use containsKey() when you want to know whether a key exists.

Map<Integer, String> users = new HashMap<>();
users.put(101, "Amit");
if (users.containsKey(101)) {
    System.out.println("User exists");
}

Output:

User exists

Checking Values with containsValue()

You can also check whether a particular value exists:

if (users.containsValue("Amit")) {
    System.out.println("Value found");
}

For large maps, key-based lookup is generally the more important operation because maps are designed primarily around keys.

Removing Entries

Use remove() to delete a key-value pair.

Map<Integer, String> users = new HashMap<>();
users.put(101, "Amit");
users.put(102, "Priya");
users.remove(101);
System.out.println(users);

The entry for key 101 is removed.

Getting the Size

Use size():

System.out.println(users.size());

If the map contains three key-value pairs:

3

Checking Whether a HashMap Is Empty

Use:

map.isEmpty()

Example:

if (users.isEmpty()) {
    System.out.println("Map is empty");
}

Removing All Entries

Use clear():

users.clear();

After this operation, the map contains no mappings.

How Hashing Works in HashMap

The most important concept behind HashMap is hashing.

When you add a key:

map.put("Java", 90);

Java uses the key's hash information to determine where the entry should be stored internally.

Conceptually:

Key↓hashCode()↓Hash calculation↓Bucket↓Stored entry

This is why HashMap can provide very fast average-case key lookup.

What Is a Bucket?

A bucket is an internal location used by a hash-based map to organize entries.

You can imagine a simplified structure like this:

Bucket 0 → EntryBucket 1 → EntryBucket 2 → EntryBucket 3 → EntryBucket 4 → EntryBucket 5 → Entry

When a key is inserted, its hash is used to determine an appropriate bucket.

For example:

"Java"↓hashCode()↓hash value↓bucket selection↓stored entry

The exact internal calculation is an implementation detail and should not be treated as a fixed formula in application code.

What Is hashCode()?

Every Java object inherits a hashCode() method from Object.

Example:

String key = "Java";
System.out.println(key.hashCode());

The returned integer is used by hash-based collections as part of locating entries.

Important:

A hash code is not a unique ID.

Different objects can produce the same hash code.

This situation is called a hash collision.

What Is a Hash Collision?

A hash collision happens when different keys produce the same hash value or otherwise map to the same bucket.

Conceptually:

Key A → Hash → Bucket 5Key B → Hash → Bucket 5

Both entries may therefore need to be handled within the same bucket.

HashMap is designed to handle collisions internally.

How HashMap Handles Collisions

Modern Java implementations use a node-based structure for entries and can transform heavily populated buckets into a tree structure under certain conditions.

Conceptually:

Bucket | +-- Entry A | +-- Entry B | +-- Entry C

For sufficiently large collision chains, Java can use a balanced tree structure rather than keeping everything in a simple linked chain.

The exact thresholds and implementation details are JDK-specific and should not be relied upon as API behavior.

Why hashCode() and equals() Matter

Hash-based collections depend on both:

hashCode()

and

equals()

For objects used as keys, the important contract is:

If two objects are equal according to equals(), they must return the same hashCode().

For example:

class Student {
    int id;
    Student(int id) {
        this.id = id;
    } @Override public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Student)) return false;
        Student other =(Student) obj;
        return id == other.id;
    } @Override public int hashCode() {
        return Integer.hashCode(id);
    }
}

Now two Student objects with the same ID can behave consistently as hash-based keys.

Why Mutable Keys Can Be Dangerous

Be careful when using mutable objects as HashMap keys.

Suppose the fields used by equals() and hashCode() change after the object is inserted.

The map may no longer be able to find the entry using the modified key.

For example:

Student student = new Student(101);
Map<Student, String> map = new HashMap<>();
map.put(student, "Amit");
// Changing fields that participate in equality/hashing
// can make later lookup unreliable.

For map keys, immutable objects are often easier and safer to reason about.

Common examples include:

StringIntegerLongUUID

Null Keys in HashMap

HashMap permits a null key.

Example:

Map<String, Integer> map = new HashMap<>();
map.put(null, 100);
System.out.println(map.get(null));

Output:

100

A HashMap can have only one null key because keys are unique.

It can also contain multiple null values:

map.put("A", null);
map.put("B", null);

Iterating Through a HashMap

You can iterate through a map using entrySet().

Map<String, Integer> marks = new HashMap<>();
marks.put("Java", 90);
marks.put("Python", 85);
marks.put("SQL", 88);
for (Map.Entry<String, Integer> entry : marks.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

This gives access to both the key and value.

Iterating Through Keys

Use keySet():

for (String subject : marks.keySet()) {
    System.out.println(subject);
}

Iterating Through Values

Use values():

for (Integer mark : marks.values()) {
    System.out.println(mark);
}

Using forEach()

Modern Java also provides a convenient forEach() method:

marks.forEach((subject, mark) -> System.out.println(subject + " = " + mark));

This is concise and useful when the operation is simple.

HashMap Does Not Guarantee Order

One of the most important rules is:

HashMap does not guarantee a predictable iteration order.

For example:

Map<Integer, String> map = new HashMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");
System.out.println(map);

You should not assume the output will follow:

3, 1, 2

or:

1, 2, 3

The iteration order is not part of the HashMap contract.

If predictable insertion order matters, consider LinkedHashMap.

What Is LinkedHashMap?

LinkedHashMap is a Map implementation that combines hash-based lookup with a linked structure used to maintain iteration order.

Import it with:

import java.util.LinkedHashMap;

Example:

Map<String, Integer> marks = new LinkedHashMap<>();
marks.put("Java", 90);
marks.put("Python", 85);
marks.put("SQL", 88);

When iterating, the entries normally appear in insertion order:

JavaPythonSQL

LinkedHashMap Preserves Insertion Order

Consider:

Map<Integer, String> users = new LinkedHashMap<>();
users.put(103, "Amit");
users.put(101, "Priya");
users.put(102, "Rahul");
for (Map.Entry<Integer, String> entry : users.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

Output:

103 = Amit101 = Priya102 = Rahul

The insertion order is preserved.

HashMap vs LinkedHashMap

LinkedHashMap and Access Order

LinkedHashMap can also be configured for access-order iteration.

The normal constructor:

new LinkedHashMap<>()

uses insertion-order iteration.

Another constructor allows you to specify access ordering:

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);

The final true means access order is enabled.

When entries are accessed, their relative order can change.

This behavior is useful for certain cache implementations.

LinkedHashMap Example with Access Order

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 10);
map.put("B", 20);
map.put("C", 30);
map.get("A");
map.forEach((key, value) -> System.out.println(key + " = " + value));

Because access ordering is enabled, accessing "A" affects its position during iteration.

This makes LinkedHashMap useful as a building block for some least-recently-used (LRU) cache designs.

HashMap Time Complexity

For typical hash distributions, basic operations such as:

put()get()remove()containsKey()

have average-case complexity close to:

O(1)

However, this is an average-case expectation, not an unconditional guarantee.

Performance can be affected by factors such as:

• hash distribution

• collisions

• resizing

• key equality checks

• implementation details

HashMap Resizing

A HashMap maintains an internal capacity and uses a load factor to decide when resizing is needed.

The commonly used default load factor is:

0.75

Conceptually:

capacity × load factor

determines a threshold at which the table is resized.

For example, if the capacity were:

16

and the load factor were:

0.75

the threshold would initially be around:

12

When the map grows beyond the relevant threshold, it can resize its internal table.

Why Resizing Matters

Resizing requires internal work to reorganize entries.

If you know approximately how many entries you will store, providing a suitable initial capacity can sometimes reduce unnecessary resizing.

For example:

Map<Integer, String> users = new HashMap<>(1000);

However, the constructor argument represents initial capacity rather than a strict promise that exactly that many mappings can be stored without resizing.

HashMap with Custom Objects as Keys

You can use your own classes as keys.

Example:

class Product {
    private final int id;
    Product(int id) {
        this.id = id;
    } public int getId() {
        return id;
    } @Override public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Product)) return false;
        Product other =(Product) obj;
        return id == other.id;
    } @Override public int hashCode() {
        return Integer.hashCode(id);
    }
}

Now:

Map<Product, String> products = new HashMap<>();
Product p1 = new Product(101);
products.put(p1, "Laptop");

The implementation of equals() and hashCode() determines how these objects behave as keys.

Useful HashMap Methods

Some frequently used methods are:

getOrDefault()

getOrDefault() is useful when a key may not exist.

Map<String, Integer> scores = new HashMap<>();
scores.put("Java", 90);
int pythonScore = scores.getOrDefault("Python", 0);
System.out.println(pythonScore);

Output:

This avoids manually checking for a missing key in simple cases.

putIfAbsent()

Use putIfAbsent() when you want to insert a value only if the key does not already have a mapping.

Map<String, Integer> scores = new HashMap<>();
scores.put("Java", 90);
scores.putIfAbsent("Java", 100);
System.out.println(scores.get("Java"));

Output:

90

The existing value remains unchanged.

merge()

merge() is particularly useful for counting and accumulating values.

For example:

Map<String, Integer> counts = new HashMap<>();
counts.merge("Java", 1, Integer::sum);
counts.merge("Java", 1, Integer::sum);
counts.merge("Java", 1, Integer::sum);
System.out.println(counts.get("Java"));

Output:

3

This pattern is useful when building frequency maps.

Counting Words with HashMap

A practical example is counting word frequency.

import java.util.HashMap;
import java.util.Map;
public class Main {
    public static void main(String[] args) {
        String[] words = {
            "java", "python", "java", "sql", "java", "python"
        };
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
            counts.merge(word, 1, Integer::sum);
        } System.out.println(counts);
    }
}

The result represents how many times each word occurred.

Conceptually:

java → 3python → 2sql → 1

When Should You Use HashMap?

HashMap is a good choice when:

• you need key-value storage

• fast average-case key lookup matters

• ordering is not required

• you frequently add, retrieve, update, or remove mappings

• you want a general-purpose map implementation

Example:

Map<Integer, User> users = new HashMap<>();

This is suitable for quickly finding users by ID.

When Should You Use LinkedHashMap?

Choose LinkedHashMap when:

• you need key-value storage

• you want predictable iteration order

• insertion order matters

• you are building certain cache-like structures

• you want hash-based lookup with ordering information

Example:

Map<String, String> settings = new LinkedHashMap<>();
settings.put("theme", "dark");
settings.put("language", "English");
settings.put("font", "large");

When displayed or iterated, the order can remain predictable.

HashMap vs TreeMap

TreeMap is another important Map implementation.

Map<Integer, String> map = new TreeMap<>();

Unlike HashMap, TreeMap maintains its keys according to their ordering.

A simple comparison:

HashMap vs Hashtable

Hashtable is an older Java collection.

Modern applications generally use alternatives such as:

HashMap

or, when concurrent access is required:

ConcurrentHashMap

Hashtable is synchronized and has legacy design characteristics. It also does not permit null keys or null values.

Is HashMap Thread-Safe?

No.

HashMap is not designed for unsynchronized concurrent modification by multiple threads.

If multiple threads need to update a shared map concurrently, consider an appropriate concurrent collection such as:

ConcurrentHashMap

Example:

Map<String, Integer> map = new ConcurrentHashMap<>();

The correct choice depends on the application's concurrency requirements.

Common HashMap Mistakes

Mistake 1: Assuming HashMap Is Ordered

Incorrect assumption:

HashMap

always returns entries in insertion order.

It does not guarantee that.

Use LinkedHashMap when insertion order is required.

Mistake 2: Expecting Duplicate Keys

This:

map.put("A", 10);
map.put("A", 20);

does not create two "A" keys.

The second operation replaces the previous mapping.

Mistake 3: Forgetting About null

This can return null:

Integer value = map.get("missing");

Be careful when converting the result to a primitive:

int value = map.get("missing");

If the mapping is absent, unboxing null can cause NullPointerException.

Mistake 4: Using Mutable Objects as Keys Carelessly

If fields involved in equals() or hashCode() change after insertion, lookups can become problematic.

Prefer stable, immutable key data when practical.

Mistake 5: Implementing equals() Without hashCode()

This is a common error with custom keys.

If you override:

equals()

you should also implement:

hashCode()

according to Java's object contract.

Complete HashMap Example

import java.util.HashMap;
import java.util.Map;
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> users = new HashMap<>();
        // Add users
        users.put(101, "Amit");
        users.put(102, "Priya");
        users.put(103, "Rahul");
        // Update
        users.put(102, "Priya Sharma");
        // Retrieve
        System.out.println(users.get(102));
        // Check key
        System.out.println(users.containsKey(101));
        // Remove
        users.remove(103);
        // Iterate
        for (Map.Entry<Integer, String> entry : users.entrySet()) {
            System.out.println( entry.getKey() + " = " + entry.getValue());
        }
    }
}

This example demonstrates the most common operations you will perform with a HashMap.

Complete LinkedHashMap Example

import java.util.LinkedHashMap;
import java.util.Map;
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> users = new LinkedHashMap<>();
        users.put(103, "Amit");
        users.put(101, "Priya");
        users.put(102, "Rahul");
        for (Map.Entry<Integer, String> entry : users.entrySet()) {
            System.out.println( entry.getKey() + " = " + entry.getValue());
        }
    }
}

The iteration order follows the insertion order:

103 = Amit101 = Priya102 = Rahul

Real-World Uses of HashMap

HashMap is widely useful in application development.

User Lookup

User ID → User Object

Product Lookup

Product ID → Product

Configuration

Setting Name → Setting Value

Frequency Counting

Word → Number of Occurrences

Caching

Request Key → Cached Result

Database-Like Lookup

Employee ID → Employee Details

Real-World Uses of LinkedHashMap

LinkedHashMap is useful when the order of entries should remain predictable.

Examples include:

• ordered configuration output

• preserving the order of imported records

• displaying recently processed items

• simple cache structures

• predictable JSON-like data construction

• maintaining insertion order while performing key-based lookup

HashMap Mental Model

A simple way to remember how HashMap works is:

HashMap | Key + Value | hashCode() | Hash | Bucket | Find matching key | equals() | Value

The hash helps narrow down where to look, while equality determines whether the key matches.

HashMap vs LinkedHashMap: Quick Decision Guide

Use:

HashMap

when you need a general-purpose map and do not care about iteration order.

Use:

LinkedHashMap

when you need predictable iteration order in addition to hash-based map behavior.

Use:

TreeMap

when sorted key order is required.

Use:

ConcurrentHashMap

when you need a map designed for concurrent access.

Frequently Asked Questions

What is HashMap in Java?

HashMap is a Map implementation that stores key-value pairs and uses hashing to support efficient average-case key-based operations.

Does HashMap allow duplicate keys?

No. A map can contain only one mapping for a given key according to its equality rules. Adding the same key again replaces its value.

Does HashMap allow duplicate values?

Yes. Multiple different keys can map to the same value.

Does HashMap maintain insertion order?

No. HashMap does not guarantee a predictable iteration order.

Which Java collection preserves insertion order?

LinkedHashMap preserves insertion order during normal insertion-order iteration.

What is a bucket in HashMap?

A bucket is an internal location in the hash table where entries associated with particular hash results are organized.

Why are hashCode() and equals() important?

Hash-based collections use hash codes to narrow down candidate entries and equality checks to determine whether keys match. Equal objects must have equal hash codes.

Can HashMap contain null?

Yes. HashMap permits a null key and multiple null values.

Is HashMap thread-safe?

No. For concurrent access, use an appropriate concurrent collection such as ConcurrentHashMap when its semantics fit the application.

Which is faster, HashMap or LinkedHashMap?

Both provide similar average-case complexity for basic hash-based operations. LinkedHashMap maintains additional ordering information, so it can have extra memory and bookkeeping overhead.

When should I use LinkedHashMap instead of HashMap?

Use LinkedHashMap when you need predictable iteration order, especially insertion order or access-order behavior.

Graphics and Design Ideas

Graphic 1: HashMap Internal Concept

Create a clean diagram:

             KEY
↓
hashCode()
↓
Hash Calculation
↓
┌─────────┐
          │ Bucket 0│
          ├─────────┤
          │ Bucket 1│
          ├─────────┤
          │ Bucket 2│ ← Entry
          ├─────────┤
          │ Bucket 3│
          └─────────┘

Graphic 2: HashMap vs LinkedHashMap

Show two side-by-side structures:

HashMap LinkedHashMapBucket → Entry Bucket → EntryBucket → Entry Bucket → EntryBucket → Entry Bucket → Entry↓Linked Order A → B → C

Graphic 3: Key-Value Concept

Use a simple visual:

101 → Amit102 → Priya103 → Rahul

Label the left side Key and the right side Value.

Graphic 4: Hash Collision

Key A ──┐
        ├──→ Bucket 5
Key B ──┘

This helps beginners understand why multiple keys can sometimes be associated with the same bucket.