Suppose your application stores 1 million employee records. Initially, you used an ArrayList, but searching an employee by employeeId has become very slow. How would you improve the performance?
Suppose your application stores 1 million employee records. Initially, you used an ArrayList<Employee>, but searching an employee by employeeId has become very slow. How would you improve the performance?
2-Line Answer
Instead of searching through an ArrayList, store employees in a HashMap<Integer, Employee> where the key is employeeId. A HashMap uses hashing to directly locate the correct bucket, making lookups much faster than scanning every employee one by one.
Detailed Answer
This is one of those interview questions that looks simple.
Many candidates immediately answer, "I'll use a HashMap because searching is O(1)." That's correct, but experienced interviewers don't stop there.
The next question usually is:
"Why is HashMap O(1)?"
If you can't explain that, the interviewer knows you've memorized the answer instead of understanding it.
Let's build the answer from scratch.
Why is ArrayList Slow?
Imagine you have one million employees stored in an ArrayList.
Now someone asks for Employee ID 987654.
How does Java find it?
It starts from the first employee.
Then the second.
Then the third.
And keeps checking until it finds the correct employee.
If the employee is at the end of the list, Java may have to check almost one million records.
That's called Linear Search.
Its time complexity is:
As the number of employees grows, the search time grows too.
That's why your application starts feeling slow.
Why HashMap is Faster
Instead of searching every employee one by one, we can organize them differently.
Here,
- Key → Employee ID
- Value → Employee Object
Now, when someone asks for Employee ID 987654, Java doesn't scan every employee.
It directly jumps to the location where that employee is likely stored.
That's why searching becomes much faster.
How Does HashMap Actually Work?
This is where interviewers start asking deeper questions.
A HashMap doesn't store data randomly.
Internally, it contains an array called Buckets.
Imagine something like this:
Each bucket can store one or more entries.
When you insert an employee,
Java doesn't simply place it in the next empty bucket.
It first calculates a number called the Hash Code.
Step 1: hashCode()
Every key has a hash code.
For Integer keys,
returns
For custom objects,
Java uses the hashCode() method.
Step 2: Bucket Index Calculation
The hash code is converted into a bucket index.
Simplified version:
Employee 101 is stored in Bucket 5.
Now suppose someone searches:
Java performs the same calculation.
It immediately jumps to Bucket 5 instead of checking one million employees.
That's the magic behind HashMap.
What is a Collision?
Now imagine another employee.
Employee ID
Oops.
Employee 117 also belongs to Bucket 5.
Now both employees want the same bucket.
This situation is called a Collision.
Hash collisions are completely normal.
A HashMap is designed to handle them.
How Does HashMap Handle Collisions?
In older Java versions, collided entries were stored as a Linked List.
When searching for Employee 117,
Java enters Bucket 5 and checks the linked list one node at a time.
Starting from Java 8,
If one bucket becomes too crowded (more than 8 entries) and the table is large enough, Java converts that linked list into a Red-Black Tree.
Searching in a tree is much faster than traversing a long linked list.
Where Does equals() Come Into the Picture?
Another favorite interview question.
Suppose two keys produce the same bucket.
Java now has multiple entries inside one bucket.
How does it know which one is correct?
It compares the keys using equals().
First,
Java uses hashCode() to find the bucket.
Then,
it uses equals() to identify the exact key inside that bucket.
Both methods work together.
Not one.
Both.
Why Should hashCode() and equals() Always Match?
Suppose two Employee objects represent the same employee.
If e1.equals(e2) returns true then e1.hashCode() and e2.hashCode()
must return the same value.
Otherwise,
they'll be placed in different buckets.
Later,
HashMap won't be able to find the object correctly.
That's why Java's contract says:
Equal objects must have equal hash codes.
What Happens When HashMap Becomes Full?
A HashMap doesn't keep growing forever.
It has a default capacity of 16.
It also has a Load Factor of 0.75.
That means,
once around 12 buckets are occupied,
HashMap automatically creates a larger internal array.
This process is called Resizing.
During resizing,
every existing entry is recalculated and moved into its new bucket.
This operation is expensive.
That's why, if you already know you'll store around one million employees, it's a good idea to initialize the HashMap with a larger capacity instead of letting it resize repeatedly.
Time Complexity
| Operation | ArrayList | HashMap |
|---|---|---|
| Search by Employee ID | O(n) | O(1) Average |
| Insert | O(1) (at end) | O(1) Average |
| Delete | O(n) | O(1) Average |
Worst-case lookup in a HashMap can still become O(n) if every key lands in the same bucket, although Java 8 reduces this to O(log n) in heavily collided buckets by converting them into Red-Black Trees.
Interview Follow-up Questions
Q1. Why is HashMap search O(1)?
Because it uses the key's hash code to calculate the bucket directly instead of scanning every element.
Q2. What is hashing?
Hashing is the process of converting a key into a numeric hash value that determines where the data should be stored.
Q3. What is a bucket?
A bucket is an index in HashMap's internal array where one or more key-value pairs are stored.
Q4. What is a collision?
A collision happens when two different keys map to the same bucket.
Q5. Why do we override both equals() and hashCode()?
hashCode() helps HashMap locate the correct bucket.
equals() identifies the exact object inside that bucket.
Both are required for correct behavior.
Q6. What is resizing?
When the number of stored entries crosses the load factor threshold, HashMap creates a larger internal array and redistributes all existing entries into new buckets.
Q7. What happens if every key has the same hash code?
All entries end up in the same bucket.
Performance drops because Java must search within that bucket instead of jumping directly to a unique location.
Real-World Example
Imagine a massive library with 1 million books.
If the books are lying randomly on shelves, the librarian has to walk through shelf after shelf until the correct book is found. That's exactly how an ArrayList search works.
Now imagine every book is assigned to a numbered rack based on its category code. The librarian looks at the code, walks straight to Rack 42, and finds the book in seconds. That's how a HashMap works.
Sometimes two books belong to the same rack. That's a collision. The librarian then checks the book title to pick the correct one. That's the role of equals() after hashCode() finds the bucket.
Code Example
Summary
An ArrayList works well for sequential data, but it's not the right choice when you need to search millions of records by a unique key. A HashMap solves this by using hashing, buckets, hashCode(), and equals() to locate data quickly, while handling collisions and resizing internally. In interviews, don't stop after saying "HashMap gives O(1) lookup." Explain why it does, because that's the difference between someone who uses Java and someone who understands how Java works internally.
Comments
Post a Comment