Course contentsShow
← Java
Lesson 1111 of 2,87026. Map ImplementationsFree lesson

remove() Operation: Deletion Process

How HashMap locates and removes entries, unlinking nodes from bucket chains while maintaining structure.

What You'll Learn

You'll learn how HashMap's remove() method locates and removes an entry by traversing bucket chains and unlinking nodes while preserving the structure.

The Deletion Process

When you call remove(key) on a HashMap, it must find the entry and cleanly extract it from the bucket chain without breaking the links between remaining nodes.

The process follows these steps:

1. Hash and Locate Bucket

Just like get() and put(), remove() starts by computing the key's hash code, applying secondary hashing, and calculating the bucket index. This tells HashMap which bucket chain to search.

2. Traverse the Chain

HashMap walks through the linked list of nodes in that bucket, comparing each node's key with the target key using equals(). It keeps track of both the current node and the previous node.

3. Unlink the Node

When the matching node is found, HashMap must "unlink" it:

  • If it's the first node in the bucket: Update the bucket array to point to the second node (or null if it was the only node)
  • If it's in the middle or end: Update the previous node's next reference to skip over the deleted node, pointing directly to the node after it

Analogy: Imagine removing a person from a conga line. You need to connect the person behind them to the person in front of them, so the line stays intact.

4. Return the Old Value

The remove() method returns the value that was associated with the removed key (or null if the key wasn't found).

5. Decrement Size

Finally, HashMap decreases its internal size counter by one.

Key Takeaway: HashMap's remove() locates entries using the same hash-and-search process as get(), then carefully unlinks the node from its bucket chain by adjusting references to maintain structural integrity.