Ashifur nahid

Posted on Nov 26

HashMap in Java - Complete Documentation

#algorithms #computerscience #java

Overview

HashMap is a widely-used data structure in Java that implements the Map interface for storing key-value pairs. It delivers O(1) time complexity for fundamental operations like insertion and retrieval under typical conditions.

Internal Architecture

Bucket Array Structure

HashMap utilizes an array of nodes as its foundation, commonly referred to as the bucket array. Each bucket can accommodate multiple entries through either a linked list or tree structure when collisions occur.

Node Composition

Every entry in the HashMap is represented by a Node object that implements the Map.Entry interface:

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;      // Hash code of the key
    final K key;         // The key
    V value;             // Associated value
    Node<K, V> next;     // Reference to next node
}

Core Operations

1. Insertion Process

Hash Computation:

The key's hashCode() method generates a hash value
The hash is converted to an array index using: index = (n - 1) & hash
Here, n represents the bucket array size

Bucket Placement:

If the target bucket is empty, a new node is created
If occupied, the node is appended to the existing linked list or tree

2. Collision Resolution

When multiple keys map to the same index:

Linked List: Used for fewer than 8 nodes
Binary Search Tree: Automatically implemented for 8+ nodes, improving search from O(n) to O(log n)

3. Search Operation

Hash code is calculated and converted to an index
The bucket at that index is examined
If necessary, the linked list or tree is traversed to locate the key

4. Deletion

Index is determined via the key's hash code
The bucket is traversed to find and remove the target node
Pointers are adjusted to maintain structure integrity

Performance Optimization

Load Factor

The load factor (default: 0.75) determines when resizing occurs:

Resizing triggers when the map reaches 75% capacity
Maintains optimal performance by preventing excessive collisions

Dynamic Resizing

When elements > capacity × load factor:

Bucket array size doubles
All elements are rehashed and redistributed
Ensures balanced distribution across buckets

Working Example: Collision Scenario

Initial Setup

HashMap<Integer, String> map = new HashMap<>();
map.put(1, "Apple");
map.put(17, "Banana");
map.put(33, "Cherry");

Index Calculation (Array size = 16)

index(1)  = (16 - 1) & 1  = 1
index(17) = (16 - 1) & 17 = 1
index(33) = (16 - 1) & 33 = 1

Result: All keys collide at index 1

Collision Resolution Structure

Bucket[1] → Node(1, "Apple") → Node(17, "Banana") → Node(33, "Cherry")

Retrieval Process

map.get(17);  // Returns "Banana"

Calculate index: 1
Navigate to bucket 1
Traverse linked list to find key 17
Return associated value

Essential Methods

Method	Description
`put(K key, V value)`	Inserts or updates a key-value pair
`get(Object key)`	Retrieves value associated with key
`remove(Object key)`	Removes the entry for specified key
`containsKey(Object key)`	Checks if key exists
`containsValue(Object value)`	Checks if value exists
`size()`	Returns number of entries
`isEmpty()`	Checks if map is empty
`clear()`	Removes all entries
`clone()`	Creates a shallow copy

Code Example

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // Insert entries
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Orange", 3);

        // Access entries
        System.out.println(map.get("Apple"));   // Output: 1
        System.out.println(map.get("Banana"));  // Output: 2

        // Check operations
        System.out.println(map.containsKey("Orange"));  // true
        System.out.println(map.size());                 // 3

        // Remove an entry
        map.remove("Orange");
        System.out.println(map.size());  // 2
    }
}

Performance Characteristics

Time Complexity

Best Case: O(1) for insert, search, and delete
Worst Case: O(n) with excessive collisions (degraded to linked list)
With Tree Structure: O(log n) when 8+ collisions occur

Space Complexity

O(n) where n is the number of key-value pairs

Key Considerations

Null Handling

One null key is permitted
Multiple null values are allowed

Thread Safety

HashMap is not synchronized
For concurrent access, use ConcurrentHashMap or external synchronization

Hash Function Quality

Performance depends heavily on proper hashCode() implementation
Poor hash functions increase collision probability

Best Practices

Initial Capacity: Set appropriate initial capacity to minimize resizing
Load Factor: Use default 0.75 unless specific requirements exist
Key Immutability: Use immutable objects as keys to prevent inconsistencies
Null Safety: Handle potential null returns from get() method
Thread Safety: Use ConcurrentHashMap for multi-threaded environments

Summary

HashMap provides an efficient mechanism for key-value storage through intelligent hashing, collision resolution, and dynamic resizing. Its combination of array-based indexing and linked list/tree structures ensures scalability and performance, making it an indispensable tool in Java development.

DEV Community